Document Open Access Logo

How Do Centrality Measures Choose the Root of Trees?

Authors Cristian Riveros, Jorge Salas, Oskar Skibski

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2023.12.pdf
  • Filesize: 0.72 MB
  • 17 pages

Document Identifiers

Author Details

Cristian Riveros
  • Pontificia Universidad Católica de Chile, Santiago, Chile
  • Millennium Institute for Foundational Research on Data, Santiago, Chile
Jorge Salas
  • Pontificia Universidad Católica de Chile, Santiago, Chile
  • Millennium Institute for Foundational Research on Data, Santiago, Chile
  • University of Edinburgh, UK
Oskar Skibski
  • University of Warsaw, Poland

Funding

C. Riveros and J. Salas were supported by ANID - Millennium Science Initiative Program - Code ICN17_002. Jorge Salas and Oskar Skibski were supported by the Polish National Science Centre Grant No. 2018/31/B/ST6/03201.

Cite AsGet BibTex

Cristian Riveros, Jorge Salas, and Oskar Skibski. How Do Centrality Measures Choose the Root of Trees?. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ICDT.2023.12

Abstract

Centrality measures are widely used to assign importance to graph-structured data. Recently, understanding the principles of such measures has attracted a lot of attention. Given that measures are diverse, this research has usually focused on classes of centrality measures. In this work, we provide a different approach by focusing on classes of graphs instead of classes of measures to understand the underlying principles among various measures. More precisely, we study the class of trees. We observe that even in the case of trees, there is no consensus on which node should be selected as the most central. To analyze the behavior of centrality measures on trees, we introduce a property of tree rooting that states a measure selects one or two adjacent nodes as the most important, and the importance decreases from them in all directions. This property is satisfied by closeness centrality but violated by PageRank. We show that, for several centrality measures that root trees, the comparison of adjacent nodes can be inferred by potential functions that assess the quality of trees. We use these functions to give fundamental insights on rooting and derive a characterization explaining why some measure root trees. Moreover, we provide an almost linear time algorithm to compute the root of a graph by using potential functions. Finally, using a family of potential functions, we show that many ways of tree rooting exist with desirable properties.

Subject Classification

ACM Subject Classification
  • Information systems → Data management systems
  • Computing methodologies → Network science
  • Networks → Network structure
  • Theory of computation → Data structures and algorithms for data management
Keywords
  • Databases
  • centrality measures
  • data centrality
  • graph theory
  • tree structures

Metrics

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

Related Versions

References

  1. Neo4j: Centrality. URL: https://neo4j.com/docs/graph-data-science/current/algorithms/centrality/.
  2. Tigergraph: Centrality algorithms. URL: https://docs.tigergraph.com/graph-ml/current/centrality-algorithms/.
  3. Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of databases, volume 8. Addison-Wesley Reading, 1995. Google Scholar
  4. Francis Bloch, Matthew O. Jackson, and Pietro Tebaldi. Centrality measures in networks. arXiv preprint, 2019. URL: http://arxiv.org/abs/1608.05845.
  5. Paolo Boldi, Alessandro Luongo, and Sebastiano Vigna. Rank monotonicity in centrality measures. Network Science, 5(4):529-550, 2017. Google Scholar
  6. Paolo Boldi and Sebastiano Vigna. Axioms for centrality. Internet Mathematics, 10(3-4):222-262, 2014. Google Scholar
  7. Phillip Bonacich. Factoring and weighting approaches to status scores and clique identification. Journal of mathematical sociology, 2(1):113-120, 1972. Google Scholar
  8. Ulrik Brandes. Network analysis: methodological foundations, volume 3418. Springer Science & Business Media, 2005. Google Scholar
  9. Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2009. Google Scholar
  10. Zoltán Dezső and Albert-László Barabási. Halting viruses in scale-free networks. Physical Review E, 65:055103, 2002. Google Scholar
  11. Linton C Freeman. A set of measures of centrality based on betweenness. Sociometry, pages 35-41, 1977. Google Scholar
  12. Manuj Garg. Axiomatic foundations of centrality in networks. Available at SSRN 1372441, 2009. Google Scholar
  13. Per Hage and Frank Harary. Eccentricity and centrality in networks. Social networks, 17(1):57-63, 1995. Google Scholar
  14. Aidan Hogan, Andreas Harth, Jürgen Umbrich, Sheila Kinsella, Axel Polleres, and Stefan Decker. Searching and browsing linked data with swse: The semantic web search engine. Journal of web semantics, 9(4):365-401, 2011. Google Scholar
  15. Gábor Iván and Vince Grolmusz. When the web meets the cell: using personalized PageRank for analyzing protein interaction networks. Bioinformatics, 27(3):405-407, 2010. Google Scholar
  16. Matthew O Jackson. Social and economic networks. Princeton university press, 2010. Google Scholar
  17. Mitri Kitti. Axioms for centrality scoring with principal eigenvectors. Social Choice and Welfare, 46(3):639-653, 2016. Google Scholar
  18. Dirk Koschützki, Katharina Anna Lehmann, Leon Peeters, Stefan Richter, Dagmar Tenfelde-Podehl, and Oliver Zlotowski. Centrality indices. In Network analysis, pages 16-61. Springer, 2005. Google Scholar
  19. Jose L Martinez-Rodriguez, Aidan Hogan, and Ivan Lopez-Arevalo. Information extraction meets the semantic web: a survey. Semantic Web, 11(2):255-335, 2020. Google Scholar
  20. Mark Newman. Networks. Oxford university press, 2018. Google Scholar
  21. Juhani Nieminen. On the centrality in a directed graph. Social Science Research, 2(4):371-378, 1973. Google Scholar
  22. Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999. Google Scholar
  23. K Brooks. Reid. Centrality measures in trees. In Advances in Interdisciplinary Applied Discrete Mathematics, pages 167-197. World Scientific, 2011. Google Scholar
  24. Cristian Riveros and Jorge Salas. A family of centrality measures for graph data based on subgraphs. In Carsten Lutz and Jean Christoph Jung, editors, ICDT, volume 155, pages 23:1-23:18, 2020. Google Scholar
  25. Gert Sabidussi. The centrality index of a graph. Psychometrika, 31(4):581-603, 1966. Google Scholar
  26. Oskar Skibski. Vitality indices are equivalent to induced game-theoretic centralities. In Zhi-Hua Zhou, editor, IJCAI, pages 398-404. International Joint Conferences on Artificial Intelligence Organization, 2021. Google Scholar
  27. Oskar Skibski, Tomasz P. Michalak, and Talal Rahwan. Axiomatic characterization of game-theoretic centrality. Journal of Artificial Intelligence Research, 62:33-68, 2018. Google Scholar
  28. René van den Brink and Robert P. Gilles. Measuring domination in directed networks. Social Networks, 22(2):141-157, 2000. Google Scholar
  29. Tomasz Wąs and Oskar Skibski. Axiomatization of the PageRank centrality. In IJCAI, pages 3898-3904. International Joint Conferences on Artificial Intelligence Organization, 2018. Google Scholar
  30. Mihalis Yannakakis. Algorithms for acyclic database schemes. In VLDB, volume 81, pages 82-94, 1981. 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 Imprint Privacy Contact