Localization and centrality in networks

Abstract

Eigenvector centrality is a common measure of the importance of nodes in a network. Here we show that under common conditions the eigenvector centrality displays a localization transition that causes most of the weight of the centrality to concentrate on a small number of nodes in the network. In this regime the measure is no longer useful for distinguishing among the remaining nodes and its efficacy as a network metric is impaired. As a remedy, we propose an alternative centrality measure based on the nonbacktracking matrix, which gives results closely similar to the standard eigenvector centrality in dense networks where the latter is well behaved, but avoids localization and gives useful results in regimes where the standard centrality fails.

arXiv comment5 pages, 1 figure

References in corpus (11)

• Emergence of scaling in random networks
• Random graphs with arbitrary degree distributions and their applications
• Spectral redemption: clustering sparse networks
• Spectra of "Real-World" Graphs: Beyond the Semi-Circle Law
• Localization and Spreading of Diseases in Complex Networks
• Generic scale of the "scale-free" growing networks
• Pseudo-likelihood methods for community detection in large sparse networks
• Spectra and eigenvectors of scale-free networks
• Modularity and Extreme Edges of the Internet
• Spectra of random graphs with arbitrary expected degrees
• Spectral properties of Google matrix of Wikipedia and other networks

Cited by in corpus (101)

• Epidemic processes in complex networks
• Vital nodes identification in complex networks
• Random walks and diffusion on networks
• Statistical physics of inference: Thresholds and algorithms
• Unification of theoretical approaches for epidemic spreading on complex networks
• Consistency and differences between centrality measures across distinct classes of networks
• Coevolution spreading in complex networks
• A framework for epidemic spreading in multiplex networks of metapopulations
• Distinct types of eigenvector localization in networks
• Predicting percolation thresholds in networks
• Finding influential nodes for integration in brain networks using optimal percolation theory
• A message-passing approach for recurrent-state epidemic models on networks
• Predicting the speed of epidemics spreading on networks
• Leveraging percolation theory to single out influential spreaders in networks
• Relating Topological Determinants of Complex Networks to Their Spectral Properties: Structural and Dynamical Effects
• Eigenvector localization in real networks and its implications for epidemic spreading
• Efficient collective influence maximization in cascading processes with first-order transitions
• Disentangling bipartite and core-periphery structure in financial networks
• Predicting the epidemic threshold of the susceptible-infected-recovered model
• Spectra of networks containing short loops
• Belief propagation for networks with loops
• Identifying an influential spreader from a single seed in complex networks via a message-passing approach
• Spectra of random networks with arbitrary degrees
• Urban Scaling of Cities in the Netherlands
• Accurate ranking of influential spreaders in networks based on dynamically asymmetric link-impact
• Master equation analysis of mesoscopic localization in contagion dynamics on higher-order networks
• The localization of non-backtracking centrality in networks and its physical consequences
• Universality in the spectral and eigenfunction properties of random networks
• A message-passing approach to epidemic tracing and mitigation with apps
• Systematic comparison between methods for the detection of influential spreaders in complex networks
• Message passing methods on complex networks
• Nonbacktracking expansion of finite graphs
• Spacing ratio characterization of the spectra of directed random networks
• Super-resolution community detection for layer-aggregated multilayer networks
• Stochasticity in pandemic spread over the World Airline Network explained by local flight connections
• Localization and universality of eigenvectors in directed random graphs
• Centrality metrics and localization in core-periphery networks
• Principal eigenvector localization and centrality in networks: revisited
• Exact distribution of spacing ratios for random and localized states in quantum chaotic systems
• Relevance of backtracking paths in epidemic spreading on networks
• Heterogeneous micro-structure of percolation in sparse networks
• Optimized evolution of networks for principal eigenvector localization
• Eigenvalue Repulsion and Eigenfunction Localization in Sparse Non-Hermitian Random Matrices
• Topological structure and the H-index in complex networks
• Influential spreaders for recurrent epidemics on networks
• Dimension reduction of dynamical systems on networks with leading and non-leading eigenvectors of adjacency matrices
• Influencers identification in complex networks through reaction-diffusion dynamics
• Scale-dependent measure of network centrality from diffusion dynamics
• Impact of presymptomatic transmission on epidemic spreading in contact networks: A dynamic message-passing analysis
• Message-Passing Methods for Complex Contagions
• A Network Science perspective of Graph Convolutional Networks: A survey
• Targeted influence maximization in complex networks
• Quantum centrality testing on directed graphs via PT-symmetric quantum walks
• Analytic solution of the resolvent equations for heterogeneous random graphs: spectral and localization properties
• Dynamic range maximization in excitable networks
• Orientations and matrix function-based centralities in multiplex network analysis of urban public transport
• Nonlocal PageRank
• Finding the Resistance Distance and Eigenvector Centrality from the Network's Eigenvalues
• Centrality Measures in Complex Networks: A Survey
• Percolation in random graphs with higher-order clustering
• Localization of eigenvector centrality in networks with a cut vertex
• Multifractality in random networks with power-law decaying bond strengths
• Node Immunization with Non-backtracking Eigenvalues
• Effect of network clustering on mutually cooperative coinfections
• Identifying Influential Nodes in Two-mode Data Networks using Formal Concept Analysis
• Spectral theory of the non-backtracking Laplacian for graphs
• Analysis of the Dynamics and Topology Dependencies of Small Perturbations in Electric Transmission Grids
• Dissent and Rebellion in the House of Commons: A Social Network Analysis of Brexit-Related Divisions in the 57${}^{th}$ Parliament
• Localization transition in non-Hermitian systems depending on reciprocity and hopping asymmetry
• The Bow-Tie Centrality: A Novel Measure for Directed and Weighted Networks with an Intrinsic Node Property
• Non-backtracking Spectrum: Unitary Eigenvalues and Diagonalizability
• Model-free hidden geometry of complex networks
• Susceptible-infected-susceptible model on networks with eigenvector localization
• Influence Maximization: Divide and Conquer
• Graph Distance from the Topological View of Non-backtracking Cycles
• Factorized Graph Representations for Semi-Supervised Learning from Sparse Data
• Popularity and Centrality in Spotify Networks: Critical transitions in eigenvector centrality
• The Atlas for the Aspiring Network Scientist
• Generating functions for message-passing on weighted networks: directed bond percolation and SIR epidemics
• Backtracking activation impacts the criticality of excitable networks
• Spectral density of equitable core-periphery graphs
• Influence measures in subnetworks using vertex centrality
• Adjustable reach in a network centrality based on current flows
• Central limit theorem for the principal eigenvalue and eigenvector of Chung-Lu random graphs
• Localization of nonbacktracking centrality on dense subgraphs of sparse networks
• Maximizing spreading in complex networks with risk in node activation
• Making root cause analysis feasible for large code bases: a solution approach for a climate model
• Wheel graph strategy for PEV localization of networks
• Eigenfactor
• Thematic recommendations on knowledge graphs using multilayer networks
• On the initial value of PageRank
• The Perron non-backtracking eigenvalue after node addition
• Large Fixed-Diameter Graphs are Good Expanders
• Approximating nonbacktracking centrality and localization phenomena in large networks
• Network construction: A learning framework through localizing principal eigenvector
• Complex non-backtracking matrix for directed graphs
• Impacts of bridging nodes on the epidemic activation mechanisms
• Statistics of remote regions of networks
• Identifying super-spreaders in information-epidemic coevolving dynamics on multiplex networks
• Spectral analysis for gene communities in cancer cells
• Non-Backtracking Centrality Based Random Walk on Networks