Document Open Access Logo

An Adaptive Version of Brandes' Algorithm for Betweenness Centrality

Authors Matthias Bentert, Alexander Dittmann, Leon Kellerhals, André Nichterlein, Rolf Niedermeier

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.36.pdf
  • Filesize: 0.55 MB
  • 13 pages

Document Identifiers

Author Details

Matthias Bentert
  • Algorithmics and Computational Complexity, Faculty IV, TU Berlin, Germany
Alexander Dittmann
  • Algorithmics and Computational Complexity, Faculty IV, TU Berlin, Germany
Leon Kellerhals
  • Algorithmics and Computational Complexity, Faculty IV, TU Berlin, Germany
André Nichterlein
  • Algorithmics and Computational Complexity, Faculty IV, TU Berlin, Germany
Rolf Niedermeier
  • Algorithmics and Computational Complexity, Faculty IV, TU Berlin, Germany

Funding

  • Kellerhals, Leon: Supported by DFG project FPTinP, NI 369/16.

Cite As Get BibTex

Matthias Bentert, Alexander Dittmann, Leon Kellerhals, André Nichterlein, and Rolf Niedermeier. An Adaptive Version of Brandes' Algorithm for Betweenness Centrality. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 36:1-36:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ISAAC.2018.36

Abstract

Betweenness centrality - measuring how many shortest paths pass through a vertex - is one of the most important network analysis concepts for assessing the relative importance of a vertex. The well-known algorithm of Brandes [2001] computes, on an n-vertex and m-edge graph, the betweenness centrality of all vertices in O(nm) worst-case time. In follow-up work, significant empirical speedups were achieved by preprocessing degree-one vertices and by graph partitioning based on cut vertices. We further contribute an algorithmic treatment of degree-two vertices, which turns out to be much richer in mathematical structure than the case of degree-one vertices. Based on these three algorithmic ingredients, we provide a strengthened worst-case running time analysis for betweenness centrality algorithms. More specifically, we prove an adaptive running time bound O(kn), where k < m is the size of a minimum feedback edge set of the input graph.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • network science
  • social network analysis
  • centrality measures
  • shortest paths
  • tree-like graphs
  • efficient pre- and postprocessing
  • FPT in P

Metrics

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

Related Versions

References

  1. Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter. In Proc. of 26th SODA, pages 1681-1697. SIAM, 2015. Google Scholar
  2. Miriam Baglioni, Filippo Geraci, Marco Pellegrini, and Ernesto Lastres. Fast exact computation of betweenness centrality in social networks. In Proc. of 4th ASONAM, pages 450-456. IEEE Computer Society, 2012. Google Scholar
  3. Ulrik Brandes. A faster algorithm for betweenness centrality. J Math Sociol, 25(2):163-177, 2001. Google Scholar
  4. Wouter De Nooy, Andrej Mrvar, and Vladimir Batagelj. Exploratory Social Network Analysis with Pajek. Cambridge University Press, 2011. Google Scholar
  5. Vladimir Estivill-Castro and Derick Wood. A Survey of Adaptive Sorting Algorithms. ACM Comput Surv, 24(4):441-476, 1992. Google Scholar
  6. Linton Freeman. A set of measures of centrality based on betweenness. Sociometry, 40:35-41, 1977. Google Scholar
  7. Archontia C. Giannopoulou, George B. Mertzios, and Rolf Niedermeier. Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs. Theor Comput Sci, 689:67-95, 2017. Google Scholar
  8. David S. Johnson. The genealogy of theoretical computer science: A preliminary report. ACM SIGACT News, 16(2):36-49, 1984. Google Scholar
  9. Mark E. J. Newman. Who Is the Best Connected Scientist? A Study of Scientific Coauthorship Networks. In Proc. of 23rd CNLS, pages 337-370. Springer, 2004. Google Scholar
  10. André Nichterlein, Rolf Niedermeier, Johannes Uhlmann, and Mathias Weller. On tractable cases of Target Set Selection. SNAM, 3(2):233-256, 2013. Google Scholar
  11. Kim Norlen, Gabriel Lucas, Michael Gebbie, and John Chuang. EVA: Extraction, visualization and analysis of the telecommunications and media ownership network. In Proc. of 14th ITS, 2002. Google Scholar
  12. Rami Puzis, Yuval Elovici, Polina Zilberman, Shlomi Dolev, and Ulrik Brandes. Topology manipulations for speeding betweenness centrality computation. J Comp Net, 3(1):84-112, 2015. Google Scholar
  13. Ahmet Erdem Sariyüce, Kamer Kaya, Erik Saule, and Ümit V. Çatalyürek. Graph Manipulations for Fast Centrality Computation. ACM Trans Knowl Discov Data, 11(3):26:1-26:25, 2017. Google Scholar
  14. Flavio Vella, Massimo Bernaschi, and Giancarlo Carbone. Dynamic Merging of Frontiers for Accelerating the Evaluation of Betweenness Centrality. ACM JEA, 23(1):1.4:1-1.4:19, 2018. Google Scholar
  15. Wei Wang and Choon Yik Tang. Distributed computation of node and edge betweenness on tree graphs. In Proc. of 52nd CDC, pages 43-48. IEEE, 2013. 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