Overlapping Community Detection in Dynamic Networks

Nathan Aston, Jacob Hertzler, Wei Hu^*

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

DOI: 10.4236/jsea.2014.710078                

Abstract

Due to the increasingly large size and changing nature of social networks, algorithms for dynamic networks have become an important part of modern day community detection. In this paper, we use a well-known static community detection algorithm and modify it to discover communities in dynamic networks. We have developed a dynamic community detection algorithm based on Speaker-Listener Label Propagation Algorithm (SLPA) called SLPA Dynamic (SLPAD). This algorithm, tested on two real dynamic networks, cuts down on the time that it would take SLPA to run, as well as produces similar, and in some cases better, communities. We compared SLPAD to SLPA, LabelRankT, and another algorithm we developed, Dynamic Structural Clustering Algorithm for Networks Overlapping (DSCAN-O), to further test its validity and ability to detect overlapping communities when compared to other community detection algorithms. SLPAD proves to be faster than all of these algorithms, as well as produces communities with just as high modularity for each network.

Keywords

Community Detection, Modularity, Dynamic Networks, Overlapping Community Detection, Label Propagation

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	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, Article ID: 036106. http://dx.doi.org/10.1103/PhysRevE.76.036106
[2]	Xie, J.R., Szymanski, B.K. and Liu, X.M. (2011) Slpa: Uncovering Overlapping Communities in Social Networks via a Speaker-Listener Interaction Dynamic Process. 2011 IEEE 11th International Conference on Data Mining Workshops (ICDMW), Vancouver, 11-11 December 2011, 344-349.
[3]	Xie, J.R. (2012) Agent-Based Dynamics Models for Opinion Spreading and Community Detection in Large-Scale Social Networks. Diss. Rensselaer Polytechnic Institute, Troy.
[4]	Aston, N. and Hu, W. (2014) Community Detection in Dynamic Social Networks. Communications and Network 6.02, 124.
[5]	Pizzuti, C. (2008) GA-Net: A Genetic Algorithm for Community Detection in Social Networks. Parallel Problem Solving from Nature—PPSN X. Springer, Berlin Heidelberg, 1081-1090.
[6]	Leskovec, J., Kleinberg, J. and Faloutsos, C. (2005) Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations. In: Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, ACM, New York, 177-187.
[7]	Hristova, D., Musolesi, M. and Mascolo, C. (2014) Keep Your Friends Close and Your Facebook Friends Closer: A Multiplex Network Approach to the Analysis of Offline and Online Social Ties. arXiv preprint arXiv:1403.8034
[8]	Aharony, N., et al. (2010) Tracing Mobile Phone App Installations in the “Friends and Family” Study. Proceedings of the 2010 Workshop on Information in Networks (WIN’10).
[9]	Newman, M.EJ. (2006) Modularity and Community Structure in Networks. Proceedings of the National Academy of Sciences, 103, 8577-8582. http://dx.doi.org/10.1073/pnas.0601602103
[10]	Shen, H.W., et al. (2009) Detect Overlapping and Hierarchical Community Structure in Networks. Physica A: Statistical Mechanics and its Applications, 388, 1706-1712.