Lecture
LCN2 Seminar: Graph homotopy, non-backtracking matrix, and X-centrality
- Leo Torres (Max Plank Institute, Leipzig)
- Date
- Friday 25 February 2022
- Time
- Location
- Snellius
- Room
- Room 176
You can attend via Zoom.
Zoom link51th LCN2 seminar
Speaker: Leo Torres (Max Plank Institute, Leipzig)
Title: Graph homotopy, non-backtracking matrix, and X-centrality.
Abstract:
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.
