Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

How Do Centrality Measures Choose the Root of Trees?

Uproszczony widok
dc.abstract.enCentrality 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.
dc.affiliationUniwersytet Warszawski
dc.conference.countryGrecja
dc.conference.datefinish2023-03-31
dc.conference.datestart2023-03-28
dc.conference.placeIoannina
dc.conference.seriesInternational Conference on Database Theory
dc.conference.seriesInternational Conference on Database Theory
dc.conference.seriesshortcutICDT
dc.conference.shortcutICDT 2023
dc.conference.weblinkhttp://edbticdt2023.cs.uoi.gr/
dc.contributor.authorSkibski, Oskar
dc.contributor.authorJorge, Salas
dc.contributor.authorCristian, Riveros
dc.date.accessioned2024-01-25T03:29:41Z
dc.date.available2024-01-25T03:29:41Z
dc.date.issued2023
dc.description.financePublikacja bezkosztowa
dc.identifier.doi10.4230/LIPICS.ICDT.2023.12
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/108645
dc.identifier.weblinkhttps://drops.dagstuhl.de/opus/volltexte/2023/17754/
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages12:1-17
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.subject.endatabases
dc.subject.encentrality measures
dc.subject.endata centrality
dc.subject.engraph theory
dc.subject.entree structures
dc.titleHow Do Centrality Measures Choose the Root of Trees?
dc.typeJournalArticle
dspace.entity.typePublication