Universiteit Leiden

nl en


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

  • Leo Torres (Max Plank Institute, Leipzig)
vrijdag 25 februari 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.

Deze website maakt gebruik van cookies.  Meer informatie.