Dynamic computation of network statistics via updating schema

Given a large network, computing statistics such as clustering coefficient, or modularity, is costly for large networks. When one more edge or vertex is added, traditional methods require that the full (expensive) computation be redone on this slightly modified graph. Alternatively, we introduce here a new approach: under modification to the graph, we update the statistics instead of computing them from scratch. In this paper we provide update schemes for a number of popular statistics, to include degree distribution, clustering coefficient, assortativity, and modularity. Our primary aim is to reduce the computational complexity needed to track the evolving behavior of large networks. As an important consequence, this approach provides efficient methods which may support modeling the evolution of dynamic networks to identify and understand critical transitions. Using the updating scheme, the network statistics can be computed much faster than re-calculating each time that the network evolves. We also note that the update formula can be used to determine which edge or node will lead to the extremal change of network statistics, providing a way of predicting or designing network evolution rules that would optimize some chosen statistic. We present our evolution methods in terms of a network statistics differential notation.

Figure 1

(Color online) Schematic addition of an edge. The original graph consists of $N=5$ nodes (solid circles) and $M=6$ edges (solid lines). We have, for the original graph, the degree vector $k=[2,3,3,2,2]$, the triangle vector $△=[1,1,1,0,0]$, the clustering coefficient vector $C=[1,\frac{1}{3},\frac{1}{3},0,0]$, and the average clustering coefficient is $\frac{1}{3}$. After an edge is added between node 2 and node 5 (dashed line), the above statistics change to $\tilde{k}=[2,4,3,2,3]$, $\widetilde{△}=[1,3,2,1,2]$, $\tilde{C}=[1,\frac{1}{2},\frac{2}{3},1,\frac{2}{3}]$, and the new average clustering coefficient becomes $\frac{23}{30}$.

Figure 2

(Color online) An example that the modularity actually decreases when a new edge is added to vertices within the same group. The dashed oval boxes indicate the preexisting partition of the graph into two groups. Solid lines are the edges in the original graph. Before adding the new edge (dashed arrow line), the modularity is 0.125. After a new edge is added between two vertices in the same group (solid circles) the updated modularity becomes 0.1235.

Figure 3

(Color online) Schematic removal of an edge. The original graph consists of $N=5$ nodes (solid circles) and $M=7$ edges (solid lines), with statistics $k=[2,4,3,2,3]$, $△=[1,3,2,1,2]$, $C=[1,\frac{1}{2},\frac{2}{3},1,\frac{2}{3}]$, and average clustering coefficient $\frac{23}{30}$. After the edge between node 2 and node 5 is deleted, the new statistics are $\widehat{k}=[2,3,3,2,2]$, $\widehat{△}=[1,1,1,0,0]$ $\widehat{C}=[1,\frac{1}{3},\frac{1}{3},0,0]$, and the new average clustering coefficient is $\frac{1}{3}$. Note that this is a symmetric operation to the one shown in Fig. 1.

Figure 4

Evolution of degree distribution of a random growing network. The number of vertices is 1000 in the network. Initially the connection probability of any pair of edges is 0.01, by adding random edges in the network, this probability increases to 0.02 in the end. We show two views of the evolution of the degree distribution as with respect to the process of add successive random edges. In the left panel we see that for any given time, the empirical distribution shows the underlying Poission process, and the peak is moving to larger degree side as time increases. The right panel simply provides an alternate view of the same data, providing clearer visualization of hidden portions of the three-dimensional surface.

Figure 5

(Color online) Evolution of the average clustering coefficient $C$ of a growing Barabasi-Albert network. In the left panel we show the evolution of the average clustering coefficient $C$ at each time instance. In the right panel we show the change of average clustering coefficient $\Delta C$. Note that to obtain this curve of the evolution of $C$, we only need to compute $C$ for the initial network once, which requires $O(⟨k{⟩}^{3}N)$ operations, and then adopt our update formula, which requires $O(⟨k⟩)$ operations per step; while if one uses direct computation, it would require $O(⟨k{⟩}^{3}N)$ to compute each single step, and is highly inefficient. The structure in the right side graph is only observable because we compute the change at each time step and would be obscured if one were to compute the change over larger time increments.

Figure 6

(Color online) Spy plot at three specific instances for the adjacency matrix. The left panel corresponds to the initial network ($p_1=p_2=0.2$ and $p_{\mathit{\text{between}}}=0.05$), where there is a clear community structure. The middle panel corresponds to the time when $p_{\mathit{\text{between}}}$ reaches 0.1 where the community structure becomes less apparent. The right panel is the end of the growing process such that $p_{\mathit{\text{between}}}=0.2$ and the network is totally random with no community structure.

Figure 7

(Color online) The evolution of modularity $Q$. Three red squares correspond to the time instances that are shown in Fig. 6