Localization of nonbacktracking centrality on dense subgraphs of sparse networks
- 3 January 2023
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 107 (1) , 014301
Abstract
The nonbacktracking matrix and the related nonbacktracking centrality (NBC) play a crucial role in models of percolation-type processes on networks, such as nonrecurrent epidemics. Here we study the localization of NBC in infinite sparse networks that contain an arbitrary finite subgraph. Assuming the local tree likeness of the enclosing network, and that branches emanating from the finite subgraph do not intersect at finite distances, we show that the largest eigenvalue of the nonbacktracking matrix of the composite network is equal to the highest of the two largest eigenvalues: that of the finite subgraph and of the enclosing network. In the localized state, when the largest eigenvalue of the subgraph is the highest of the two, we derive explicit expressions for the NBCs of nodes in the subgraph and other nodes in the network. In this state, nonbacktracking centrality is concentrated on the subgraph and its immediate neighborhood in the enclosing network. We obtain simple, exact formulas in the case where the enclosing network is uncorrelated. We find that the mean NBC decays exponentially around the finite subgraph, at a rate which is independent of the structure of the enclosing network, contrary to what was found for the localization of the principal eigenvector of the adjacency matrix. Numerical simulations confirm that our results provide good approximations even in moderately sized, loopy, real-world networks.Keywords
All Related Versions
Funding Information
- Fundação para a Ciência e a Tecnologia (CEECIND/03838/2017)
This publication has 29 references indexed in Scilit:
- Spectral redemption in clustering sparse networksProceedings of the National Academy of Sciences, 2013
- Epidemic thresholds of the susceptible-infected-susceptible model on networks: A comparison of numerical and theoretical resultsPhysical Review E, 2012
- Localization and Spreading of Diseases in Complex NetworksPhysical Review Letters, 2012
- Intermittent social distancing strategy for epidemic controlPhysical Review E, 2012
- Thresholds for Epidemic Spreading in NetworksPhysical Review Letters, 2010
- Message passing approach for general epidemic modelsPhysical Review E, 2010
- Localized spatial clustering of HIV infections in a widely disseminated rural South African epidemicInternational Journal of Epidemiology, 2009
- Spread of epidemic disease on networksPhysical Review E, 2002
- On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphsIEEE Transactions on Information Theory, 2001
- The Ising model and percolation on trees and tree-like graphsCommunications in Mathematical Physics, 1989