nips nips2012 nips2012-194 nips2012-194-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Jure Leskovec, Julian J. Mcauley
Abstract: Our personal social networks are big and cluttered, and currently there is no good way to organize them. Social networking sites allow users to manually categorize their friends into social circles (e.g. ‘circles’ on Google+, and ‘lists’ on Facebook and Twitter), however they are laborious to construct and must be updated whenever a user’s network grows. We define a novel machine learning task of identifying users’ social circles. We pose the problem as a node clustering problem on a user’s ego-network, a network of connections between her friends. We develop a model for detecting circles that combines network structure as well as user profile information. For each circle we learn its members and the circle-specific user profile similarity metric. Modeling node membership to multiple circles allows us to detect overlapping as well as hierarchically nested circles. Experiments show that our model accurately identifies circles on a diverse set of data from Facebook, Google+, and Twitter for all of which we obtain hand-labeled ground-truth. 1
[1] Y.-Y. Ahn, J. Bagrow, and S. Lehmann. Link communities reveal multiscale complexity in networks. Nature, 2010.
[2] E. Airoldi, D. Blei, S. Fienberg, and E. Xing. Mixed membership stochastic blockmodels. JMLR, 2008.
[3] R. Balasubramanyan and W. Cohen. Block-LDA: Jointly modeling entity-annotated text and entity-entity links. In SDM, 2011.
[4] E. Boros and P. Hammer. Pseudo-boolean optimization. Discrete Applied Mathematics, 2002.
[5] J. Chang and D. Blei. Relational topic models for document networks. In AIStats, 2009.
[6] J. Chang, J. Boyd-Graber, and D. Blei. Connections between the lines: augmenting social networks with text. In KDD, 2009.
[7] Y. Chen and C. Lin. Combining SVMs with various feature selection strategies. Springer, 2006.
[8] M. Handcock, A. Raftery, and J. Tantrum. Model-based clustering for social networks. Journal of the Royal Statistical Society Series A, 2007.
[9] S. Johnson. Hierarchical clustering schemes. Psychometrika, 1967.
[10] D. Kim, Y. Jo, L.-C. Moon, and A. Oh. Analysis of twitter lists as a potential source for discovering latent characteristics of users. In CHI, 2010.
[11] P. Krivitsky, M. Handcock, A. Raftery, and P. Hoff. Representing degree distributions, clustering, and homophily in social networks with latent cluster random effects models. Social Networks, 2009.
[12] P. Lazarsfeld and R. Merton. Friendship as a social process: A substantive and methodological analysis. In Freedom and Control in Modern Society. 1954.
[13] Y. Liu, A. Niculescu-Mizil, and W. Gryc. Topic-link LDA: joint models of topic and author community. In ICML, 2009.
[14] D. MacKay. Information Theory, Inference and Learning Algorithms. Cambrdige University Press, 2003.
[15] J. McAuley and J. Leskovec. Discovering social circles in ego networks. arXiv:1210.8182, 2012.
[16] M. McPherson. An ecology of affiliation. American Sociological Review, 1983.
[17] A. Menon and C. Elkan. Link prediction via matrix factorization. In ECML/PKDD, 2011.
[18] A. Mislove, B. Viswanath, K. Gummadi, and P. Druschel. You are who you know: Inferring user profiles in online social networks. In WSDM, 2010.
[19] P. Nasirifard and C. Hayes. Tadvise: A twitter assistant based on twitter lists. In SocInfo, 2011.
[20] M. Newman. Modularity and community structure in networks. PNAS, 2006.
[21] G. Palla, I. Derenyi, I. Farkas, and T. Vicsek. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 2005.
[22] C. Rother, V. Kolmogorov, V. Lempitsky, and M. Szummer. Optimizing binary MRFs via extended roof duality. In CVPR, 2007.
[23] A. Streich, M. Frank, D. Basin, and J. Buhmann. Multi-assignment clustering for boolean data. JMLR, 2012.
[24] J. Ugander, B. Karrer, L. Backstrom, and C. Marlow. The anatomy of the Facebook social graph. preprint, 2011.
[25] C. Volinsky and A. Raftery. Bayesian information criterion for censored survival models. Biometrics, 2000.
[26] D. Vu, A. Asuncion, D. Hunter, and P. Smyth. Dynamic egocentric models for citation networks. In ICML, 2011.
[27] S. Wu, J. Hofman, W. Mason, and D. Watts. Who says what to whom on twitter. In WWW, 2011.
[28] J. Yang and J. Leskovec. Community-affiliation graph model for overlapping community detection. In ICDM, 2012.
[29] J. Yang and J. Leskovec. Defining and evaluating network communities based on ground-truth. In ICDM, 2012.
[30] T. Yoshida. Toward finding hidden communities based on user profiles. In ICDM Workshops, 2010.
[31] J. Zhao. Examining the evolution of networks based on lists in twitter. In IMSAA, 2011. 9