  A non-backtracking walk on a graph is a directed path such that no edge is
the inverse of its preceding edge. The non-backtracking matrix of a graph is
indexed by its directed edges and can be used to count non-backtracking 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 non-backtracking 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 that community detection can be made on the
basis of the leading eigenvectors above the feasibility threshold.
