Localized eigenvectors of the non-backtracking matrix

Abstract

In the case of graph partitioning, the emergence of localized eigenvectors can cause the standard spectral method to fail. To overcome this problem, the spectral method using a non-backtracking matrix was proposed. Based on numerical experiments on several examples of real networks, it is clear that the non-backtracking matrix does not exhibit localization of eigenvectors. However, we show that localized eigenvectors of the non-backtracking matrix can exist outside the spectral band, which may lead to deterioration in the performance of graph partitioning.

11 pages, 5 figures, to be published from JSTAT

References in corpus (3)

• Signed Networks in Social Media
• Predicting Positive and Negative Links in Online Social Networks
• Localization on low-order eigenvectors of data matrices