The localization of non-backtracking centrality in networks and its physical consequences

Abstract

The spectrum of the non-backtracking matrix plays a crucial role in determining various structural and dynamical properties of networked systems, ranging from the threshold in bond percolation and non-recurrent epidemic processes, to community structure, to node importance. Here we calculate the largest eigenvalue of the non-backtracking matrix and the associated non-backtracking centrality for uncorrelated random networks, finding expressions in excellent agreement with numerical results. We show however that the same formulas do not work well for many real-world networks. We identify the mechanism responsible for this violation in the localization of the non-backtracking centrality on network subgraphs whose formation is highly unlikely in uncorrelated networks, but rather common in real-world structures. Exploiting this knowledge we present an heuristic generalized formula for the largest eigenvalue, which is remarkably accurate for all networks of a large empirical dataset. We show that this newly uncovered localization phenomenon allows to understand the failure of the message-passing prediction for the percolation threshold in many real-world structures.

References in corpus (6)

• Critical phenomena in complex networks
• A message passing approach for general epidemic models
• Percolation on sparse networks
• Langevin approach for the dynamics of the contact process on annealed scale-free networks
• Predicting percolation thresholds in networks
• On the numerical study of percolation and epidemic critical properties in networks

Cited by in corpus (6)

• Impact of presymptomatic transmission on epidemic spreading in contact networks: A dynamic message-passing analysis
• Centralities in complex networks
• Localization of nonbacktracking centrality on dense subgraphs of sparse networks
• Comparison of theoretical approaches for epidemic processes with waning immunity in complex networks
• Impacts of bridging nodes on the epidemic activation mechanisms
• Approximating nonbacktracking centrality and localization phenomena in large networks