A Community Detection Algorithm Based on Node Degree Difference and Node Similarity

Abstract:

This paper proposes an algorithm called DDSCDA, which is based on the concepts of the node degree difference and the node similarity. In the algorithm, we iteratively extract the node from the network with larger degree and certified the node as a kernel node, then take the kernel node as the founder or initiator of a community to attract its neighbors to join in that community; by doing so, we obtain a partition corresponding to a coarse-grained community structure of the network. Finally taken the coarse-grained community as a starting point, we use the strategy of LPA to propagate labels through the network further. At the end of the algorithm, we obtain the final community structure. We compared the performance with classical community detection algorithms such as LPA, LPAm, FastQ, etc., the experimental results have manifested that our proposal is a feasible algorithm, can extract higher quality communities from the network, and outperforms the previous algorithms significantly.

• Periodical: Applied Mechanics and Materials (Volumes 462-463)
• Pages: 458-461
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.462-463.458
• Online since: November 2013
• Authors: Jian Jun Cheng, Peng Fei Wang, Qi Bin Zhang, Zheng Quan Zhang, Ming Wei Leng, Hong Xu, Xiao Yun Chen*
• Keywords: Community Detection, Community Structure, Node Degree Difference

References

[1] B. Kernighan and S. Lin. Bell system technical journal, (1970).

[2] Gong M G, Zhang L J, Ma J J, et al. Journal of Computer Science and Technology, 2012, 27(3): 455-467.

[3] Pons P, Latapy M. Computing communities in large networks using random walks[M]/Computer and Information Sciences-ISCIS 2005. Springer Berlin Heidelberg, 2005: 284-293.

DOI: 10.1007/11569596_31

[4] Gong M, Ma L, Zhang Q, et al. Physica A: Statistical Mechanics and its Applications, 2012, 391(15): 4050-4060.

DOI: 10.1016/j.physa.2012.03.021

[5] Danon L, Díaz-Guilera A, Arenas A. Journal of Statistical Mechanics: Theory and Experiment, 2006, 2006(11): P11010.

DOI: 10.1088/1742-5468/2006/11/p11010

[6] Girvan M, Newman M E J. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826.

[7] Newman M E J, Girvan M. Physical review E, 2004, 69(2): 026113.

[8] Newman M E J. Physical review E, 2004, 69(6): 066133.

[9] Raghavan U N, Albert R, Kumara S. Physical Review E, 2007, 76(3): 036106.

[10] Barber M J, Clark J W. Physical Review E, 2009, 80(2): 026129.

[11] Zachary W W. Journal of anthropological research, 1977: 452-473.

[12] Lusseau D, Schneider K, Boisseau O J, et al. Behavioral Ecology and Sociobiology, 2003, 54(4): 396-405.

[13] Lusseau D, Newman M E J. Proceedings of the Royal Society of London. Series B: Biological Sciences, 2004, 271(Suppl 6): S477-S481.