English
Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs
Post-edited
Auteurs : Massoulié, Laurent (Auteur de la Conférence)
CIRM (Editeur )
05C50 - Graphs and linear algebra (matrices, eigenvalues, etc.)
05C80 - Random graphs
68T05 - Learning and adaptive systems
91D30 - Social networks
CIRM (Editeur )
Résumé :
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.
Codes MSC : 05C50 - Graphs and linear algebra (matrices, eigenvalues, etc.)
05C80 - Random graphs
68T05 - Learning and adaptive systems
91D30 - Social networks
|
Informations sur la Vidéo
Réalisateur : Hennenfent, GuillaumeLangue : Anglais Date de publication : 29/01/16 Date de captation : 06/01/16 Sous collection : Research talks arXiv category : Probability Domaine : Combinatorics ; Probability & Statistics ; Computer Science Format : MP4 (.mp4) - HD Durée : 00:57:41 Audience : Researchers Download : https://videos.cirm-math.fr/2016-01-06_Massoulie.mp4 
|
Informations sur la Rencontre
Nom de la rencontre : Spectrum of random graphs / Spectre de graphes aléatoiresOrganisateurs de la rencontre : Bordenave, Charles ; Guionnet, Alice ; Virág, Bálint Dates : 04/01/16 - 08/01/16 Année de la rencontre : 2016 URL Congrès : http://conferences.cirm-math.fr/1186.html
Données de citation
DOI : 10.24350/CIRM.V.18912103Citer cette vidéo: 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 |
Voir aussi
- [Multi angle] Random walk on random digraph / Auteur de la Conférence Salez, Justin.
- [Multi angle] Anchored expansion in the hyperbolic Poisson Voronoi tessellation / Auteur de la Conférence Paquette, Elliot.
- [Multi angle] Spectral measures of factor of i.i.d. processes on the regular tree / Auteur de la Conférence Backhausz, Agnes.
- [Multi angle] Random irregular graphs are nearly Ramanujan / Auteur de la Conférence Puder, Doron.
Bibliographie
- 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.
