m
• E

F Nous contacter

0

Multi angle

H 1 Overlapping community detection by spectral methods

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

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éesOrganisateurs de la rencontre : Pouet, Christophe ; Reiss, Markus ; Rigollet, PhilippeDates : 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

Bibliographie

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

0
Z