# Node Immunization with Non-backtracking Eigenvalues

arXiv: https://arxiv.org/abs/2002.12309 · HTML: https://mlsanity.com/paper/2002.12309/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2020.

## Built on by (most cited first, 1 of 1)

- [Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphs](https://mlsanity.com/paper/2103.03561/) (2021)

## Abstract (arXiv)

The non-backtracking matrix and its eigenvalues have many applications in network science and graph mining, such as node and edge centrality, community detection, length spectrum theory, graph distance, and epidemic and percolation thresholds. Moreover, in network epidemiology, the reciprocal of the largest eigenvalue of the non-backtracking matrix is a good approximation for the epidemic threshold of certain network dynamics. In this work, we develop techniques that identify which nodes have the largest impact on the leading non-backtracking eigenvalue. We do so by studying the behavior of the spectrum of the non-backtracking matrix after a node is removed from the graph. From this analysis we derive two new centrality measures: X-degree and X-non-backtracking centrality. We perform extensive experimentation with targeted immunization strategies derived from these two centrality measures. Our spectral analysis and centrality measures can be broadly applied, and will be of interest to both theorists and practitioners alike.