Multi angle

H 1 Overlapping community detection by spectral methods

Auteurs : Levina, Elizaveta (Auteur de la Conférence)
CIRM (Editeur )

    Loading the player...

    Résumé : Community detection is a fundamental problem in network analysis which is made more challenging by overlaps between communities which often occur in practice. Here we propose a general, flexible, and interpretable generative model for overlapping communities, which can be thought of as a generalization of the degree-corrected stochastic block model. We develop an efficient spectral algorithm for estimating the community memberships, which deals with the overlaps by employing the $K$-medians algorithm rather than the usual $K$-means for clustering in the spectral domain. We show that the algorithm is asymptotically consistent when networks are not too sparse and the overlaps between communities not too large. Numerical experiments on both simulated networks and many real social networks demonstrate that our method performs very well compared to a number of benchmark methods for overlapping community detection. This is joint work with Yuan Zhang and Ji Zhu.

    community detection - networks - pseudo-likelihood

    Codes MSC :
    62G20 - Nonparametric asymptotic efficiency
    62H30 - Classification and discrimination; cluster analysis
    65C60 - Computational problems in statistics

      Informations sur la Vidéo

      Langue : Anglais
      Date de publication : 08/01/15
      Date de captation : 16/12/14
      Collection : Research talks ; Computer Science ; Probability and Statistics
      Format : quicktime ; audio/x-aac
      Durée : 00:28:53
      Domaine : Computer Science ; Probability & Statistics
      Audience : Chercheurs ; Doctorants , Post - Doctorants
      Download : https://videos.cirm-math.fr/2014-12-16_Levina.mp4

    Informations sur la rencontre

    Nom de la rencontre : Meeting in mathematical statistics: new procedures for new data / Rencontre de statistiques mathématiques : nouvelles procédures pour de nouvelles données
    Organisateurs de la rencontre : Pouet, Christophe ; Reiss, Markus ; Rigollet, Philippe
    Dates : 15/12/14 - 19/12/14
    Année de la rencontre : 2014

    Citation Data

    DOI : 10.24350/CIRM.V.18659703
    Cite this video as: Levina, Elizaveta (2014). Overlapping community detection by spectral methods. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.18659703
    URI : http://dx.doi.org/10.24350/CIRM.V.18659703


    1. Amini, A.A., Chen, A., Bickel, P.J., & Levina, E. (2013). Pseudo-likelihood methods for community detection in large sparse networks. The Annals of Statistics, 41(4),2097-2122 - http://dx.doi.org/10.1214/13-aos1138

    2. Airoldi, E.M., Blei, D.M., Fienberg, S.E., & Xing, E.P. (2008). Mixed membership stochastic blockmodels. Journal of Machine Learning Research, 9, 1981-2014 - http://www.jmlr.org/papers/v9/airoldi08a.html

    3. Ball, B., Karrer, B., and Newman, M.E.J. (2011). An efficient and principled method for detecting communities in networks. Physical Review E, 84(3), 036103 - http://dx.doi.org/10.1103/physreve.84.036103

    4. Bickel, P.J. & Chen, A. (2009). A nonparametric view of network models and Newman-Girvan and other modularities. Proceedings of the National Academy of Sciences of the United States of America, 106(50), 21068-21073 - http://dx.doi.org/10.1073/pnas.0907096106

    5. Cai, T. & Li, X. (2014). Robust and Computationally feasible community detection in the presence of arbitrary outlier nodes. - http://arxiv.org/abs/1404.6000

    6. Chaudhuri, K., Chung, F., & Tsiatas, A. (2012). Spectral clustering of graphs with general degrees in the extended planted partition model. JMLR Workshop and Conference Proceedings, 23, 35.1 - 35.23 - http://jmlr.csail.mit.edu/proceedings/papers/v23/chaudhuri12.html

    7. 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

    8. Karrer, B., & Newman, M.E.J. (2011). Stochastic blockmodels and community structure in networks. Physical Review E, 83(1), 016107 - http://dx.doi.org/10.1103/PhysRevE.83.016107

    9. McAuley, J., & Leskovec, J. (2012). Learning to discover social circles in ego networks. In F. Pereira, C.J.C. Burges, L. Bottou, & K.Q. Weinberger (Eds.), Advances in Neural Information Processing Systems 25 (pp. 548-556). New-York: Curran Associates - http://papers.nips.cc/paper/4532-learning-to-discover-social-circles-in-ego-networks.pdf

    10. Newman, M.E.J. (2013). Spectral methods for network community detection and graph partitioning. Physical Review E, 88(4), 042822 - http://dx.doi.org/10.1103/PhysRevE.88.042822

    11. Qin, T., & Rohe, K. (2013). Regularized spectral clustering under the degree-corrected stochastic blockmodel. In C.J.C. Burges, L. Bottou, M. Welling, Z. Ghahramani, & K.Q. Weinberger (Eds.), Advances in Neural Information Processing Systems 26 (pp. 3120-3128). New-York: Curran Associates - http://papers.nips.cc/paper/5099-regularized-spectral-clustering-under-the-degree-corrected-stochastic-blockmodel.pdf

    12. Sarkar, P., & Bickel, P.J. (2013). Role of normalization in spectral clustering for stochastic blockmodels. - http://arxiv.org/abs/1310.1495

    13. Wang, F., Li, T., Wang, X., Zhu, S., & Ding, C. (2011). Community discovery using nonnegative matrix factorization. Data Mining and Knowledge Discovery, 22(3), 493–521 - http://dx.doi.org/10.1007/s10618-010-0181-y

    14. Young, S.J., & Scheinerman, E.R. (2007). Random dot product graph models for social networks. In A. Bonato, & F.R.K. Chung (Eds.), Algorithms and models for the web-graph, (pp. 138-149). Berlin: Springer. (Lecture Notes in Computer Science, 4863) - http://dx.doi.org/10.1007/978-3-540-77004-6_11

    15. Zhang, Y., Levina, E., & Zhu, J. (2014). Detecting overlapping communities in networks with spectral methods. - http://arxiv.org/abs/1412.3432

Ressources Electroniques (Depuis le CIRM)

Books & Print journals

Recherche avancée