Semi-synchronous communities detection algorithm based on label influence

doi:10.11772/j.issn.1001-9081.2016.06.1573

Journal of Computer Applications ›› 2016, Vol. 36 ›› Issue (6): 1573-1578.DOI: 10.11772/j.issn.1001-9081.2016.06.1573

Previous Articles Next Articles

Semi-synchronous communities detection algorithm based on label influence

WANG Yan¹, HUANG Faliang¹, YUAN Chang'an²

1. Faculty of Software, Fujian Normal University, Fuzhou Fujian 350108, China;
2. Key Laboratory of Scientific Computing and Intelligent Information Processing in Universities of Guangxi, Nanning Guangxi 530023, China

Received:2015-11-04 Revised:2015-12-21 Online:2016-06-10 Published:2016-06-08
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61363037), the Youth Foundation of Humanities and Social Sciences of Ministry of Education (12YJCZH074), the Category A Project of Fujian Provincial Department of Education (JA13077).

基于标签影响力的半同步社区发现算法

汪焱¹, 黄发良¹, 元昌安²

1. 福建师范大学软件学院, 福州 350108;
2. 科学计算与智能信息处理广西高校重点实验室, 南宁 530023

通讯作者: 黄发良
作者简介:汪焱(1988-),男,湖北随州人,硕士,主要研究方向:数据挖掘、社区发现;黄发良(1975-),男,湖南永州人,副教授,博士,CCF会员,主要研究方向:数据挖掘、社交媒体处理;元昌安(1964-),男,安徽肥东人,教授,博士,CCF会员,主要研究方向:数据挖掘。
基金资助:
国家自然科学基金资助项目(61363037);教育部人文社会科学研究青年基金资助项目(12YJCZH074);福建省教育厅A类项目(JA13077)。

Abstract

Abstract: It is a great challenge to discover communities in the fast growing large-scale interactive social information networks such as Weibo and social networks. Although Label Propagation Algorithm (LPA) has great advantage in time complexity, but its inherent multiple random strategies make the algorithm unstable. In order to solve the problem, a semi-synchronous label propagation algorithm named Influence-driven Semi-synchronous Label Propagation Algorithm (ISLPA) was proposed. The propagation oscillation was avoided effectively and the synchronous update between neighbor nodes was realized by abandoning the original random strategy and integrating node influence into label initialization, neighbor node selection and updated order determination. The experimental results from the real-world and artificial networks indicate that, in terms of validity and stability of generated communities from the networks, the proposed ISLPA outperforms the currently typical LPAs used in community detection.

Key words: community detection, Label Propagation Algorithm (LPA), semi-synchronization, node influence, oscillation

摘要： 微博网络与社交网络等的交互式社会信息网络规模的快速增长对社区发现提出巨大挑战。标签传播算法(LPA)虽然在时间复杂度上具有很大的优势,但是其内在的多种随机策略使得算法稳定性不高。针对LPA的随机问题,提出了一种基于影响力的半同步标签传播算法(ISLPA),能有效地避免振荡问题,巧妙地实现了相邻节点之间的同步更新,并结合影响力从初始标签、选择邻居节点和更新顺序三方面进行了改进,摒弃了原有的随机策略。真实网络和人工网络的实验结果表明,ISLPA具有较高的稳定性与有效性,与其他LPA相关算法相比存在明显的优势。

关键词: 社区发现, 标签传播法, 半同步, 节点影响力, 振荡

CLC Number:

TP393

WANG Yan, HUANG Faliang, YUAN Chang'an. Semi-synchronous communities detection algorithm based on label influence[J]. Journal of Computer Applications, 2016, 36(6): 1573-1578.

汪焱, 黄发良, 元昌安. 基于标签影响力的半同步社区发现算法[J]. 计算机应用, 2016, 36(6): 1573-1578.

References

