Community detection with the non-backtracking operator

-
Marc LeLarge , ENS - France

Community detection consists in identification of groups of similar items within a population. In the context of online social networks, it is a useful primitive for recommending either contacts or news items to users. We will consider a particular generative probabilistic model for the observations, namely the so-called stochastic block model and prove that the non-backtracking operator provides a significant improvement when used for spectral clustering.  joint work with C. Bordenave and L. Massoulie.