社交网络中基于模块度最大化的标签传播算法的研究

doi:10.11959/j.issn.1000-436x.2017025

Abstract

Abstract:

A kind of community detection method based on the combination of modularity and community structure attributes was proposed.Firstly,updating the whole network after communities merging every time could result in the high time complexity,therefore,introducing propagation distance parameter and “merger going after label propagation” was utilized to reduce time complexity.Secondly,CDMM-LPA algorithm was proposed by combing label propagation with community structure.Finally,empirical analysis on data networks verified the validity of the approaches.The experimental results show that the CDMM-LPA algorithm has a high modularity value and a more stable community structure while reducing the time complexity.

Key words: modularity,propagation distance, community structure, abel propagation, community detection

CLC Number:

TP301.6

Jing CHEN,Yun WAN. Research on label propagation algorithm based on modularity maximization in the social network[J]. Journal on Communications, 2017, 38(2): 25-33.

Figures/Tables 12

References 18

[1]	刘耀庭 . 社交网络结构研究[D]. 杭州:浙江大学, 2008.
	LIU Y T . Research on social network structure[D]. Hangzhou:Zhejiang University, 2008.
[2]	SCOTT J . Social network analysis[M]. London: Sage PublicationPress, 2013.
[3]	KERNIGHAN B W , LIN S . An efficient heuristic procedure for partitioning graphs[J]. Bell System Technical Journal, 1970,49(2): 291-307.
[4]	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.
[5]	NEWMAN M E J . Analysis of weighted networks[J]. Physical Review E, 2004,70(5):056131
[6]	CLAUSET A , NEWMAN M E J , MOORE C . Finding community structure in very large networks[J]. Physical Review E, 2004,70(6):066111
[7]	ZHU X , GHAHRAMANI Z . Learning from labeled and unlabeled data with label propagation[R]. Technical Report CMU-CALD-02-107,Carnegie Mellon University, 2002.
[8]	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
[9]	赵卓翔, 王轶彤, 田家堂 . 社会网络中基于标签传播的社区发现新算法[J]. 计算机研究与发展, 2011,48(S3): 8-15.
	ZHAO Z X , WANG Y T , TIAN J T . A novel algorithm for community discovery in social networks based on label propagation[J]. Journal of Computer Research and Development, 2011,48(S3): 8-15.
[10]	LOU H , LI S H , ZHAO Y X . Detecting community structure using label propagation with weighted coherent neighborhood propinquity[J]. Physica A, 2013,392: 3095-3105.
[11]	GREGORY S , . An algorithm to find overlapping community structure in networks[C]// Knowledge discovery in databases:PKDD 2007. 2007: 91-102.
[12]	WU Z H , LIN Y F , GREGORY S . Balanced multi-label propagation for overlapping community detection in social networks[J]. Journal of Computer Science and Technology, 2012,27(3): 468-479.
[13]	朱牧, 孟凡荣, 周勇 . 基于链接密度聚类的重叠社区发现算法[J]. 计算机研究与发展, 2013,50(12): 2520-2530
	ZHU M , MENG F R , ZHOU Y . Density-based link clustering algorithm for overlapping community detection[J]. Journal of Computer Research and Development, 2013,50(12): 2520-2530.
[14]	BARBER M J , CLARK J W . Detecting network communities by propagating labels under constraints[J]. Physical Review E, 2009,80(2):026129
[15]	LIU X , MURATA T . Advanced modularity-specialized label propagation algorithm for detecting communities in networks[J]. Physica A:Statistical Mechanics and its Applications, 2010,389(7): 1493-1500.
[16]	LIU W , PELLEGRINI M , WANG X . Detecting communities based on network topology[J]. Scientific Reports, 2014,4(4): 5739-5739.
[17]	SHANG R H , LUO S , LI Y . Large-scale community detection based on node membership grade and sub-communities integration[J]. Physica A:Statistical Mechanics and its Applications, 2015,428: 279-294.
[18]	RADICCHI F , CASTELLANO C , CECCONI F . Defining and identifying communities in networks[J]. The National Academy of Sciences of the United States of America, 2004,101(9): 2658-2663.

Metrics

Recommended 0

No Suggested Reading articles found!

名称	节点数	边数
dolphins social network	62	159
American football	115	613
Email	1 133	5 451
Condmat2003	31 163	120 029
Amazon	334 863	925 872

