nips nips2013 nips2013-47 nips2013-47-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Charles Blundell, Yee Whye Teh
Abstract: We propose an efficient Bayesian nonparametric model for discovering hierarchical community structure in social networks. Our model is a tree-structured mixture of potentially exponentially many stochastic blockmodels. We describe a family of greedy agglomerative model selection algorithms that take just one pass through the data to learn a fully probabilistic, hierarchical community model. In the worst case, Our algorithms scale quadratically in the number of vertices of the network, but independent of the number of nested communities. In practice, the run time of our algorithms are two orders of magnitude faster than the Infinite Relational Model, achieving comparable or better accuracy. 1
[1] P. Holland, K.B. Laskey, and S. Leinhardt. Stochastic blockmodels: Some first steps. Social Networks, 5:109137, 1983.
[2] Edoardo M. Airoldi, David M. Blei, Stephen E. Fienberg, and Eric P. Xing. Mixed membership stochastic blockmodel. Journal of Machine Learning Research, 9:1981–2014, 2008.
[3] M. Girvan and M. E. J. Newman. Community structure in social and biological networks. PNAS, 99:7821–7826, 2002.
[4] A. Clauset, M. E. J. Newman, and C. Moore. Finding community structure in very large networks. Physics Review E, 70, 2004.
[5] Charles Kemp, Joshua B. Tenenbaum, Thomas L. Griffiths, Takeshi Yamada, and Naonori Ueda. Learning systems of concepts with an infinite relational model. AAAI, 2006.
[6] Zhao Xu, Volker Tresp, Kai Yu, and Hans-Peter Kriegel. Infinite hidden relational models. Uncertainty in Artificial Intelligence (UAI), 2006.
[7] Morten Mørup and Mikkel N. Schmidt. Bayesian community detection. Neural Computation, 24:2434–2456, 2012.
[8] T. Herlau, M. Mørup, M. N. Schmidt, and L. K. Hansen. Detecting hierarchical structure in networks. In Cognitive Information Processing, 2012.
[9] Phaedon-Stelios Koutsourelakis and Tina Eliassi-Rad. Finding mixed-memberships in social networks. 2008 AAAI Spring Symposium on Social Information Processing (AAAI-SS’08), 2008.
[10] Konstantina Palla, David A. Knowles, and Zoubin Ghahramani. An infinite latent attribute model for network data. In Proceedings of the 29th International Conference on Machine Learning, ICML 2012. July 2012.
[11] Qirong Ho, Ankur P. Parikh, Le Song, and Erix P. Xing. Multiscale community blockmodel for network exploration. Proceedings of the Fourteenth International Workshop on Artificial Intelligence and Statistics (AISTATS), 2011.
[12] D. M. Roy and Y. W. Teh. The Mondrian process. In Advances in Neural Information Processing Systems, volume 21, 2009.
[13] K. A. Heller and Z. Ghahramani. Bayesian hierarchical clustering. In Proceedings of the International Conference on Machine Learning, volume 22, 2005.
[14] C. Blundell, Y. Teh, and K. A. Heller. Bayesian Rose trees. UAI, 2010.
[15] T. Snijders and K. Nowicki. Estimation and prediction for stochastic blockmodels for graphs with latent block structure. Journal of Classification, 14:75–100, 1997.
[16] Jake M. Hofman and Chris H. Wiggins. Bayesian approach to network modularity. Physical Review Letters, 100(25):258701, 2008.
[17] S. F. Sampson. A novitiate in a period of change. an experimental and case study of social relationships. 1968.
[18] Kurt T. Miller, Thomas L. Griffiths, and Michael I. Jordan. Nonparametric latent feature models for link prediction. Neural Information Processing Systems (NIPS), 2009.
[19] A. Globerson, G. Chechik, F. Pereira, and N. Tishby. Euclidean embedding of co-occurrence data. Journal of Machine Learning Research, 8:2265–2295, 2007.
[20] Charles Kemp. Infinite relational model implementation. http://www.psy.cmu.edu/ ˜ckemp/code/irm.html. Accessed: 2013-04-08.
[21] Q. Ho, J. Yin, and E. P. Xing. On triangular versus edge representations — towards scalable modeling of networks. Neural Information Processing Systems (NIPS), 2012. 9