1 Search Results for "Skibski, Oskar"

Document
DOI: 10.4230/LIPIcs.ICDT.2023.12
How Do Centrality Measures Choose the Root of Trees?

Authors: Cristian Riveros, Jorge Salas, and Oskar Skibski

Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{riveros_et_al:LIPIcs.ICDT.2023.12,
  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 =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.12},
  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}
}
  • Refine by Author
  • 1 Riveros, Cristian
  • 1 Salas, Jorge
  • 1 Skibski, Oskar

  • Refine by Classification
  • 1 Computing methodologies → Network science
  • 1 Information systems → Data management systems
  • 1 Networks → Network structure
  • 1 Theory of computation → Data structures and algorithms for data management

  • Refine by Keyword
  • 1 Databases
  • 1 centrality measures
  • 1 data centrality
  • 1 graph theory
  • 1 tree structures

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2023

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