We use both real-world and synthetic networks. In case of disconnected graphs, we extract the largest connected component first. The properties of real-world networks are summarised in Table REF . We cover a range from relatively small networks, on which we test all the implemented algorithms, to large networks with millions of edges, on which we can execute only the most scalable methods, i.e. RK and our incremental approach. In particular, the introduction of approximation allows us to approach graphs of several orders of magnitude larger than those considered by previous dynamic algorithms [1]}.
Our test set includes routing/transportation networks in which BC has a straightforward interpretation, as well as social networks in which BC can be understood as a measure of social influence.
Most networks are publicly available from the collection compiled for the 10th DIMACS challengehttp://www.cc.gatech.edu/dimacs10/downloads.shtml [2]}.
Due to a shortage of actual dynamic network data with only edge dynamics, we simulate dynamics on these real networks by removing a small fraction of random edges (without separating the connected component) and adding them back in batches.
To study the scalability of the methods, we also use synthetic graphs of growing sizes obtained with the Dorogovtsev-Mendes generator, a simple and scalable model for networks with power-law degree distribution [3]}. Since NPR and our IAW perform best on weighted graphs, we also generate weighted instances of Dorogovtsev-Mendes networks, by adding random weights to the edges according to a Gaussian distribution with mean 1 and standard deviation 0.1.
<TABLE>