Journal
ANNALS OF PROBABILITY
Volume 46, Issue 1, Pages 1-71Publisher
INST MATHEMATICAL STATISTICS
DOI: 10.1214/16-AOP1142
Keywords
Random graphs; nonbacktracking matrix; spectral gap; community detection
Categories
Ask authors/readers for more resources
A nonbacktracking walk on a graph is a directed path such that no edge is the inverse of its preceding edge. The nonbacktracking matrix of a graph is indexed by its directed edges and can be used to count nonbacktracking walks of a given length. It has been used recently in the context of community detection and has appeared previously in connection with the Ihara zeta function and in some generalizations of Ramanujan graphs. In this work, we study the largest eigenvalues of the nonbacktracking matrix of the Erdos-Renyi random graph and of the stochastic block model in the regime where the number of edges is proportional to the number of vertices. Our results confirm the spectral redemption conjecture in the symmetric case and show that community detection can be made on the basis of the leading eigenvectors above the feasibility threshold.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available