Spectral redemption in clustering sparse networks

Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborová, Pan Zhang

Research output: Contribution to journalArticle

267 Scopus citations

Abstract

Spectral algorithms are classic approaches to clustering and community detection in networks. However, for sparse networks the standard versions of these algorithms are suboptimal, in some cases completely failing to detect communities evenwhen other algorithms such as belief propagation can do so. Here, we present a class of spectral algorithms based on a nonbacktracking walk on the directed edges of the graph. The spectrum of this operator is much betterbehaved than that of the adjacency matrix or other commonly used matrices,maintaining a strong separation between the bulk eigenvalues and the eigenvalues relevant to community structure even in the sparse case. We show that our algorithm is optimal for graphs generated by the stochastic block model, detecting communities all of the way down to the theoretical limit.We also show the spectrum of the nonbacktracking operator for some real-world networks, illustrating its advantages over traditional spectral clustering.

Original languageEnglish (US)
Pages (from-to)20935-20940
Number of pages6
JournalProceedings of the National Academy of Sciences of the United States of America
Volume110
Issue number52
DOIs
StatePublished - Dec 24 2013

All Science Journal Classification (ASJC) codes

  • General

Fingerprint Dive into the research topics of 'Spectral redemption in clustering sparse networks'. Together they form a unique fingerprint.

  • Cite this