Yu-Ru Lin
ABSTRACT
We discover communities from social network data, and analyze the community evolution. These communities are inherent characteristics of human interaction in online social networks, as well as paper citation networks. Also, communities may evolve over time, due to changes to individuals' roles and social status in the network as well as changes to individuals' research interests. We present an innovative algorithm that deviates from the traditional two-step approach to analyze community evolutions. In the traditional approach, communities are first detected for each time slice, and then compared to determine correspondences. We argue that this approach is inappropriate in applications with noisy data. In this paper, we propose FacetNet for analyzing communities and their evolutions through a robust unified process. In this novel framework, communities not only generate evolutions, they also are regularized by the temporal smoothness of evolutions. As a result, this framework will discover communities that jointly maximize the fit to the observed data and the temporal evolution. Our approach relies on formulating the problem in terms of non-negative matrix factorization, where communities and their evolutions are factorized in a unified way. Then we develop an iterative algorithm, with proven low time complexity, which is guaranteed to converge to an optimal solution. We perform extensive experimental studies, on both synthetic datasets and real datasets, to demonstrate that our method discovers meaningful communities and provides additional insights not directly obtainable from traditional methods.
- S. Asur, S. Parthasarathy, and D. Ucar. An event-based framework for characterizing the evolutionary behavior of interaction graphs. In Proc. of the 13th ACM SIGKDD Conference, 2007. Google Scholar
Digital Library
- D. Chakrabarti, R. Kumar, and A. Tomkins. Evolutionary clustering. In Proc. of the 12th ACM SIGKDD Conference, 2006. Google ScholarDigital Library
- Y. Chi, X. Song, D. Zhou, K. Hino, and B. L. Tseng. Evolutionary spectral clustering by incorporating temporal smoothness. In Proc. of the 13th ACM SIGKDD Conference, 2007. Google ScholarDigital Library
- F. R. K. Chung. Spectral Graph Theory. American Mathematical Society, 1997.Google Scholar
- S. Dhillon, Y. Guan, and B. Kulis. Kernel k-means: spectral clustering and normalized cuts. In Proc. of the 10th ACM SIGKDD Conference, 2004. Google ScholarDigital Library
- G. Flake, S. Lawrence, and C. Giles. Efficient identification of web communities. In Proc. of the 6th ACM SIGKDD Conference, 2000. Google ScholarDigital Library
- J. M. Kleinberg. Authoritative sources in a hyperlinked environment. J. of the ACM, 46(5), 1999. Google ScholarDigital Library
- R. Kumar, J. Novak, P. Raghavan, and A. Tomkins. On the bursty evolution of blogspace. In Proc. of the 12th WWW Conference, 2003. Google ScholarDigital Library
- R. Kumar, J. Novak, and A. Tomkins. Structure and evolution of online social networks. In Proc. of the 12th ACM SIGKDD Conference, 2006. Google ScholarDigital Library
- J. Leskovec, J. Kleinberg, and C. Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In Proc. of the 11th ACM SIGKDD Conference, 2005. Google ScholarDigital Library
- Y. Lin, H. Sundaram, Y. Chi, J. Tatemura, and B. L. Tseng. Blog community discovery and evolution based on mutual awareness expansion. In Proc. of the Int. Conf. on Web Intelligence, 2007. Google ScholarDigital Library
- Q. Mei and C. Zhai. Discovering evolutionary theme patterns from text: an exploration of temporal text mining. In Proc. of the 11th ACM SIGKDD Conference, 2005. Google ScholarDigital Library
- M. E. J. Newman and M. Girvan. Finding and evaluating community structure in networks. Phys. Rev. E, 2004.Google ScholarCross Ref
- H. Ning, W. Xu, Y. Chi, Y. Gong, and T. Huang. Incremental spectral clustering with application to monitoring of evolving blog communities. In SIAM Int. Conf. on Data Mining, 2007.Google ScholarCross Ref
- L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. In Technical report, Stanford Digital Library Technologies Project, Stanford University, Stanford, CA, USA, 1998.Google Scholar
- G. Palla, A.-L. Barabasi, and T. Vicsek. Quantifying social group evolution. Nature, 446, 2007.Google Scholar
- P. Sarkar and A. W. Moore. Dynamic social network analysis using latent space models. SIGKDD Explor. Newsl., 7(2), 2005. Google ScholarDigital Library
- J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Trans. on Pattern Analysis and Machine Intelligence, 22(8), 2000. Google ScholarDigital Library
- M. Spiliopoulou, I. Ntoutsi, Y. Theodoridis, and R. Schult. Monic: modeling and monitoring cluster transitions. In Proc. of the 12th ACM SIGKDD Conference, 2006. Google ScholarDigital Library
- J. Sun, C. Faloutsos, S. Papadimitriou, and P. S. Yu. GraphScope: parameter-free mining of large time-evolving graphs. In Proc. of the 13th ACM SIGKDD Conference, 2007. Google ScholarDigital Library
- M. Toyoda and M. Kitsuregawa. Extracting evolution of web communities from a series of web archives. In HYPERTEXT '03: Proc. of the 14th ACM conference on hypertext and hypermedia, 2003. Google ScholarDigital Library
- S. Wasserman and K. Faust. Social Network Analysis: Methods and Applications. Cambridge University Press, 1994.Google ScholarCross Ref
- S. White and P. Smyth. A spectral clustering approach to finding communities in graph. In SDM, 2005.Google ScholarCross Ref
- K. Yu, S. Yu, and V. Tresp. Soft clustering on graphs. In NIPS, 2005.Google Scholar
- H. Zha, X. He, C. H. Q. Ding, M. Gu, and H. D. Simon. Spectral relaxation for k-means clustering. In NIPS, 2001.Google Scholar
Index Terms
- Facetnet: a framework for analyzing communities and their evolutions in dynamic networks
Recommendations
Analyzing communities and their evolutions in dynamic social networks
We discover communities from social network data and analyze the community evolution. These communities are inherent characteristics of human interaction in online social networks, as well as paper citation networks. Also, communities may evolve over ...
Maximizing modularity intensity for community partition and evolution
Most previous studies of community partition have often focused on the network topology, the topology and link weights are in fact closely associated with each other for community formation in complex networks. This paper proposes a function-modularity ...
Characterizing the Evolution of Communities on Reddit
SMSociety'20: International Conference on Social Media and SocietyOne of the most important structures in social networks is communities. Communities in social networks evolve over time. Understanding the evolution of communities is useful in many applications, such as building successful communities, maintaining the ...
Comments