Author : K Lakshmi Priya 1
Date of Publication :7th March 2016
Abstract: Analysis on dynamic networks has become a popularly discussed topic today, with more and more emerging data over time. In this paper we investigate the problem of detecting and tracking the variation communities within a given time period. We first define a metric to measure the strength of a community, called the normalized temporal community strength. And then, we propose our analysis framework. The community may evolve over time, either split to multiple communities or merge with others. We address the problem of evolutionary clustering with requirement on temporal smoothness and propose a revised soft clustering method based on non-negative matrix factorization. Then we use a clustering matching method to find the soft correspondence between different community distribution structures. This matching establishes the connection between consecutive snapshots. To estimate the variation rate and meanwhile address the smoothness during continuous evolution, we propose an objective function that combines the conformity of current variation and historical variation trend. In addition, we integrate the weights to the objective function to identify the temporal outliers. An iterative coordinate descent method is proposed to solve the optimization framework. We extensively evaluate our method with a synthetic dataset and several real datasets. The experimental results demonstrate the effectiveness of our method, which is greatly superior to the baselines on detection of the communities with significant variation over time.
Reference :
-
- Chi, Y., Song, X., Zhou, D., Hino, K., Tseng, B.L.: Evolutionary spectral clustering by incorporating temporal smoothness. In: Proc. 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2007)
- Eagle, N., Pent land, A., Laser, and D.: Inferring friendship network structure by using mobile phone data. Proceedings of the National Academy of Sciences 106(36), 15274{15278 (2009)
- Falkowski, T., Bartelheimer, J., Spiliopoulou, and M.: Mining and visualizing the evolution of subgroups in social networks. In: Proc. IEEE/WIC/ACM International Conference on Web Intelligence (2006)
- Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, and M.W.: Statistical properties of community structure in large social and information networks. In: Proc. 17th International Conference on the World Wide Web (2008)
- MIT academic calendar 2004-2005, http://web.mit.edu/registrar/www/calendar0405.html
- Mucha, P.J., Richardson, T., Macon, K., Porter, M.A., Onnela, and J.P.: Community structure in time dependent, multistate, and multiplex networks. Science 328(5980), 876{878 (2010)
- Newman, M.E.J.: Modularity and community structure in networks. Proceedings of the National Academy of Sciences 103(23), 8577{8582 (2006)
- Project Honey Pot, http://www.projecthoneypot.org
- Prince, M., Dahl, B., Holloway, L., Keller, A., Langheinrich, and E.: Understanding how spammers steal your e-mail address: An analysis of the rest six months of data from Project Honey Pot. In: Proc. 2nd Conference on Email and AntiSpam (2005)
- Tang, L., Liu, H., Zhang, J., Nazeri, and Z.: Community evolution in dynamic multimode networks. In: Proc. 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2008)
- Tantipathananandh, C., Berger-Wolf, T., Kempe, D.: A framework for community identification in dynamic social networks. In: Proc. 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2007)
- von Luxburg, U.: A tutorial on spectral clustering. Statistics and Computing 17(4), 395{416 (2007)
- Xu, K.S., Kliger, M., Hero III, A.O.: Evolutionary spectral clustering with adaptive forgetting factor. In: Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing (2010)
- Yu, S.X., Shi, J.: Multiclass spectral clustering. In: Proc. 9th IEEE International Conference on Computer Vision (2003)