Back to Search
Start Over
Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs
- Source :
- Annals of Probability, Annals of Probability, 2014, pp.abs/1501.06087, FOCS, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, Oct 2015, Berkeley, United States. ⟨10.1109/FOCS.2015.86⟩, Annals of Probability, Institute of Mathematical Statistics, 2014, pp.abs/1501.06087
- Publication Year :
- 2014
- Publisher :
- HAL CCSD, 2014.
-
Abstract
- A non-backtracking walk on a graph is a directed path such that no edge is the inverse of its preceding edge. The non-backtracking matrix of a graph is indexed by its directed edges and can be used to count non-backtracking 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 non-backtracking matrix of the Erdos-Renyi 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 that community detection can be made on the basis of the leading eigenvectors above the feasibility threshold.<br />Comment: 59 pages
- Subjects :
- Social and Information Networks (cs.SI)
FOS: Computer and information sciences
Random graph
Discrete mathematics
Block graph
Probability (math.PR)
Computer Science - Social and Information Networks
Ihara zeta function
05C80, 05C50, 91D30
law.invention
Combinatorics
[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI]
Indifference graph
Pathwidth
Chordal graph
law
Line graph
Random regular graph
FOS: Mathematics
Ramanujan graphs
[INFO]Computer Science [cs]
Stochastic Block Model
Mathematics - Probability
non-backtracking matrix
Mathematics
Subjects
Details
- Language :
- English
- ISSN :
- 00911798 and 2168894X
- Database :
- OpenAIRE
- Journal :
- Annals of Probability, Annals of Probability, 2014, pp.abs/1501.06087, FOCS, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, Oct 2015, Berkeley, United States. ⟨10.1109/FOCS.2015.86⟩, Annals of Probability, Institute of Mathematical Statistics, 2014, pp.abs/1501.06087
- Accession number :
- edsair.doi.dedup.....0f22955c42c341a8a67fbad3f2d5fa88