nips nips2012 nips2012-298 nips2012-298-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Prem Gopalan, Sean Gerrish, Michael Freedman, David M. Blei, David M. Mimno
Abstract: We develop a scalable algorithm for posterior inference of overlapping communities in large networks. Our algorithm is based on stochastic variational inference in the mixed-membership stochastic blockmodel (MMSB). It naturally interleaves subsampling the network with estimating its community structure. We apply our algorithm on ten large, real-world networks with up to 60,000 nodes. It converges several orders of magnitude faster than the state-of-the-art algorithm for MMSB, finds hundreds of communities in large real-world networks, and detects the true communities in 280 benchmark networks with equal or better accuracy compared to other scalable algorithms. 1
[1] Santo Fortunato. Community detection in graphs. Physics Reports, 486(35):75–174, 2010.
[2] E. Airoldi, D. Blei, S. Fienberg, and E. Xing. Mixed membership stochastic blockmodels. Journal of Machine Learning Research, 9:1981–2014, 2008.
[3] Brian Ball, Brian Karrer, and M. E. J. Newman. Efficient and principled method for detecting communities in networks. Physical Review E, 84(3):036103, 2011.
[4] M. E. J. Newman and M. Girvan. Finding and evaluating community structure in networks. Physical Review E, 69(2):026113, 2004.
[5] K. Nowicki and T. Snijders. Estimation and prediction for stochastic blockstructures. Journal of the American Statistical Association, 96(455):1077–1087, 2001.
[6] Peter J. Bickel and Aiyou Chen. A nonparametric view of network models and Newman-Girvan and other modularities. Proceedings of the National Academy of Sciences, 106(50):21068–21073, 2009.
[7] Imre Dernyi, Gergely Palla, and Tams Vicsek. Clique percolation in random networks. Physical Review Letters, 94(16):160202, 2005.
[8] Yong-Yeol Ahn, James P. Bagrow, and Sune Lehmann. Link communities reveal multiscale complexity in networks. Nature, 466(7307):761–764, 2010.
[9] M. E. J. Newman and E. A. Leicht. Mixture models and exploratory analysis in networks. Proceedings of the National Academy of Sciences, 104(23):9564–9569, 2007.
[10] A. Goldenberg, A. Zheng, S. Fienberg, and E. Airoldi. A survey of statistical network models. Foundations and Trends in Machine Learning, 2:129–233, 2010.
[11] W. Fu, L. Song, and E. Xing. Dynamic mixed membership blockmodel for evolving networks. In ICML, 2009.
[12] Qirong Ho, Ankur P. Parikh, and Eric P. Xing. A multiscale community blockmodel for network exploration. Journal of the American Statistical Association, 107(499):916–934, 2012.
[13] H. Robbins and S. Monro. A stochastic approximation method. The Annals of Mathematical Statistics, 22(3):400–407, 1951.
[14] M. Hoffman, D. Blei, C. Wang, and J. Paisley. Stochastic variational inference. arXiv:1206.7051, 2012.
[15] M. Hoffman, D. Blei, and F. Bach. Online learning for latent Dirichlet allocation. In NIPS, 2010.
[16] M. E. J. Newman. Finding community structure in networks using the eigenvectors of matrices. Physical Review E, 74(3):036104, 2006.
[17] Tams Nepusz, Andrea Petrczi, Lszl Ngyessy, and Flp Bazs. Fuzzy communities and the concept of bridgeness in complex networks. Physical Review E, 77(1):016107, 2008.
[18] M. Jordan, Z. Ghahramani, T. Jaakkola, and L. Saul. Introduction to variational methods for graphical models. Machine Learning, 37:183–233, 1999.
[19] S. Amari. Differential geometry of curved exponential families-curvatures and information loss. The Annals of Statistics, 1982.
[20] M. Morup, M.N. Schmidt, and L.K. Hansen. Infinite multiple membership relational modeling for complex networks. In IEEE MLSP, 2011.
[21] M. Kim and J. Leskovec. Modeling social networks with node attributes using the multiplicative attribute graph model. In UAI, 2011.
[22] RITA. U.S. Air Carrier Traffic Statistics, Bur. Trans. Stats, 2010.
[23] J. Leskovec, J. Kleinberg, and C. Faloutsos. Graph evolution: Densification and shrinking diameters. ACM TKDD, 2007.
[24] J. Gehrke, P. Ginsparg, and J. M. Kleinberg. Overview of the 2003 KDD cup. SIGKDD Explorations, 5:149–151, 2003.
[25] B. Klimmt and Y. Yang. Introducing the Enron corpus. In CEAS, 2004.
[26] M. E. J. Newman. The structure of scientific collaboration networks. Proceedings of the National Academy of Sciences, 98(2):404–409, 2001.
[27] J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahone. Community structure in large networks: Natural cluster sizes and the absence of large well-defined cluster. In Internet Mathematics, 2008.
[28] Andrea Lancichinetti and Santo Fortunato. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Physical Review E, 80(1):016118, 2009. 9