Community Detection in Dynamic Social Networks

Nathan Aston, Wei Hu

Department of Computer Science, Houghton College, Houghton, USA.

DOI: 10.4236/cn.2014.62015                

Abstract

There are many community detection algorithms for discovering communities in networks, but very few deal with networks that change structure. The SCAN (Structural Clustering Algorithm for Networks) algorithm is one of these algorithms that detect communities in static networks. To make SCAN more effective for the dynamic social networks that are continually changing their structure, we propose the algorithm DSCAN (Dynamic SCAN) which improves SCAN to allow it to update a local structure in less time than it would to run SCAN on the entire network. We also improve SCAN by removing the need for parameter tuning. DSCAN, tested on real world dynamic networks, performs faster and comparably to SCAN from one timestamp to another, relative to the size of the change. We also devised an approach to genetic algorithms for detecting communities in dynamic social networks, which performs well in speed and modularity.

Keywords

Community Detection, Dynamic Social Networks, Density, Genetic Algorithms

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Fortunato, S. (2010) Community Detection in Graphs. Physics Reports, 486, 75-174. http://dx.doi.org/10.1016/j.physrep.2009.11.002
[2]	Xu, X., Yuruk, N., Feng, Z. and Schweiger, T. (2007) SCAN: A Structural Clustering Algorithm for Networks. KDD’07. ACM, 824-833. http://dx.doi.org/10.1145/1281192.1281280
[3]	Ester, M., Kriegel, H.-P., Sander, J. and Xu, X. (1996) A Density-Based Algorithm for Discovering Communities in Large Spatial Databases with Noise. Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining (KDD-96).
[4]	Falkowski, T. (2009) Community Analysis in Dynamic Social Networks. PhD. Otto-von-Guericke-University, Magdeburg.
[5]	Ronhovde, R.K., Peter, R. and Nussinov, Z. (2013) An Edge Density Definition of Overlapping and Weighted Graph Communities. arXiv preprint arXiv:1301.3120.
[6]	Raghavan, U.N., Albert, R. and Kumara, S. (2007) Near Linear Time Algorithm to Detect Community Structures in Large-Scale Networks. Physical Review E, 76, 036106. http://dx.doi.org/10.1103/PhysRevE.76.036106
[7]	Xie, J., Szymanski, B.K. and Liu, X. (2011) SLPA: Uncovering Overlapping Communities in Social Networks via a Speaker-Listener Interaction Dynamic Process. Proc. ICDM Workshop, 344-349.
[8]	Pizzuti, C. (2008) GA-Net: A Genetic Algorithm for Community Detection in Social Networks. PPSN, Volume 5199 of Lecture Notes in Computer Science, pages 1081-1090. Springer.
[9]	Leskovec, J., Kleinberg, J. and Faloutsos, C. (2005) Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD).
[10]	Dong, W., Lepri, B. and Pentland, A.S. (2011) Modeling the Co-Evolution of Behaviors and Social Relationships Using Mobile Phone Data, Media, 134-143,
[11]	Newman, M.E.J. (2006) Modularity and Community Structure in Networks. Proceedings of the National Academy of Sciences of the United States of America, 103, 8577-8858. http://dx.doi.org/10.1073/pnas.0601602103