Français
Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs
Post-edited
Authors : Massoulié, Laurent (Author of the conference)
CIRM (Publisher )
05C50 - Graphs and linear algebra (matrices, eigenvalues, etc.)
05C80 - Random graphs
68T05 - Learning and adaptive systems
91D30 - Social networks
CIRM (Publisher )
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.
MSC Codes : 05C50 - Graphs and linear algebra (matrices, eigenvalues, etc.)
05C80 - Random graphs
68T05 - Learning and adaptive systems
91D30 - Social networks
|
Information on the Video
Film maker : Hennenfent, GuillaumeLanguage : English Available date : 29/01/16 Conference Date : 06/01/16 Subseries : Research talks arXiv category : Probability Mathematical Area(s) : Combinatorics ; Probability & Statistics ; Computer Science Format : MP4 (.mp4) - HD Video Time : 00:57:41 Targeted Audience : Researchers Download : https://videos.cirm-math.fr/2016-01-06_Massoulie.mp4 
|
Information on the Event
Event Title : Spectrum of random graphs / Spectre de graphes aléatoiresEvent Organizers : Bordenave, Charles ; Guionnet, Alice ; Virág, Bálint Dates : 04/01/16 - 08/01/16 Event Year : 2016 Event URL : http://conferences.cirm-math.fr/1186.html
Citation Data
DOI : 10.24350/CIRM.V.18912103Cite this video as: Massoulié, Laurent (2016). Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.18912103 URI : http://dx.doi.org/10.24350/CIRM.V.18912103 |
See Also
- [Multi angle] Random walk on random digraph / Author of the conference Salez, Justin.
- [Multi angle] Anchored expansion in the hyperbolic Poisson Voronoi tessellation / Author of the conference Paquette, Elliot.
- [Multi angle] Spectral measures of factor of i.i.d. processes on the regular tree / Author of the conference Backhausz, Agnes.
- [Multi angle] Random irregular graphs are nearly Ramanujan / Author of the conference Puder, Doron.
Bibliography
- Bordenave, C., Lelarge, M., & Massoulié, L. (2015). Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs.
- Decelle, A., Krzakala, F., Moore, C., & Zdeborová, L. (2011). Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Physical Review E, 84(6), 066106 - http://dx.doi.org/10.1103/PhysRevE.84.066106
- Massoulié, L. (2014). Community detection thresholds and the weak Ramanujan property. Proceedings of the 46th annual ACM symposium on theory of computing (pp. 694-703). New York, NY: Association for Computing Machinery. (STOC '14) - http://dx.doi.org/10.1145/2591796.2591857
- Mossel, E., Neeman, J., & Sly, A. (2015). Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields, 162(3-4), 431-461.
