×

Label propagation algorithm for community detection based on node importance and label influence. (English) Zbl 1376.91133

Summary: Recently, the detection of high-quality community has become a hot spot in the research of social network. Label propagation algorithm (LPA) has been widely concerned since it has the advantages of linear time complexity and is unnecessary to define objective function and the number of community in advance. However, LPA has the shortcomings of uncertainty and randomness in the label propagation process, which affects the accuracy and stability of the community. For large-scale social network, this paper proposes a novel label propagation algorithm for community detection based on node importance and label influence (LPA_NI). The experiments with comparative algorithms on real-world networks and synthetic networks have shown that LPA_NI can significantly improve the quality of community detection and shorten the iteration period. Also, it has better accuracy and stability in the case of similar complexity.

MSC:

91D30 Social networks; opinion dynamics
05C82 Small world graphs, complex networks (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Lin, Youfang; Wang, Tianyu; Tang, Rui; Zhou, Yuanwei; Huang, Houkuan, An effective model and algorithm for community detection in social networks, J. Comput. Res. Dev., 49, 2, 337-345 (2012)
[2] Liu, Dayou; Jin, Di; He, Dongxiao; Huang, Jing; Yang, Jianning; Yang, Bo, Community mining in complex networks, J. Comput. Res. Dev., 50, 10, 2140-2154 (2013)
[3] Shiga, M.; Takigawa, I.; Mamitsuka, H., A spectral approach to clustering numerical vectors as nodes in a networks, Pattern Recognit., 44, 2, 236-251 (2011) · Zbl 1211.68363
[4] Huang, Liang; Li, Ruixuan; Chen, Hong; Gu, Xiwu; Wen, Kunmei; Li, Yuhua, Detecting network communities using regularized spectral clustering algorithm, Artif. Intell. Rev., 41, 4, 579-594 (2014)
[5] Guimera, R.; Sales-Pardo, M.; Amaral, L. A., Modularity from fluctuations in random graphs and complex networks, Phys. Rev. E, 70, 2, Article 188 pp. (2004)
[6] Guimera, R., Functional cartography of complex metabolic networks, Nature, 433, 7028, 895-900 (2005)
[7] Duch, J.; Arenas, A., Community detection in complex networks using extremal optimization, Phys. Rev. E, 72, 2, Article 986 pp. (2005)
[8] Bu, Zhan; Zhang, Chengcui; Xia, Zhengyou; Wang, Jiandong, A fast parallel modularity optimization algorithm (FPMQA) for community detection in online social network, Knowl.-Based Syst., 50, 3, 246-259 (2013)
[9] Zhang, S.; Zhao, H., Normalized modularity optimization method for community identification with degree adjustment, Phys. Rev. E, 88, 5-1, Article 471 pp. (2013)
[10] Girvan, M.; Newman, M. E.J., Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA, 99, 12, 7821-7826 (2002) · Zbl 1032.91716
[11] Wu, F.; Huberman, B. A., Finding communities in linear time: a physics approach, Eur. Phys. J. B-Condens. Matter, 38, 2, 331-338 (2004)
[12] Raghavan, U. N.; Albert, R.; Kumara, S., Near linear-time algorithm to detect community structures in large-scale networks, Phys. Rev. E, 76, 3, Article 036106 pp. (2007)
[13] Steve, G., Finding overlapping communities in networks by label propagation, New J. Phys., 12, 10, 2011-2024 (2010) · Zbl 1448.90094
[14] Barber, M. J.; Clark, J. W., Detecting network communities by propagating labels under constraints, Phys. Rev. E, 80, 2, Article 026129 pp. (2009)
[15] Leung, I. X.; Hui, P.; Lio, P.; Crowcroft, J., Towards real time community detection in large networks, Phys. Rev. E, 79, 6, Article 066107 pp. (2009)
[16] Zhang, XianKun; Tian, Xue; Li, YaNan; Song, Chen, Label propagation algorithm based on edge clustering coefficient for community detection in complex networks, Int. J. Mod. Phys. B, 28, 30 (2014)
[17] Zhang, XianKun; Fei, Song; Song, Chen; Tian, Xue; Ao, YangYue, Label propagation algorithm based on local cycles for community detection, Int. J. Mod. Phys. B, 29, 5 (2015)
[18] Xing, Y.; Meng, F.; Zhou, Y.; Zhu, M.; Shi, M.; Sun, G., A node influence based label propagation algorithm for community detection in networks, Sci. World J., 2014, 5, Article 627581 pp. (2014)
[19] Sohn, J.; Kang, D.; Park, H.; Joo, B. G.; Chung, I. J., An Improved Social Network Analysis Method for Social Networks, 115-123 (2014), Springer: Springer Netherlands
[20] Šubelj, L.; Bajec, M., Group detection in complex networks: an algorithm and comparison of the state of the art, Phys. A, Stat. Mech. Appl., 397, 3, 144-156 (2014) · Zbl 1395.68220
[21] Green, O.; Bader, D. A., Faster betweenness centrality based on data structure experimentation, Proc. Comput. Sci., 18, 1, 399-408 (2014)
[22] Zhang, Xian-Kun; Jia, Jia; Song, Chen, Ranking the importance of user node in micro-blog social network, Comput. Eng. Des., 37, 8, 2050-2056 (2016)
[23] Newman, M. E.J.; Girvan, M., Finding and evaluating community structure in networks, Phys. Rev. E, 69, 2, Article 026113 pp. (2004) · Zbl 1032.91716
[24] Zachary, W. W., An information flow model for conflict and fission in small groups, J. Anthropol. Res., 452-473 (1977)
[25] Girvan, M.; Newman, M. E.J., Community structure in social and biological networks, Proc. Natl. Acad. Sci., 99, 12, 7821-7826 (2002) · Zbl 1032.91716
[26] Papadopoulos, S.; Kompatsiaris, Y.; Vakali, A.; Spyridonos, P., Community detection in social media performance and application considerations, Data Min. Knowl. Discov., 24, 3, 515-554 (2012)
[27] Lancichinetti, Andrea; Fortunato, Santo; Kertész, János, Detecting the overlapping and hierarchical community structure in complex networks, New J. Phys., 11, 015-033 (2009)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.