Localized eigenvectors of the non-backtracking matrix

DOI10.1088/1742-5468/2016/02/023404MaRDI QIDQ3302540zbMATH OpenOpenAlexFDO

Authors T. Kawamoto

Publication date 11 August 2020

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.07543

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10)

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.

Recommendations

• Some spectral properties of the non-backtracking matrix of a graph
• Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
• Non-backtracking spectrum of degree-corrected stochastic block models
• Non-backtracking spectra of weighted inhomogeneous random graphs
• scientific article; zbMATH DE number 6276186

Cites work

• Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters
• Dynamical TAP approach to mean field glassy systems
• First eigenvalue/eigenvector in sparse random symmetric matrices: influences of degree fluctuation
• On the spectrum of the normalized graph Laplacian
• Sparse random matrices: the eigenvalue spectrum revisited
• Spectral redemption in clustering sparse networks

Cited in

(14)

• On the exponential generating function for non-backtracking walks
• Non-backtracking PageRank
• Ranking in evolving complex networks
• Targeted influence maximization in complex networks
• Identifying influential spreaders in complex networks through local effective spreading paths
• A Theory for Backtrack-Downweighted Walks
• Non-backtracking alternating walks
• Eigenvector-based centrality measures for temporal networks
• Fragmenting complex network based on non-backtracking matrix
• An algorithm for identifying eigenvectors exhibiting strong spatial localization
• Hitting times for second-order random walks
• Two accelerated non-backtracking PageRank algorithms for large-scale networks
• On the initial value of PageRank
• Stationary distribution of node2vec random walks on household models

Describes a project that uses

Uses Software

• SNAP

This page was built for publication: Localized eigenvectors of the non-backtracking matrix

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3302540)