论文标题
通过非背带特征值的节点免疫
Node Immunization with Non-backtracking Eigenvalues
论文作者
论文摘要
非折线矩阵及其特征值在网络科学和图形挖掘中具有许多应用，例如节点和边缘中心，社区检测，长度光谱论，图形距离以及流行病和渗透阈值。此外，在网络流行病学中，非折线矩阵的最大特征值的倒数是某些网络动力学流行阈值的良好近似值。在这项工作中，我们开发的技术可以确定哪些节点对领先的非背心特征值具有最大影响。我们通过研究从图中删除节点后非折线矩阵的频谱的行为来做到这一点。通过此分析，我们得出了两种新的中心度度量：X度和X-Non-BackTrackTracking Centrality。我们对从这两种中心度度量得出的有针对性的免疫策略进行了广泛的实验。我们的光谱分析和中心度措施可以广泛采用，理论家和从业者都将引起人们的关注。
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.
