License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2023.12
URN: urn:nbn:de:0030-drops-177545
Go to the corresponding LIPIcs Volume Portal

Riveros, Cristian ; Salas, Jorge ; Skibski, Oskar

How Do Centrality Measures Choose the Root of Trees?

LIPIcs-ICDT-2023-12.pdf (0.7 MB)


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.

BibTeX - Entry

  author =	{Riveros, Cristian and Salas, Jorge and Skibski, Oskar},
  title =	{{How Do Centrality Measures Choose the Root of Trees?}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{12:1--12:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-270-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{255},
  editor =	{Geerts, Floris and Vandevoort, Brecht},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-177545},
  doi =		{10.4230/LIPIcs.ICDT.2023.12},
  annote =	{Keywords: Databases, centrality measures, data centrality, graph theory, tree structures}

Keywords: Databases, centrality measures, data centrality, graph theory, tree structures
Collection: 26th International Conference on Database Theory (ICDT 2023)
Issue Date: 2023
Date of publication: 17.03.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI