Document Open Access Logo

Faster Betweenness Centrality Updates in Evolving Networks

Authors Elisabetta Bergamini, Henning Meyerhenke, Mark Ortmann, Arie Slobbe

PDF
Thumbnail PDF

File

LIPIcs.SEA.2017.23.pdf
  • Filesize: 0.78 MB
  • 16 pages

Document Identifiers

Author Details

Elisabetta Bergamini
Henning Meyerhenke
Mark Ortmann
Arie Slobbe

Cite As Get BibTex

Elisabetta Bergamini, Henning Meyerhenke, Mark Ortmann, and Arie Slobbe. Faster Betweenness Centrality Updates in Evolving Networks. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.SEA.2017.23

Abstract

Finding central nodes is a fundamental problem in network analysis. Betweenness centrality is a well-known measure which quantifies the importance of a node based on the fraction of shortest paths going though it. Due to the dynamic nature of many today’s networks, algorithms that quickly update centrality scores have become a necessity. For betweenness, several dynamic algorithms have been proposed over the years, targeting different update types (incremental- and decremental-only, fully-dynamic). In this paper we introduce a new dynamic algorithm for updating betweenness centrality after an edge insertion or an edge weight decrease. Our method is a combination of two independent contributions: a faster algorithm for updating pairwise distances as well as number of shortest paths, and a faster algorithm for updating dependencies. Whereas the worst-case running time of our algorithm is the same as recomputation, our techniques considerably reduce the number of operations performed by existing dynamic betweenness algorithms. Our experimental evaluation on a variety of real-world networks reveals that our approach is significantly faster than the current state-of-the-art dynamic algorithms, approximately by one order of magnitude on average.

Subject Classification

Keywords
  • Graph algorithms
  • shortest paths
  • distances
  • dynamic algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. David C. Bell, John S. Atkinson, and Jerry W. Carlson. Centrality measures for disease transmission networks. Social Networks, 21(1):1-21, 1999. URL: http://dx.doi.org/10.1016/S0378-8733(98)00010-0.
  2. Elisabetta Bergamini and Henning Meyerhenke. Approximating betweenness centrality in fully dynamic networks. Internet Mathematics, 12(5):281-314, 2016. URL: http://dx.doi.org/10.1080/15427951.2016.1177802.
  3. Elisabetta Bergamini, Henning Meyerhenke, and Christian Staudt. Approximating betweenness centrality in large evolving networks. In 17th Workshop on Algorithm Enginnering and Experiments, ALENEX 2015, pages 133-146. SIAM, 2015. URL: http://dx.doi.org/10.1137/1.9781611973754.12.
  4. Paolo Boldi and Sebastiano Vigna. Axioms for centrality. Internet Mathematics, 10(3-4):222-262, 2014. URL: http://dx.doi.org/10.1080/15427951.2013.865686.
  5. Michele Borassi and Emanuele Natale. KADABRA is an adaptive algorithm for betweenness via random approximation. In 24th Annual European Symposium on Algorithms, ESA 2016, volume 57 of LIPIcs, pages 20:1-20:18. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.20.
  6. Ulrik Brandes. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25:163-177, 2001. Google Scholar
  7. Pierluigi Crescenzi, Gianlorenzo D'Angelo, Lorenzo Severini, and Yllka Velaj. Greedily improving our own centrality in A network. In Experimental Algorithms - 14th International Symposium, SEA 2015, Proceedings, volume 9125 of Lecture Notes in Computer Science, pages 43-55. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-20086-6_4.
  8. Robert Geisberger, Peter Sanders, and Dominik Schultes. Better approximation of betweenness centrality. In 10th Workshop on Algorithm Engineering and Experiments (ALENEX'08), pages 90-100. SIAM, 2008. Google Scholar
  9. Oded Green, Robert McColl, and David A. Bader. A fast algorithm for streaming betweenness centrality. In SocialCom/PASSAT, pages 11-20. IEEE, 2012. Google Scholar
  10. Takanori Hayashi, Takuya Akiba, and Yuichi Yoshida. Fully dynamic betweenness centrality maintenance on massive networks. Proceedings of 41st International Conference on Very Large Data Bases (PVLDB 2015), 9(2):48-59, 2015. Google Scholar
  11. Miray Kas, Matthew Wachs, Kathleen M. Carley, and L. Richard Carley. Incremental algorithm for updating betweenness centrality in dynamically growing networks. In Advances in Social Networks Analysis and Mining 2013 (ASONAM'13), pages 33-40. ACM, 2013. Google Scholar
  12. Christine Kiss and Martin Bichler. Identification of influencers - measuring influence in customer networks. Decision Support Systems, 46(1):233-253, 2008. URL: http://dx.doi.org/10.1016/j.dss.2008.06.007.
  13. Dirk Koschützki, Katharina Anna Lehmann, Leon Peeters, Stefan Richter, Dagmar Tenfelde-Podehl, and Oliver Zlotowski. Centrality indices. In Network Analysis, volume 3418 of LNCS, pages 16-61. Springer Berlin Heidelberg, 2005. URL: http://dx.doi.org/10.1007/978-3-540-31955-9_3.
  14. N. Kourtellis, G. De Francisci Morales, and F. Bonchi. Scalable online betweenness centrality in evolving graphs. Knowledge and Data Engineering, IEEE Transactions on, PP(99):1-1, 2015. Google Scholar
  15. Jérôme Kunegis. KONECT: the koblenz network collection. In 22nd International World Wide Web Conference, WWW'13, pages 1343-1350, 2013. URL: http://dl.acm.org/citation.cfm?id=2488173.
  16. Min-Joong Lee, Sunghee Choi, and Chin-Wan Chung. Efficient algorithms for updating betweenness centrality in fully dynamic graphs. Information Sciences, 326:278-296, 2016. Google Scholar
  17. Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection, June 2014. URL: http://snap.stanford.edu/data.
  18. Chih-Chung Lin and Ruei-Chuan Chang. On the dynamic shortest path problem. Journal of Information Processing, 13(4):470-476, April 1991. URL: http://dl.acm.org/citation.cfm?id=105582.105591.
  19. Meghana Nasre, Matteo Pontecorvi, and Vijaya Ramachandran. Betweenness centrality - incremental and faster. In Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, volume 8635 of Lecture Notes in Computer Science, pages 577-588. Springer, 2014. Google Scholar
  20. Matteo Pontecorvi and Vijaya Ramachandran. Fully dynamic betweenness centrality. In Algorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings, volume 9472 of Lecture Notes in Computer Science, pages 331-342. Springer, 2015. Google Scholar
  21. G. Ramalingam and Thomas W. Reps. On the computational complexity of dynamic graph problems. Theoretical Computer Science, 158(1&2):233-277, 1996. URL: http://dx.doi.org/10.1016/0304-3975(95)00079-8.
  22. Matteo Riondato and Evgenios M. Kornaropoulos. Fast approximation of betweenness centrality through sampling. Data Mining and Knowledge Discovery, 30(2):438-475, 2016. Google Scholar
  23. Matteo Riondato and Eli Upfal. ABRA: approximating betweenness centrality in static and dynamic graphs with rademacher averages. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016, pages 1145-1154. ACM, 2016. URL: http://dx.doi.org/10.1145/2939672.2939770.
  24. Christian L. Staudt, Aleksejs Sazonovs, and Henning Meyerhenke. NetworKit: A tool suite for high-performance network analysis. Network Science, To appear. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact