Spectral Redemption in Clustering Sparse Networks. Krzakala, F., Moore, C., Mossel, E., Neeman, J., Sly, A., Zdeborová, L., & Zhang, P. 110(52):20935–20940.
Spectral Redemption in Clustering Sparse Networks [pdf]Paper  doi  abstract   bibtex   
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 even when 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 better-behaved 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.
@article{krzakalaSpectralRedemptionClustering2013,
  title = {Spectral Redemption in Clustering Sparse Networks},
  volume = {110},
  issn = {0027-8424, 1091-6490},
  url = {http://www.pnas.org/content/110/52/20935%5Cnhttp://www.ncbi.nlm.nih.gov/pubmed/24277835%5Cnhttp://www.pnas.org/content/110/52/20935.full.pdf},
  doi = {10.1073/pnas.1312486110},
  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 even when 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 better-behaved 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.},
  number = {52},
  journaltitle = {Proceedings of the National Academy of Sciences of the United States of America},
  date = {2013},
  pages = {20935--20940},
  author = {Krzakala, Florent and Moore, Cristopher and Mossel, Elchanan and Neeman, Joe and Sly, Allan and Zdeborová, Lenka and Zhang, Pan},
  file = {/home/dimitri/Nextcloud/Zotero/storage/WFVBRMZ2/Krzakala et al. - 2013 - Spectral redemption in clustering sparse networks.pdf},
  eprinttype = {pmid},
  eprint = {24277835}
}
Downloads: 0