FoCM 2014 conference

Workshop B6 - Random Matrices - Semi-plenary talk

December 16, 15:35 ~ 16:25 - Room B22

Non-backtracking spectrum of random graphs

Charles Bordenave

University of Toulouse & CNRS, France   -

The non-backtracking matrix of a graph is a non-symmetric matrix on the oriented edge of a graph which has interesting algebraic properties and appears notably in connection with the Ihara zeta function and in some generalizations of Ramanujan graphs. It has also been used recently in the context of community detection. In this talk, we will study the largest eigenvalues of this matrix for the Erdos-Renyi graph G(n,c/n) and for simple inhomogeneous random graphs (stochastic block model).

Joint work with Marc Lelarge (INRIA) and Laurent Massoulié (Microsoft & INRIA)..

View abstract PDF