Approximating nonbacktracking centrality and localization phenomena in large networks

Abstract

Message-passing theories have proved to be invaluable tools in studying percolation, non-recurrent epidemics and similar dynamical processes on real-world networks. At the heart of the message-passing method is the nonbacktracking matrix whose largest eigenvalue, the corresponding eigenvector, and the closely related nonbacktracking centrality play a central role in determining how the given dynamical model behaves. Here we propose a degree-class-based method to approximate these quantities using a smaller matrix related to the joint degree-degree distribution of neighbouring nodes. Our findings suggest that in most networks degree-degree correlations beyond nearest neighbour are actually not strong, and our first-order description already results in accurate estimates, particularly when message-passing itself is a good approximation to the original model in question, that is when the number of short cycles in the network is sufficiently low. We show that localization of the nonbacktracking centrality is also captured well by our scheme, particularly in large networks. Our method provides an alternative to working with the full nonbacktracking matrix in very large networks where this may not be possible due to memory limitations.

arXiv comment11 pages, 6 figures; supplemental material

References in corpus (18)

• Critical phenomena in complex networks
• Influence maximization in complex networks through optimal percolation
• Spectral redemption: clustering sparse networks
• Epidemic spreading in correlated complex networks
• A message passing approach for general epidemic models
• Localization and Spreading of Diseases in Complex Networks
• Localization and centrality in networks
• Percolation on sparse networks
• Percolation on correlated networks
• Competing activation mechanisms in epidemics on networks
• Distinct types of eigenvector localization in networks
• Predicting percolation thresholds in networks
• Predicting the speed of epidemics spreading on networks
• Leveraging percolation theory to single out influential spreaders in networks
• Eigenvector localization in real networks and its implications for epidemic spreading
• Identifying an influential spreader from a single seed in complex networks via a message-passing approach
• The localization of non-backtracking centrality in networks and its physical consequences
• Nonbacktracking expansion of finite graphs