Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs. (English) Zbl 1386.05174
Summary: A nonbacktracking walk on a graph is a directed path such that no edge is the inverse of its preceding edge. The nonbacktracking matrix of a graph is indexed by its directed edges and can be used to count nonbacktracking walks of a given length. It has been used recently in the context of community detection and has appeared previously in connection with the Ihara zeta function and in some generalizations of Ramanujan graphs. In this work, we study the largest eigenvalues of the nonbacktracking matrix of the Erdős-Rényi random graph and of the stochastic block model in the regime where the number of edges is proportional to the number of vertices. Our results confirm the “spectral redemption conjecture” in the symmetric case and show that community detection can be made on the basis of the leading eigenvectors above the feasibility threshold.
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C20 | Directed graphs (digraphs), tournaments |
| 60B20 | Random matrices (probabilistic aspects) |
| 62M15 | Inference from stochastic processes and spectral analysis |
| 60J85 | Applications of branching processes |
| 15B52 | Random matrices (algebraic aspects) |
References:
| [1] | Angel, O., Friedman, J. and Hoory, S. (2015). The non-backtracking spectrum of the universal cover of a graph. Trans. Amer. Math. Soc.367 4287-4318. · Zbl 1310.05136 |
| [2] | Barbour, A. D. and Chen, L. H. Y., eds. (2005). An Introduction to Stein’s Method. Lecture Notes Series. Institute for Mathematical Sciences. National Univ. Singapore 4. Singapore Univ. Press, Singapore. · Zbl 1072.62007 |
| [3] | Benjamini, I. and Schramm, O. (2001). Recurrence of distributional limits of finite planar graphs. Electron. J. Probab.6 no. 23, 13 pp. (electronic). · Zbl 1010.82021 |
| [4] | Bhatia, R. (1997). Matrix Analysis. Graduate Texts in Mathematics 169. Springer, New York. · Zbl 0863.15001 |
| [5] | Bollobás, B., Janson, S. and Riordan, O. (2007). The phase transition in inhomogeneous random graphs. Random Structures Algorithms 31 3-122. · Zbl 1123.05083 |
| [6] | Bordenave, C. (2015). A new proof of Friedman’s second eigenvalue theorem and its extension to random lifts. Preprint. Available at arXiv:1502.04482. · Zbl 1462.05324 |
| [7] | Chung, F. R. K. (1989). Diameters and eigenvalues. J. Amer. Math. Soc.2 187-196. · Zbl 0678.05037 |
| [8] | Decelle, A., Krzakala, F., Moore, C. and Zdeborová, L. (2011). Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Phys. Rev. E (3) 84 066106. |
| [9] | Friedman, J. (2008). A proof of Alon’s second eigenvalue conjecture and related problems. Mem. Amer. Math. Soc.195 viii \(+100\). · Zbl 1177.05070 · doi:10.1090/memo/0910 |
| [10] | Friedman, J. and Kohler, D.-E. (2014). The relativized second eigenvalue conjecture of Alon. Preprint. Available at arXiv:1403.3462. |
| [11] | Füredi, Z. and Komlós, J. (1981). The eigenvalues of random symmetric matrices. Combinatorica 1 233-241. · Zbl 0494.15010 |
| [12] | Hashimoto, K. (1989). Zeta functions of finite graphs and representations of \(p\)-adic groups. In Automorphic Forms and Geometry of Arithmetic Varieties. Adv. Stud. Pure Math.15 211-280. Academic Press, Boston, MA. · Zbl 0688.00008 |
| [13] | Holland, P. W., Laskey, K. B. and Leinhardt, S. (1983). Stochastic blockmodels: First steps. Soc. Netw.5 109-137. |
| [14] | Hoory, S., Linial, N. and Wigderson, A. (2006). Expander graphs and their applications. Bull. Amer. Math. Soc. (N.S.) 43 439-561 (electronic). · Zbl 1147.68608 |
| [15] | Horn, R. A. and Johnson, C. R. (1991). Topics in Matrix Analysis. Cambridge Univ. Press, Cambridge. · Zbl 0729.15001 |
| [16] | Horton, M. D., Stark, H. M. and Terras, A. A. (2006). What are zeta functions of graphs and what are they good for? In Quantum Graphs and Their Applications. Contemp. Math.415 173-189. Amer. Math. Soc., Providence, RI. · Zbl 1222.11109 |
| [17] | Kesten, H. and Stigum, B. P. (1966). Additional limit theorems for indecomposable multidimensional Galton-Watson processes. Ann. Math. Stat.37 1463-1481. · Zbl 0203.17402 |
| [18] | Kesten, H. and Stigum, B. P. (1966). A limit theorem for multidimensional Galton-Watson processes. Ann. Math. Stat.37 1211-1223. · Zbl 0203.17401 |
| [19] | Kotani, M. and Sunada, T. (2000). Zeta functions of finite graphs. J. Math. Sci. Univ. Tokyo 7 7-25. · Zbl 0978.05051 |
| [20] | Krzakala, F., Moore, C., Mossel, E., Neeman, J., Sly, A., Zdeborová, L. and Zhang, P. (2013). Spectral redemption in clustering sparse networks. Proc. Natl. Acad. Sci. USA 110 20935-20940. · Zbl 1359.62252 · doi:10.1073/pnas.1312486110 |
| [21] | Lubotzky, A. (1995). Cayley graphs: Eigenvalues, expanders and random walks. In Surveys in Combinatorics, 1995 (Stirling). London Mathematical Society Lecture Note Series 218 155-189. Cambridge Univ. Press, Cambridge. · Zbl 0835.05033 |
| [22] | Lubotzky, A., Phillips, R. and Sarnak, P. (1988). Ramanujan graphs. Combinatorica 8 261-277. · Zbl 0661.05035 · doi:10.1007/BF02126799 |
| [23] | Massoulié, L. (2014). Community detection thresholds and the weak Ramanujan property. In STOC’14—Proceedings of the 2014 ACM Symposium on Theory of Computing 694-703. ACM, New York. · Zbl 1315.68210 |
| [24] | Mossel, E., Neeman, J. and Sly, A. (2013). A proof of the block model threshold conjecture. Preprint. Available at arXiv:1311.4115v2. · Zbl 1424.05272 |
| [25] | Mossel, E., Neeman, J. and Sly, A. (2015). Reconstruction and estimation in the planted partition model. Probab. Theory Related Fields 162 431-461. · Zbl 1320.05113 |
| [26] | Murty, M. R. (2003). Ramanujan graphs. J. Ramanujan Math. Soc.18 33-52. · Zbl 1038.05038 |
| [27] | Nilli, A. (1991). On the second eigenvalue of a graph. Discrete Math.91 207-210. · Zbl 0771.05064 |
| [28] | Shi, X. and Wei, Y. (2012). A sharp version of Bauer-Fike’s theorem. J. Comput. Appl. Math.236 3218-3227. · Zbl 1247.15017 |
| [29] | Sunada, T. (1988). Fundamental groups and Laplacians. In Geometry and Analysis on Manifolds (Katata/Kyoto, 1987). Lecture Notes in Math.1339 248-277. Springer, Berlin. · Zbl 0815.58024 |
| [30] | Terras, A. |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
