Overlapping community detection by spectral methods | Vidéo | Carmin.tv

00:00:00 / 00:00:00

Overlapping community detection by spectral methods

By Elizaveta Levina

Appears in collection : Meeting in mathematical statistics: new procedures for new data / Rencontre de statistiques mathématiques : nouvelles procédures pour de nouvelles données

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

Information about the video

Date of recording 16/12/2014
Date of publication 08/01/2015
Institution CIRM
Licence CC BY NC ND
Language English
Audience Researchers
Director(s) Guillaume Hennenfent
Format MP4

Citation data

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

Domain(s)

Bibliography

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
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
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
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
Cai, T. & Li, X. (2014). Robust and Computationally feasible community detection in the presence of arbitrary outlier nodes. <arXiv:1404.6000> - http://arxiv.org/abs/1404.6000
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
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
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
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
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
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
Sarkar, P., & Bickel, P.J. (2013). Role of normalization in spectral clustering for stochastic blockmodels. <arXiv:1310.1495> - http://arxiv.org/abs/1310.1495
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
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
Zhang, Y., Levina, E., & Zhu, J. (2014). Detecting overlapping communities in networks with spectral methods. <arXiv:1412.3432> - http://arxiv.org/abs/1412.3432

MSC codes

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow

Copyright Carmin.tv 2024

Give feedback