Complex networks are a hot topic in social science research today. Analyzing the structure of the relationships embedded in them through community discovery techniques is an important tool for the study of complex networks. To address the randomness problem of label propagation in label propagation algorithms, this paper proposes an improved algorithm for label propagation based on rough kernels. The algorithm first performs the extraction of rough kernels and assigns unique labels to each rough kernel to achieve fast label preprocessing; then intervenes in the label propagation process through the ranking of node influence to reduce its randomness and make the division results more stable; finally, the community division is performed by the distribution of network labels. Experiments are conducted in real networks, and the results show that the combined performance of the method in this paper is better than the traditional labeling algorithm in terms of modularity and NMI metrics, and the proposed improved algorithm leads to improved community division results.

Laizong Huang, Fei Liu. An Improved Algorithm for Label Propagation Based on Rough Core. Academic Journal of Computing & Information Science (2022), Vol. 5, Issue 12: 82-88. https://doi.org/10.25236/AJCIS.2022.051212.

[1] Barabasi A L, Albert R. Emergence of scaling in random networks [J]. Science, 1999, 286 (5439):509-512.

[2] M. Girvan and M. E. J. Newman, ‘‘Community structure in social and biological networks,’’ Proc. Nat. Acad. Sci. USA, vol. 99, no. 12, pp. 7821–7826, Jun. 2002.

[3] Raghavan Usha Nandini and Albert Réka and Kumara Soundar. NIAr linIAr time algorithm to detect community structures in large-scale networks. [J]. Physical review. E, Statistical, nonlinIAr, and soft matter physics, 2007, 76(3 Pt 2): 036106.

[4] Girvan M, Newman M E J. Community structure in social and biological networks [J]. Proceedings of the national academy of sciences, 2002, 99(12): 7821-7826.

[5] Yin C, Zhu S, Chen H, et al. A method for community detection of complex networks based on hierarchical clustering [J]. International Journal of Distributed Sensor Networks, 2015, 11(6): 849140.

[6] Helal N A, Ismail R M, Badr N L, et al. Leader‐based community detection algorithm for social networks [J]. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2017, 7(6): e1213.

[7] Jiang F, Jin S, Wu Y, et al. A uniform framework for community detection via influence maximization in social networks[C]//2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2014). IEEE, 2014: 27-32.

[8] Pothen A, Simon H D, Liou K P. Partitioning sparse matrices with eigenvectors of graphs [J]. SIAM journal on matrix analysis and applications, 1990, 11(3): 430-452.

[9] Capocci A, Baldassarri A, Servedio V D P, et al. Friendship, collaboration and semantics in Flickr: from social interaction to semantic similarity[C]//Proceedings of the International Workshop on Modeling Social Media. 2010: 1-4.

[10] Shen G, Ye D. A distance-based spectral clustering approach with applications to network community detection [J]. Journal of Industrial Information Integration, 2017, 6: 22-32.

[11] Newman M E J. Fast algorithm for detecting community structure in networks [J]. Physical review E, 2004, 69(6): 066133.

[12] Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of communities in large networks [J]. Journal of statistical mechanics: theory and experiment, 2008, 2008(10): P10008.

[13] Guimera R, Nunes Amaral L A. Functional cartography of complex metabolic networks [J]. Nature, 2005, 433(7028): 895-900.

[14] De Meo P, Ferrara E, Fiumara G, et al. Mixing local and global information for community detection in large networks[J]. Journal of Computer and System Sciences, 2014, 80(1): 72-87.

[15] Fortunato S, Barthelemy M. Resolution limit in community detection [J]. Proceedings of the national academy of sciences, 2007, 104(1): 36-41.

[16] Mairisha M, Saptawati G A P. Improved modularity for community detection analysis in weighted graph[C]//2016 4th International Conference on Information and Communication Technology (ICoICT). IEEE, 2016: 1-6.

[17] Chen S, Wang Z Z, Bao M H, et al. Adaptive multi-resolution modularity for detecting communities in networks [J]. Physica A: Statistical Mechanics and its Applications, 2018, 491: 591-603.

[18] Qiao Shaojie, Han Nan, Zhang Kaifeng, et al. Overlapping community detection algorithms in complex network big data[J]. Journal of Software, 2017, 28(3):17.

[19] Qiao Shaojie, Guo Jun, Han Nan, et al. Parallel discovery algorithms for large scale complex network communities[J]. Journal of Computer Science, 2017, 40(3): 687-700.

[20] Zhu X, Ghahramani Z. Learning from labeled and unlabeled data with label propagation[R]. City: Citeseer, 2002. 

[21] Raghavan U N, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical review E, 2007, 76(3): 036106.