Universiteit Leiden

nl en


LCN2 Seminar: Graph homotopy, non-backtracking matrix, and X-centrality

  • Leo Torres (Max Plank Institute, Leipzig)
Friday 25 February 2022
Room 176

You can attend via Zoom.

Zoom link

51th LCN2 seminar

Speaker: Leo Torres (Max Plank Institute, Leipzig) 

Title: Graph homotopy, non-backtracking matrix, and X-centrality.


The non-backtracking matrix and its eigenvalues have many applications in network science and graph mining. For example, 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, first we establish relationships between homotopy of graphs and non-backtracking walks, and develop a measure of graph distance based on this connection. Then 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, which can be thought of as immunizing a node against the spread of disease. From this analysis we derive a centrality measure which we call X-centrality, which is then used to predict which nodes have a large influence in the epidemic threshold. Finally, we discuss work currently in progress on connections with eigenvector localization and percolation theory.

This website uses cookies.  More information.