Approximating nonbacktracking centrality and localization phenomena in large networks

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 with 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 fairly accurate estimates. 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. Our results may also be useful in designing group-based inoculation strategies to control epidemics.