|Created: 28 Jul 2014||Modified: 23 Jun 2017||BibTeX Entry||RIS Citation|
The goal here is to prototype a smooth and efficient way of evolving a
NetworkX graph object, given a more compact specification of a “interval” temporal network, as discussed in Temporal Networks in SeriationCT.
In the following, I assume either that a compact configuration, or a random network generating process (NGP), produces a sequence of
numpy matrices which are indexed by a time coordinate. The task, then, is to examine differences in the sequence of matrices, and produce corresponding changes to a
NetworkX graph object, without simply destroying and reformulating the graph object.
The latter requirement is important because each vertex in the graph object will also be a container, holding a subpopulation of agents which are engaged in social learning. Vertices will thus represent demes of individuals, and our observable samples in the
seriationct model will be derived as time-averaged samples of traits from each vertex.
For simplicity, I start with the complete graph \(C4\) on four vertices, with one link having a link weight
import numpy as np import networkx as nx import matplotlib.pyplot as plt # start with C4, the complete graph on four vertices, with uniform weights t1 = np.array([[1,3,1,1],[3,1,1,1],[1,1,1,1],[1,1,1,1]]) g = nx.to_networkx_graph(t1)
At step 2, we imagine that two links are lost, indicated by their weight going to zero in the adjacency matrix.
# step 1 - loss of two links t2 = np.array([[1,0,1,1],[0,1,1,1],[1,1,1,0],[1,1,0,1]]) g2 = nx.to_networkx_graph(t2)
We can tell which edges change by looking at the nonzero elements of the upper triangular portion of the difference of the two matrices:
t2 - t1 # array([[ 0, -3, 0, 0], # [-3, 0, 0, 0], # [ 0, 0, 0, -1], # [ 0, 0, -1, 0]]) np.nonzero(np.triu(t2 - t1)) # (array([0, 2]), array([1, 3])) changed = t2 - t1 changed_edges = np.nonzero(np.triu(changed)) # (array([0, 2]), array([1, 3]))
changed_edges reports those elements which are different between the two matrices, in the upper triangular portion of the matrix. We are mainly interested in off-diagonal elements at the moment. The data structure is a tuple composed of two lists, the row and then the column coordinates. This unusual structure is the reason for the use of
zip in the enumeration below.
Weight changes to existing edges are simply the difference between the two matrix elements, already reflected in the
changed matrix entry, and we can detect edges that go away entirely by a weight change which complete offsets the
t1 weight at
t2. If an edge goes away, we remove it. If the weight changes, we alter the weight property for the edge
for i,j in zip(changed_edges, changed_edges): weight_delta = changed[i,j] removed = False if t1[i,j] + changed[i,j] else True print "changed edge at %s,%s - weight delta: %s remove? %s" % (i,j, weight_delta, removed) if removed: g.remove_edge(i,j) else: g[i][j]['weight'] += weight_delta # changed edge at 0,1 - weight delta: -3 remove? True # changed edge at 2,3 - weight delta: -1 remove? True