Scale-dependent measure of network centrality from diffusion dynamics

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.

References in corpus (12)

• Cooperative Game Theory Approaches for Network Partitioning
• Identification of influential spreaders in complex networks
• OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks
• Subgraph Centrality in Complex Networks
• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• Laplacian Dynamics and Multiscale Modular Structure in Networks
• Localization and centrality in networks
• Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
• Flow-based network analysis of the Caenorhabditis elegans connectome
• Structure of complex networks: Quantifying edge-to-edge relations by failure-induced flow redistribution
• Multiscale dynamical embeddings of complex networks
• Absorbing Random Walks Interpolating Between Centrality Measures on Complex Networks

Cited by in corpus (8)

• Linking the Network Centrality Measures Closeness and Degree
• Unfolding the multiscale structure of networks with dynamical Ollivier-Ricci curvature
• Relative, local and global dimension in complex networks
• An integrative dynamical perspective for graph theory and the study of complex networks
• Multiscale mobility patterns and the restriction of human movement
• Adjustable reach in a network centrality based on current flows
• Modeling advection on distance-weighted directed networks
• Gromov Centrality: A Multi-Scale Measure of Network Centrality Using Triangle Inequality Excess