Graph centrality is a question of scale
File(s)PhysRevResearch.2.033104.pdf (4.65 MB)
Published version
Author(s)
Peach, Robert
Arnaudon, Alexis
Barahona, Mauricio
Type
Journal Article
Abstract
Classic measures of graph centrality capture distinct aspects of node importance, from the local (e.g., degree) to the global (e.g., closeness). Here we exploit the connection between diffusion and geometry to introduce a multiscale centrality measure. A node is defined to be central if it breaks the metricity of the diffusion as a consequence of the effective boundaries and inhomogeneities in the graph. Our measure is naturally multiscale, as it is computed relative to graph neighbourhoods within the varying time horizon of the diffusion. We find that the centrality of nodes can differ widely at different scales. In particular, our measure correlates with degree (i.e., hubs) at small scales and with closeness (i.e., bridges) at large scales, and also reveals the existence of multi-centric structures in complex networks. By examining centrality across scales, our measure thus provides an evaluation of node importance relative to local and global processes on the network.
Date Issued
2020-07-01
Date Acceptance
2020-06-15
Citation
Physical Review Research, 2020, 2 (3)
ISSN
2643-1564
Publisher
American Physical Society
Journal / Book Title
Physical Review Research
Volume
2
Issue
3
Copyright Statement
© 2020 The Author(s). Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.
License URL
Sponsor
Engineering & Physical Science Research Council (EPSRC)
Identifier
arxiv:1907.08624v1
Grant Number
EP/N014529/1
Subjects
physics.soc-ph
physics.soc-ph
cs.SI
Publication Status
Published
Article Number
033104
Date Publish Online
2020-07-20