How do centrality measures choose the root of trees?
| Autor: | Riveros, Cristian, Salas, Jorge, Skibski, Oskar |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Social and Information Networks (cs.SI)
FOS: Computer and information sciences 68P15 68P01 68R10 Networks → Network structure Discrete Mathematics (cs.DM) centrality measures graph theory data centrality Theory of computation → Data structures and algorithms for data management Information systems → Data management systems Computer Science - Social and Information Networks Databases (cs.DB) G.2.2 Databases Computing methodologies → Network science Computer Science - Databases E.0 Computer Science - Discrete Mathematics tree structures |
| DOI: | 10.48550/arxiv.2112.13736 |
| Popis: | 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. LIPIcs, Vol. 255, 26th International Conference on Database Theory (ICDT 2023), pages 12:1-12:17 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|