nips nips2013 nips2013-196 nips2013-196-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Prem Gopalan, Chong Wang, David Blei
Abstract: We develop a probabilistic approach for accurate network modeling using node popularities within the framework of the mixed-membership stochastic blockmodel (MMSB). Our model integrates two basic properties of nodes in social networks: homophily and preferential connection to popular nodes. We develop a scalable algorithm for posterior inference, based on a novel nonconjugate variant of stochastic variational inference. We evaluate the link prediction accuracy of our algorithm on nine real-world networks with up to 60,000 nodes, and on simulated networks with degree distributions that follow a power law. We demonstrate that the AMP predicts significantly better than the MMSB. 1
[1] L. A. Adamic and N. Glance. The political blogosphere and the 2004 U.S. election: divided they blog. In LinkKDD, LinkKDD ’05, page 3643, New York, NY, USA, 2005. ACM.
[2] E. M. Airoldi, D. M. Blei, S. E. Fienberg, and E. P. Xing. Mixed membership stochastic blockmodels. J. Mach. Learn. Res., 9:1981–2014, June 2008.
[3] S. Amari. Differential geometry of curved exponential Families-Curvatures and information loss. The Annals of Statistics, 10(2):357–385, June 1982.
[4] B. Ball, B. Karrer, and M. E. J. Newman. Efficient and principled method for detecting communities in networks. Physical Review E, 84(3):036103, Sept. 2011.
[5] J. Davis and M. Goadrich. The relationship between precision-recall and ROC curves. In Proceedings of the 23rd international conference on Machine learning, ICML ’06, pages 233–240, New York, NY, USA, 2006. ACM.
[6] S. Fortunato. Community detection in graphs. Physics Reports, 486(35):75–174, Feb. 2010.
[7] T. M. J. Fruchterman and E. M. Reingold. Graph drawing by force-directed placement. Softw. Pract. Exper., 21(11):1129–1164, Nov. 1991.
[8] S. Geisser and W. Eddy. A predictive approach to model selection. Journal of the American Statistical Association, 74:153–160, 1979.
[9] P. K. Gopalan and D. M. Blei. Efficient discovery of overlapping communities in massive networks. Proceedings of the National Academy of Sciences, 110(36):14534–14539, 2013.
[10] P. Hoff, A. Raftery, and M. Handcock. Latent space approaches to social network analysis. Journal of the American Statistical Association, 97(460):1090–1098, 2002.
[11] M. Hoffman, D. M. Blei, C. Wang, and J. Paisley. Stochastic variational inference. Journal of Machine Learning Research, 2013.
[12] H. Jeong, Z. Nda, and A. L. Barabsi. Measuring preferential attachment in evolving networks. EPL (Europhysics Letters), 61(4):567, 2003.
[13] M. I. Jordan, Z. Ghahramani, T. S. Jaakkola, and L. K. Saul. An introduction to variational methods for graphical models. Mach. Learn., 37(2):183–233, Nov. 1999.
[14] B. Karrer and M. E. J. Newman. Stochastic blockmodels and community structure in networks. Phys. Rev. E, 83:016107, Jan 2011.
[15] D. I. Kim, P. Gopalan, D. M. Blei, and E. B. Sudderth. Efficient online inference for bayesian nonparametric relational models. In Neural Information Processing Systems, 2013.
[16] P. N. Krivitsky, M. S. Handcock, A. E. Raftery, and P. D. Hoff. Representing degree distributions, clustering, and homophily in social networks with latent cluster random effects models. Social Networks, 31(3):204–213, July 2009.
[17] A. Lancichinetti and S. Fortunato. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Physical Review E, 80(1):016118, July 2009.
[18] 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.
[19] D. Liben-Nowell and J. Kleinberg. The link prediction problem for social networks. In Proceedings of the twelfth international conference on Information and knowledge management, CIKM ’03, pages 556–559, New York, NY, USA, 2003. ACM.
[20] P. McCullagh and J. A. Nelder. Generalized Linear Models, Second Edition. Chapman and Hall/CRC, 2 edition, Aug. 1989.
[21] M. E. J. Newman. Assortative mixing in networks. Physical Review Letters, 89(20):208701, Oct. 2002.
[22] M. E. J. Newman. Finding community structure in networks using the eigenvectors of matrices. Physical Review E, 74(3):036104, 2006.
[23] K. Nowicki and T. A. B. Snijders. Estimation and prediction for stochastic blockstructures. Journal of the American Statistical Association, 96(455):1077–1087, Sept. 2001.
[24] F. Papadopoulos, M. Kitsak, M. . Serrano, M. Bogu, and D. Krioukov. Popularity versus similarity in growing networks. Nature, 489(7417):537–540, Sept. 2012.
[25] RITA. U.S. Air Carrier Traffic Statistics, Bur. Trans. Stats, 2010.
[26] H. Robbins and S. Monro. A stochastic approximation method. The Annals of Mathematical Statistics, 22(3):400–407, Sept. 1951.
[27] Y. J. Wang and G. Y. Wong. Stochastic blockmodels for directed graphs. Journal of the American Statistical Association, 82(397):8–19, 1987. 9