社区集	节点集
1	2,38,46,90,104,106,26,34,110
2	3,7,48,14,16,33,65,101,40,61,107
3	4,6,11,53,103,41,75,85,99,82,73,108
4	1,5,17,10,94,42,24,105
5	8,9,23,52,79,78,22,109,112,69
6	12,51,60,25,70,98,64
7	13,32,19,27,15,35,44,62,39,55,86,72,100
8	20,30,56,80,31,95,36,102
9	18,96,57,28,63,88,66,21,71,97,77,114
10	29,50,47,59,68,89,74,54,84,115
11	43,37,83,81,91
12	45,58,49,93,67,87,92,76,111,113

社区集	节点集
1	2,26,46,110,34,90,38,106,104
2	4,41,11,108,75,6,85,53,73,82,103,99
3	30,20,31,56,80,36,81,95,102,83
4	54,68,84,74,89,50,47,115,111
5	8,112,23,22,79,52,78,9,109,69
6	7,76,45,49,64,59,98,58,60,87,93,113,92
7	18,88,96,71,21,97,77,57,63,66,28,114
8	55,72,39,19,86,43,44,35,15,32,100,62,13,27,37
9	3,7,14,16,65,61,107,40,33,101,48

数据集	LPA	LPAm+	CDMM-LPA
Email	82.1%	87.6%	97.1%
Condmat2003	69.7%	82.4%	91.2%
nc₃	78.3%	87.5%	94.8%

数据集	LPA/s	LPAm+/s	CDMM-LPA/s
dolphins social network	0.047	0.060	0.046
American football	0.047	0.125	0.109
Email	0.906	46.953	13.142
Condmat2003	48.583	2 157.413	247.257
Amazon	402.180	4 875.257	1 152.184
nc₃	5.752	162.175	36.138
nc₄	8.228	195.731	50.815

Research on label propagation algorithm based on modularity maximization in the social network

RichHTML

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

Figures/Tables 12

References 18

Related Articles 14

Metrics

Recommended 0

名称	mu	N	k	maxk	maxc	minc
nc₁	0.2	5 000	15	50	50	20
nc₂	0.4	5 000	15	50	50	20
nc₃	0.2	4 000	20	00	50	20
nc₄	0.2	5 000	20	00	50	20

[1]	Yang GAO, Hongli ZHANG. Survey on community detection method based on random walk [J]. Journal on Communications, 2023, 44(6): 198-210.
[2]	Yancui SHI,Yuan WANG,Qing ZHAO,Xiankun ZHANG. Research status of community detection based on local expansion [J]. Journal on Communications, 2019, 40(1): 149-162.
[3]	Qiang LIU,Yan JIA,Binxing FANG,Bin ZHOU,Yue HU,Jiuming HUANG. Research on the scalability of parallel community detection algorithms [J]. Journal on Communications, 2018, 39(4): 13-20.
[4]	Kun DENG,Wen-ping LI,Fa-hong YU,Jian-pei ZHANG. Overlapping community detection in complex networks based on multi kernel label propagation [J]. Journal on Communications, 2017, 38(2): 53-66.
[5]	Zhen-chao CHANG,Hong-chang CHEN,Rui-yang HUANG,Hong-tao YU,Yang LIU. Semi-supervised dynamic community detection based on non-negative matrix factorization [J]. Journal on Communications, 2016, 37(2): 132-143.
[6]	Kun GUO,Wen-zhong GUO,Qi-rong QIU,Qi-shan ZHANG. Community detection algorithm based on local affinity propagation and user profile [J]. Journal on Communications, 2015, 36(2): 68-79.
[7]	Tong WANG,Xin-lin ZHAO. Improved shuffled frog-leaping algorithm based network community detection method [J]. Journal on Communications, 2014, 35(Z2): 48-52.
[8]	. Improved shuffled frog-leaping algorithm based network community detection method [J]. Journal on Communications, 2014, 35(Z2): 8-52.
[9]	. Privacy leakage in online social networks based on public information [J]. Journal on Communications, 2013, 34(Z1): 25-196.
[10]	Shao-qing LV,Yu-qing ZHANG,Ping NI. Privacy leakage in online social networks based on public information [J]. Journal on Communications, 2013, 34(Z1): 190-196.
[11]	. Community based multi-copied data delivery scheme for delay tolerant sensor network [J]. Journal on Communications, 2013, 34(7): 20-183.
[12]	Bin FU,Ren-fa LI,Xiong-ren XIAO,Ya-wei HUANG. Community based multi-copied data delivery scheme for delay tolerant sensor network [J]. Journal on Communications, 2013, 34(7): 174-183.
[13]	. Efficient improving community structure strategy for enhancing Internet transmission performance [J]. Journal on Communications, 2013, 34(4): 21-179.
[14]	Jun CAI,Shun-zheng YU. Improving community structure strategy for efficiently enhancing Internet transmission performance [J]. Journal on Communications, 2013, 34(4): 171-179.