Approximating Betweenness Centrality in Fully Dynamic Networks

References

• D. A. Bader, S. Kintali, K. Madduri, and M. Mihail. “Approximating Betweenness Centrality.” In 5th Workshop on Algorithms and Models for the Web-Graph (WAW ’07), pp. 124–137, LNCS 4863. Berlin, Heidelberg: Springer, 2007.
   Google Scholar
• D. A. Bader, H. Meyerhenke, P. Sanders, C. Schulz, A. Kappes, and D. Wagner. “Benchmarking for Graph Clustering and Partitioning.” In Encyclopedia of Social Network Analysis and Mining, edited by R. Alhajj and J. Rokne, pp. 73–82. New York, NY: Springer, 2014.
   Google Scholar
• R. Bauer and D. Wagner. “Batch Dynamic Single-Source Shortest-Path Algorithms: An Experimental Study.” In 8th Int. Symp. on Experimental Algorithms (SEA ’09), pp. 51–62, LNCS 5526. Berlin, Heidelberg: Springer, 2009.
   Google Scholar
• E. Bergamini and H. Meyerhenke. “Fully-Dynamic Approximation of Betweenness Centrality.” In Algorithms - ESA 2015-23rd Annual European Symposium, Proceedings, edited by N. Bansal and I. Finocchi, pp. 155–166. Berlin, Heidelberg: Springer, 2015.
   Google Scholar
• E. Bergamini, H. Meyerhenke, and C. Staudt. “Approximating Betweenness Centrality in Large Evolving Networks.” In 17th Workshop on Algorithm Engineering and Experiments, ALENEX 2015, pp. 133–146. SIAM, 2015.
   Google Scholar
• M. Borassi, P. Crescenzi, and A. Marino. “Fast and Simple Computation of Top-k Closeness Centralities.” Available online (http://arxiv.org/abs/1507.01490), 2015.
   Google Scholar
• U. Brandes. “A Faster Algorithm for Betweenness Centrality.” Journal of Mathematical Sociology 25 (2001), 163–177.
   Web of Science ®Google Scholar
• U. Brandes and C. Pich. “Centrality Estimation in Large Networks.” I. J. Bifurcation and Chaos 17: 7 (2007), 2303–2318.
   Web of Science ®Google Scholar
• M. H. Chehreghani. “An Efficient Algorithm for Approximate Betweenness Centrality Computation.” Comput. J. 57: 9 (2014), 1371–1382.
   Web of Science ®Google Scholar
• A. D’Andrea, M. D’Emidio, D. Frigioni, S. Leucci, and G. Proietti. “Experimental Evaluation of Dynamic Shortest Path Tree Algorithms on Homogeneous Batches.” In 13th Int. Symp. on Experimental Algorithms (SEA ’14), pp. 283–294, LNCS 8504. Berlin, Heidelberg: Springer, 2014.
   Google Scholar
• S. N. Dorogovtsev and J. F. Mendes. Evolution of Networks: From Biological Nets to the Internet and WWW. Oxford, UK: Oxford University Press, 2003.
   Google Scholar
• L. C. Freeman. “A Set of Measures of Centrality Based on Betweenness.” Sociometry 40: 1 (1977), 35–41.
   Google Scholar
• D. Frigioni, A. Marchetti-Spaccamela, and U. Nanni. “Semi-Dynamic Algorithms for Maintaining Single-Source Shortest Path Trees.” Algorithmica 22 (2008), 250–274.
   Web of Science ®Google Scholar
• R. Geisberger, P. Sanders, and D. Schultes. “Better Approximation of Betweenness Centrality.” In 10th Workshop on Algorithm Engineering and Experiments (ALENEX ’08), pp. 90–100. SIAM, 2008.
   Google Scholar
• K. Goel, R. R. Singh, S. Iyengar, and S. Gupta. “A Faster Algorithm to Update Betweenness Centrality after Node Alteration.” Internet Mathematics 11: 4-5 (2015), 403–420.
   Web of Science ®Google Scholar
• O. Green, R. McColl, and D. A. Bader. “A Fast Algorithm for Streaming Betweenness Centrality.” In SocialCom/PASSAT, pp. 11–20. IEEE, 2012.
   Google Scholar
• M. Kas, M. Wachs, K. M. Carley, and L. R. Carley. “Incremental Algorithm for Updating Betweenness Centrality in Dynamically Growing Networks.” In Advances in Social Networks Analysis and Mining 2013 (ASONAM ’13), pp. 33–40. New York, NY: ACM, 2013.
   Google Scholar
• N. Kourtellis, G. D. F. Morales, and F. Bonchi. “Scalable Online Betweenness Centrality in Evolving Graphs.” IEEE Trans. Knowl. Data Eng. 27: 9 (2015), 2494–2506.
   Web of Science ®Google Scholar
• J. Kunegis. “KONECT: The Koblenz Network Collection.” In 22nd Int. World Wide Web Conf., WWW ’13, pp. 1343–1350. WWW, 2013.
   Google Scholar
• M. Lee, J. Lee, J. Y. Park, R. H. Choi, and C. Chung. “QUBE: A Quick Algorithm for Updating Betweenness Centrality.” In Proceedings of the 21st World Wide Web Conference 2012, WWW 2012, edited by A. Mille, F. L. Gandon, J. Misselis, M. Rabinovich, and S. Staab, editors, pp. 351–360. New York, NY: ACM, 2012.
   Google Scholar
• J. Leskovec, J. M. Kleinberg, and C. Faloutsos. “Graphs Over Time: Densification Laws, Shrinking Diameters and Possible Explanations.” In 11th Int. Conf. on Knowledge Discovery and Data Mining, pp. 177–187. New York, NY: ACM, 2005.
   Google Scholar
• M. Nasre, M. Pontecorvi, and V. Ramachandran. “Betweenness Centrality - Incremental and Faster.” In Mathematical Foundations of Computer Science 2014-39th Int. Symp., MFCS 2014, pp. 577–588, LNCS 8635. Berlin, Heidelberg: Springer, 2014.
   Google Scholar
• M. Pontecorvi and V. Ramachandran. “A Faster Algorithm for Fully Dynamic Betweenness Centrality.” CoRR, abs/1506.05783, 2015.
   Google Scholar
• G. Ramalingam and T. Reps. “An Incremental Algorithm for a Generalization of the Shortest-Path Problem.” Journal of Algorithms 21 (1992), 267–305.
   Web of Science ®Google Scholar
• M. Riondato and E. M. Kornaropoulos. “Fast Approximation of Betweenness Centrality Through Sampling.” Data Mining and Knowledge Discovery 30: 2 (2016), 438–475.
   Web of Science ®Google Scholar
• L. Roditty and U. Zwick. “On Dynamic Shortest Paths Problems.” Algorithmica 61: 2 (2011), 389–401.
   Web of Science ®Google Scholar
• C. Staudt, A. Sazonovs, and H. Meyerhenke. “NetworKit: An Interactive Tool Suite for High-Performance Network Analysis.” (http://arxiv.org/abs/1403.3005), 2014.
   Google Scholar
• M. von Looz, H. Meyerhenke, and R. Prutkin. “Generating Random Hyperbolic Graphs in Subquadratic Time.” In Proc. 26th Int’l Symp. on Algorithms and Computation (ISAAC 2015), LNCS. Berlin, Heidelberg: Springer, 2015. To appear.
   Google Scholar