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.