[1] FORTUNATO S. Community detection in graphs[J]. Physics Reports, 2009, 486(3/4/5): 75-174.
[2] COSCIA M, GIANNOTTI F, PEDRESCHI D. A classification for community discovery methods in complex networks[J]. Statistical Analysis & Data Mining the Asa Data Science Journal, 2011, 4(5): 512-546.
[3] 黄发良.信息网络的社区发现及其应用研究[J].复杂系统与复杂性科学,2010,7(1):64-74.(HUANG F L. Studies on community detection and its application in information network[J]. Complex Systems and Complexity Science, 2010, 7(1): 64-74.)
[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] CLAUSET A, NEWMAN M E J, MOORE C. Finding community structure in very large networks[J]. Physical Review E, Statistical Nonlinear, and Soft Matter Physics, 2004, 70(6 Pt 2): 066111.
[6] RAGHAVAN U N, ALBERT R, KUMARA S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E, Statistical Nonlinear, and Soft Matter Physics, 2007, 76(3 Pt 2): 036106.
[7] SUBELJ L, BAJEC M. Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction[J]. Physical Review E, Statistical Nonlinear, and Soft Matter Physics, 2011, 83(3 Pt 2): 036103.
[8] LEUNG I X, HUI P, LIO P, et al. Towards real-time community detection in large networks[J]. Physical Review E, Statistical Nonlinear, and Soft Matter Physics, 2009, 79(6 Pt 2): 066107.
[9] ZHANG X K, FEI S, SONG C, et al. Label propagation algorithm based on local cycles for community detection[J]. International Journal of Modern Physics B, 2015, 29(5): 1550029.
[10] LIN Z, ZHENG X, XIN N, et al. CK-LPA: efficient community detection algorithm based on label propagation with community kernel[J]. Physica A: Statistical Mechanics & Its Applications, 2014, 416: 386-399.
[11] 赵卓翔,王轶彤,田家堂,等.社会网络中基于标签传播的社区发现新算法[J].计算机研究与发展,2011,48(Z2):8-15.(ZHAO Z X, WANG Y T, TIAN J T, et al. A novel algorithm for community discovery in social networks based on label propagation[J]. Journal of Computer Research and Development, 2011, 48(Z2): 8-15.)
[12] BARBER M J, CLARK J W. Detecting network communities by propagating labels under constraints[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2009, 80(2 Pt 2): 026129.
[13] LIU X, MURATA T. Advanced modularity-specialized label propagation algorithm for detecting communities in networks[J]. Physica A: Statistical Mechanics & Its Applications, 2010, 389(7): 1493-1500.
[14] SUBELJ L, BAJEC M. Robust network community detection using balanced propagation[J]. European Physical Journal B, 2011, 81(3): 353-362.
[15] LI S, LOU H, JIANG W, et al. Detecting community structure via synchronous label propagation[J]. Neurocomputing, 2015, 151(3): 1063-1075.
[16] LIU X, MURATA T. How does label propagation algorithm work in bipartite networks?[C]//Proceedings of the 2009 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology. Piscataway, NJ: IEEE, 2009: 5-8.
[17] CORDASCO G, GARGANO L. Label propagation algorithm: a semi-synchronous approach[J]. International Journal of Social Network Mining, 2012, 1(1): 3-26.
[18] TIBÉLY G, KERTÉSZ J. Note on the equivalence of the label propagation method of community detection and a Potts model approach[J]. Physica A: Statistical Mechanics & Its Applications, 2008, 387(19): 4982-4984.
[19] LANCICHINETTI A, FORTUNATO S, RADICCHI F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E, Statistical Nonlinear, and Soft Matter Physics, 2008, 78(4 Pt 2): 046110.
[20] NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2004, 69(2 Pt 2): 026113.
[21] DÍAZ-GUILERA A, DUCH J. Comparing community structure identification[J]. Journal of Statistical Mechanics Theory & Experiment, 2005, 24(9): 09008.

Semi-synchronous communities detection algorithm based on label influence

基于标签影响力的半同步社区发现算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	LI Ping, WANG Fen, CHEN Qidong, SUN Jun. Discrete random drift particle swarm optimization algorithm for solving multi-objective community detection problem [J]. Journal of Computer Applications, 2021, 41(3): 803-811.
[2]	Jicheng CHEN, Hongchang CHEN. Community detection method based on tensor modeling and evolutionary K-means clustering [J]. Journal of Computer Applications, 2021, 41(11): 3120-3126.
[3]	LI Chunying, TANG Yong, XIAO Zhenghong, LI Tiansong. Influential scholar recommendation model in academic social network [J]. Journal of Computer Applications, 2020, 40(9): 2594-2599.
[4]	LUO Xiangyu, LI Jianan, LUO Xiaoxia, WANG Jia. Improved community evolution relationship analysis method for dynamic graphs [J]. Journal of Computer Applications, 2020, 40(8): 2313-2318.
[5]	CHEN Fatang, ZHANG Youshou, DU Zheng. Low complexity offset min-sum algorithm for 5G low density parity check codes [J]. Journal of Computer Applications, 2020, 40(7): 2028-2032.
[6]	ZHENG Wenping, YUE Xiangdou, YANG Gui. Improved label propagation algorithm based on random walk [J]. Journal of Computer Applications, 2020, 40(12): 3423-3429.
[7]	WU Qingshou, CHEN Rongwang, YU Wensen, LIU Genggeng. Overlapping community detection algorithm fusing label preprocessing and node influence [J]. Journal of Computer Applications, 2020, 40(12): 3578-3585.
[8]	LI Shasha, LIANG Dongyang, YU Jie, JI Bin, MA Jun, TAN Yusong, WU Qingbo. Research team mining algorithm based on teacher-student relationship [J]. Journal of Computer Applications, 2020, 40(11): 3198-3202.
[9]	CHENG Qiwei, CHEN Qimai, HE Chaobo, LIU Hai. Overlapping community detection method based on improved symmetric binary nonnegative matrix factorization [J]. Journal of Computer Applications, 2020, 40(11): 3203-3210.
[10]	SHI Baozhu, LI Mei'an. Automatic stitching and restoration algorithm for paper fragments based on angle and edge features [J]. Journal of Computer Applications, 2019, 39(2): 571-576.
[11]	CHEN Wanjie, SHENG Yiqiang. Non-unidimensional community detection algorithm based on network representation learning [J]. Journal of Computer Applications, 2019, 39(12): 3467-3475.
[12]	DU Hangyuan, PEI Xiya, WANG Wenjian. Overlapping community detection algorithm for attributed networks [J]. Journal of Computer Applications, 2019, 39(11): 3151-3157.
[13]	GU Junhua, HUO Shijie, WANG Shoubin, TIAN Zhe. Fast label propagation algorithm based on node centrality and community similarity [J]. Journal of Computer Applications, 2018, 38(5): 1320-1326.
[14]	LI Lei, YAN Guanghui, YANG Shaowen, ZHANG Haitao. Improved Louvain method with strategy of separating isolated nodes [J]. Journal of Computer Applications, 2017, 37(4): 970-974.
[15]	CHEN Yiying, CHAI Bianfang, LI Wenbin, HE Yichao, WU Congcong. Semi-supervised community detection algorithm using active link selection based on iterative framework [J]. Journal of Computer Applications, 2017, 37(11): 3085-3089.