m
F x |
L
     
Post-edited

H 2 Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs

Auteurs : Massoulié, Laurent (Auteur de la Conférence)
CIRM (Editeur )

Loading the player...
introducing Ramanujan graphs proof by Mohar of Alon-Boppana theorem non-backtracking matrices of graphs stochastic block model and community detection characterising non back-tracking spectrum of random graphs proof of the spectral redemption conjecture Erdos-Rényi graphs are nearly Ramanujan proof elements 1: local analysis of random graphs proof elements 2 : negligible perturbations via matrix expansion open problems on community detection in stochastic block models questions of the audience
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

    Langue : Anglais
    Date de publication : 29/01/16
    Date de captation : 06/01/16
    Collection : Research talks ; Combinatorics ; Computer Science ; Probability and Statistics
    Format : MP4 (.mp4) - HD
    Durée : 00:57:41
    Domaine : Combinatorics ; Probability & Statistics ; Computer Science
    Audience : Chercheurs ; Doctorants , Post - Doctorants
    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éatoires
Organisateurs 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

Citation Data

DOI : 10.24350/CIRM.V.18912103
Cite 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

Voir aussi

Bibliographie

  • Bordenave, C., Lelarge, M., & Massoulié, L. (2015). Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs. - http://arxiv.org/abs/1501.06087

  • 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. - http://dx.doi.org/10.1007/s00440-014-0576-6


Titres de périodiques et e-books électroniques (Depuis le CIRM)

Ressources Electroniques

Books & Print journals

Recherche avancée

0
Z