Nonbacktracking Eigenvalues under Node Removal: X-Centrality and Targeted Immunization
Nonbacktracking Eigenvalues under Node Removal: X-Centrality and Targeted Immunization
复制标题
DOI：
10.1137/20m1352132
复制
发表时间：
2021-01
期刊：
影响因子：
--
通讯作者：
Leonardo A. B. Tôrres;Kevin S. Chan;Hanghang Tong;T. Eliassi-Rad
中科院分区：
文献类型：
--
作者：
Leonardo A. B. Tôrres;Kevin S. Chan;Hanghang Tong;T. Eliassi-Rad
． 非回溯矩阵及其特征值在网络科学和5图挖掘中有许多应用，如节点和边缘中心性、社区检测、长度谱理论、6图距离、流行和渗透阈值。在网络流行病学中，非回溯矩阵的最大特征值的倒数7是对某些网络动力学的流行阈值的一个很好的逼近。在这项工作中，我们开发了识别哪9个节点对这个主要特征值影响最大的技术。我们通过研究从图中删除一个节点后非回溯矩阵谱的行为来做到这一点。从这个分析中，我们得到了两个新的中心性度量：X度中心性和X非回溯中心性。我们对基于这两种中心性措施的靶向免疫策略进行了广泛的实验。我们的光谱分析和中心性测量可以广泛应用，并将引起理论家和实践者的兴趣。二次特征值问题的摄动，并应用于随机块的NB-特征值
. The non-backtracking matrix and its eigenvalues have many applications in network science and 5 graph mining, such as node and edge centrality, community detection, length spectrum theory, 6 graph distance, and epidemic and percolation thresholds. In network epidemiology, the reciprocal 7 of the largest eigenvalue of the non-backtracking matrix is a good approximation for the epidemic 8 threshold of certain network dynamics. In this work, we develop techniques that identify which 9 nodes have the largest impact on this leading eigenvalue. We do so by studying the behavior of 10 the spectrum of the non-backtracking matrix after a node is removed from the graph. From this 11 analysis we derive two new centrality measures: X -degree and X-non-backtracking centrality . We 12 perform extensive experimentation with targeted immunization strategies derived from these two 13 centrality measures. Our spectral analysis and centrality measures can be broadly applied, and will 14 be of interest to both theorists and practitioners alike. the perturbation of quadratic eigenvalue problems, with applications to the NB- eigenvalues of the stochastic block