Lei Tang
Huan Liu
Jianping Zhang
ABSTRACT
A multi-mode network typically consists of multiple heterogeneous social actors among which various types of interactions could occur. Identifying communities in a multi-mode network can help understand the structural properties of the network, address the data shortage and unbalanced problems, and assist tasks like targeted marketing and finding influential actors within or between groups. In general, a network and the membership of groups often evolve gradually. In a dynamic multi-mode network, both actor membership and interactions can evolve, which poses a challenging problem of identifying community evolution. In this work, we try to address this issue by employing the temporal information to analyze a multi-mode network. A spectral framework and its scalability issue are carefully studied. Experiments on both synthetic data and real-world large scale networks demonstrate the efficacy of our algorithm and suggest its generality in solving problems with complex relationships.
- E. Airodi, D. Blei, S. Fienberg, and E. P. Xing. Mixed membership stochastic blockmodels. JMLR, 2008. Google Scholar
Digital Library
- S. Asur, S. Parthasarathy, and D. Ucar. An event-based framework for characterizing the evolutionary behavior of interaction graphs. In KDD, pages 913--921, 2007 Google ScholarDigital Library
- F. R. Bach and M. I. Jordan. Learning spectral clustering. In NIPS, 2004.Google ScholarDigital Library
- L. Backstrom, D. Huttenlocher, J. Kleinberg, and X. Lan. Group formation in large social networks: membership, growth, and evolution. In KDD, 2006. Google ScholarDigital Library
- J. Baumes, M. Goldberg, M. Magdon-Ismail, and W. Wallace. Discovering hidden groups in communication networks. In 2nd NSF/NIJ Symposium on intelligence and Security Informatics, 2004.Google ScholarCross Ref
- R. Bhatia. Matrix Analysis. Springer, 1997.Google Scholar
- D. M. Blei, A. Y. Ng, and M. I. Jordan. Latent dirichlet allocation. J. Mach. Learn. Res., 3:993--1022, 2003. Google ScholarCross Ref
- R. Breiger, K. Carley, and P. Pattison, editors. Dynamic Social Network Modeling and Analysis: Workshop Summary and Papers. 2003.Google Scholar
- D. Chakrabarti, R. Kumar, and A. Tomkins. Evolutionary clustering. In KDD, pages 554--560, 2006 Google ScholarDigital Library
- Y. Chi, X. Song, D. Zhou, K. Hino, and B. L. Tseng. Evolutionary spectral clustering by incorporating temporal smoothness. In KDD, pages 153--162, 2007 Google ScholarDigital Library
- I. S. Dhillon. Co-clustering documents and words using bipartite spectral graph partitioning. In KDD, pages 269--274, 2001 Google ScholarDigital Library
- C. Ding, T. Li, W. Peng, and H. Park. Orthogonal nonnegative matrix t-factorizations for clustering. In KDD, pages 126--135, 2006 Google ScholarDigital Library
- B. Gao, T.-Y. Liu, X. Zheng, Q.-S. Cheng, and W.-Y. Ma. Consistent bipartite graph co-partitioning for star-structured high-order heterogeneous data co-clustering. In KDD, pages 41--50, 2005 Google ScholarDigital Library
- A. Globerson, G. Chechik, F. Pereira, and N. Tishby. Euclidean embedding of co-occurrence data. J. Mach. Learn. Res., 8:2265--2295, 2007. Google ScholarDigital Library
- G. H. Golub and C. F. V. Loan. Matrix Computation. Johns Hopkins University Press, 1996.Google Scholar
- M. S. Handcock, A. E. Raftery, and J. M. Tantrum. Model-based clustering for social networks. Journal Of The Royal Statistical Society Series A, 127(2), 2007.Google ScholarCross Ref
- C. Kemp, T. L. Griffiths, and J. B. Tenenbaum. Discoverying latent classes in relational data. Technical report, Massachusetts Institute of Technology, 2004.Google Scholar
- B. Klimat and Y. Yang. The enron corpus: A new dataset for email classification research. In ECML, 2004.Google ScholarDigital Library
- G. Kossinets and D. J. Watts. Empirical analysis of an evolving social network. Science, 311(5757), 2006.Google Scholar
- M. N. Lauren Ancel Meyers and B. Pourbohloul. Predicting epidemics on directed contact networks. In Journal of Theoretical Biology, volume 240, 2006.Google Scholar
- J. Leskovec, J. Kleinberg, and C. Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In KDD, pages 177--187, 2005. Google ScholarDigital Library
- Y.-R. Lin, Y. Chi, S. Zhu, H. Sundaram, and B. L. Tseng. Facetnet: a framework for analyzing communities and their evolutions in dynamic networks. In WWW, pages 685--694, 2008. Google ScholarDigital Library
- B. Long, Z. M. Zhang, X. Wú, and P. S. Yu. Spectral clustering for multi-type relational data. In ICML, pages 585--592, 2006. Google ScholarDigital Library
- B. Long, Z. M. Zhang, and P. S. Yu. Co-clustering by block value decomposition. In KDD, 2005. Google ScholarDigital Library
- B. Long, Z. M. Zhang, and P. S. Yu. A probabilistic framework for relational clustering. In KDD, pages 470--479, 2007. Google ScholarDigital Library
- A. McCallum, X. Wang, and A. Corrada-Emmanuel. Topic and role discovery in social networks with experiments on enron and academic email. Journal of Artificial Intelligence Research, (0):249--272, 2007. Google ScholarDigital Library
- K. Nowicki and T. A. B. Snijders. Estimation and prediction for stochastic blockstructures. Journal of the American Statistical Association, 96(455):1077--1087, 2001.Google ScholarCross Ref
- J. Palau, M. Montaner, and B. Lopez. Collaboration analysis in recommender systems using social networks. In In Eighth Intl. Workshop on Cooperative info. Agents (CIA'04), 2004.Google ScholarCross Ref
- M. S. H. Peter D. Hoff, Adrian E. Raftery. Latent space approaches to social network analysis. Journal of the American Statistical Association, 2002.Google ScholarCross Ref
- P. Sarkar and A. W. Moore. Dynamic social network analysis using latent space models. SIGKDD Explor. Newsl., 7(2):31--40, 2005. Google ScholarDigital Library
- A. Strehl and J. Ghosh. Cluster ensembles -- a knowledge reuse framework for combining multiple partitions. J. Mach. Learn. Res., 3:583--617, 2003. Google ScholarDigital Library
- C. Tantipathananandh, T. Berger-Wolf, and D. Kempe. A framework for community identification in dynamic social networks. In KDD, 2007. Google ScholarDigital Library
- J. Wang, H. Zeng, Z. Chen, H. Lu, L. Tao, and W.-Y. Ma. Recom: reinforcement clustering of multi-type interrelated data objects. In SIGIR, 2003. Google ScholarDigital Library
- X. Wang, N. Mohanty, and A. McCallum. Group and topic discovery from relations and their attributes. In NIPS, pages 1449--1456. 2006.Google Scholar
- S. Wasserman and K. Faust. Social Netwok Analysis: Methods and Applications. Cambridge University Press, 1994.Google ScholarCross Ref
- H. Zha, X. He, C. Ding, H. Simon, and M. Gu. Bipartite graph partitioning and data clustering. In CIKM, pages 25--32, New York, NY, USA, 2001. ACM. Google ScholarDigital Library
- H. Zha, X. He, C. H. Q. Ding, M. Gu, and H. D. Simon. Spectral relaxation for k-means clustering. In NIPS, pages 1057--1064, 2001.Google ScholarDigital Library
- D. Zhou, J. Huang, and B. Schölkopf. Learning from labeled and unlabeled data on a directed graph. In ICML, pages 1036--1043, 2005. Google ScholarDigital Library
- D. Zhou, E. Manavoglu, J. Li, C. L. Giles, and H. Zha. Probabilistic models for discovering e-communities. In WWW, pages 173--182, 2006. Google ScholarDigital Library
Index Terms
- Community evolution in dynamic multi-mode networks
Recommendations
Explaining social events through community evolution on temporal networks
Highlights- Establish a connection between the evolution of social networks and real social events.
AbstractThe social network is closely related to people’s lives. And social events are the products of the human subjective initiative during the evolution of networks. Therefore, there is a close correlation between social events and network ...
Evolution of communities in dynamic social networks: An efficient map-based approach
Highlights- Proposing a highly efficient approach to track community evolution.
- Defining a ...
AbstractThe expanded domain of expert system applications has risen the impact of modeling and analysis of community evolution in social networks as an important part of the decision-making process. Social networks are time-variant systems, ...
Community Evolution in Dynamic Social Networks -- Challenges and Problems
ICDMW '11: Proceedings of the 2011 IEEE 11th International Conference on Data Mining WorkshopsInformation networks that describe the relationship between individuals are called social networks and are usually modeled by a graph structure. Social network analysis is the study of these information networks which leads to uncover patterns of ...
Comments