×

zbMATH — the first resource for mathematics

Spectral redemption in clustering sparse networks. (English) Zbl 1359.62252
Summary: 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 introduce a new class of spectral algorithms based on a non-backtracking 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 the way down to the theoretical limit. We also show the spectrum of the non-backtracking operator for some real-world networks, illustrating its advantages over traditional spectral clustering.

MSC:
62H30 Classification and discrimination; cluster analysis (statistical aspects)
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
90B15 Stochastic network models in operations research
94A13 Detection theory in information and communication theory
94A15 Information theory (general)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] 5 pp 109– (1983)
[2] 82 pp 8– (1987)
[3] 17 pp 395– (2007)
[4] PNAS 106 (50) pp 21068– (2009) · Zbl 1359.62411
[5] COMBIN PROBAB COMPUT 18 pp 881– (2009) · Zbl 1191.05084
[6] COMBIN PROBAB COMPUT 19 pp 227– (2010) · Zbl 1209.05178
[7] Nadakuditi, Physical Review Letters 108 (18) pp 188701– (2012)
[8] Decelle, Physical Review Letters 107 (6) pp 065701– (2011)
[9] Decelle, Physical review. E, Statistical, nonlinear, and soft matter physics 84 (6 Pt 2) pp 066106– (2011)
[10] 12 pp P12021– (2012)
[11] 40 pp 203– (1981) · Zbl 0468.05039
[12] 48 pp 123503– (2007) · Zbl 1153.81436
[13] ADVANCED STUDIES IN PURE MATHEMATICS 15 pp 211– (1989)
[14] COMMUN CONTEMP MATH 9 pp 585– (2007) · Zbl 1140.60301
[15] Ren, IEEE transactions on neural networks / a publication of the IEEE Neural Networks Council 22 (2) pp 233– (2011)
[16] ANN MATH 67 pp 325– (1958) · Zbl 0085.13203
[17] COMBIN PROBAB COMPUT 12 pp 61– (2003)
[18] RANDOM STRUCTURES ALGORITHMS 31 pp 3– (2007) · Zbl 1123.05083
[19] INT J MATH 3 pp 717– (1992) · Zbl 0767.11025
[20] ANN MATH STAT 37 pp 1463– (1966) · Zbl 0203.17402
[21] 13 pp 817– (2003) · Zbl 1050.60082
[22] 33 pp 452– (1977)
[23] Newman, Physical review. E, Statistical, nonlinear, and soft matter physics 74 (3 Pt 2) pp 036104– (2006)
[24] Girvan, PNAS 99 (12) pp 7821– (2002) · Zbl 1032.91716
[25] 54 pp 396– (2003)
[26] Ball, Physical review. E, Statistical, nonlinear, and soft matter physics 84 (3 Pt 2) pp 036103– (2011)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.