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

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

通信学报 ›› 2017, Vol. 38 ›› Issue (2): 25-33.doi: 10.11959/j.issn.1000-436x.2017025

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

陈晶^1,²,万云¹

¹ 燕山大学信息科学与工程学院，河北秦皇岛 066004
² 河北省虚拟技术与系统集成重点实验室，河北秦皇岛 066004

修回日期:2016-12-23 出版日期:2017-02-01 发布日期:2017-07-20
作者简介:陈晶（1976-），女，黑龙江哈尔滨人，博士，燕山大学副教授，主要研究方向为社交网络、对等网络和Web服务等。|万云（1990-），女，山西晋城人，燕山大学硕士生，主要研究方向为社交网络和数据挖据。
基金资助:
国家自然科学基金资助项目(61602401);国家自然科学基金资助项目(61472340);河北省自然科学基金资助项目(F2014203192)

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

Jing CHEN^1,²,Yun WAN¹

¹ College of Information Science and Engineering,Yanshan University,Qinhuangdao 066004,China
² Key Laboratory for Computer Virtual Technology and System Integration of Hebei Province,Qinhuangdao 066004,China

Revised:2016-12-23 Online:2017-02-01 Published:2017-07-20
Supported by:
The National Natural Science Foundation of China(61602401);The National Natural Science Foundation of China(61472340);The Natural Science Founda-tion of Hebei Province(F2014203192)

摘要/Abstract

摘要：

提出了一种利用模块度最大化与社区结构属性相结合的社区发现方法。首先，针对基于模块度最大化的标签传播算法中存在的时间复杂度高的问题，引入传播距离参数，依据“先传播，后合并”的原则，降低了社区合并导致整个网络需要更新带来的较高时间复杂度；其次，结合社区结构的概念提出了基于模块度最大化的标签传播算法（CDMM-LPA）；最后，基于网络数据集，验证并分析了 CDMM-LPA 算法的可行性。实验结果表明，CDMM-LPA算法在降低了时间复杂度的同时，获得了较高的模块度值和更加稳定的强社区结构。

关键词: 模块度, 传播距离, 社区结构, 标签传播, 社区发现

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

中图分类号:

TP301.6

陈晶,万云. 社交网络中基于模块度最大化的标签传播算法的研究[J]. 通信学报, 2017, 38(2): 25-33.

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.

图/表 12

图1

图2

图3

图4

表1

表2

表3

表4

图5

表5

表6

表7

参考文献 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.

名称	节点数	边数
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

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 18

相关文章 12

Metrics

推荐阅读 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]	高阳, 张宏莉. 基于随机游走的社区发现方法综述[J]. 通信学报, 2023, 44(6): 198-210.
[2]	史艳翠,王嫄,赵青,张贤坤. 基于局部扩展的社区发现研究现状[J]. 通信学报, 2019, 40(1): 149-162.
[3]	刘强,贾焰,方滨兴,周斌,胡玥,黄九鸣. 并行社区发现算法的可扩展性研究[J]. 通信学报, 2018, 39(4): 13-20.
[4]	邓琨,李文平,余法红,张健沛. 基于多核心标签传播的复杂网络重叠社区识别方法[J]. 通信学报, 2017, 38(2): 53-66.
[5]	王桐，赵昕琳. 基于改进蛙跳算法的社区划分方法[J]. 通信学报, 2014, 35(Z2): 8-52.
[6]	董学文，杨超，盛立杰，马建峰. ESYN：基于动态模型的高效同步聚类算法[J]. 通信学报, 2014, 35(Z2): 12-93.
[7]	王桐,赵昕琳. 基于改进蛙跳算法的社区划分方法[J]. 通信学报, 2014, 35(Z2): 48-52.
[8]	董学文,杨超,盛立杰,马建峰. ESYN：基于动态模型的高效同步聚类算法[J]. 通信学报, 2014, 35(Z2): 86-93.
[9]	吕少卿1，张玉清1,2，倪平2. 基于公开信息的社交网络隐私泄露[J]. 通信学报, 2013, 34(Z1): 25-196.
[10]	吕少卿,张玉清,倪平. 基于公开信息的社交网络隐私泄露[J]. 通信学报, 2013, 34(Z1): 190-196.
[11]	蔡君,余顺争. 有效提高Internet传输性能的社团结构改善策略[J]. 通信学报, 2013, 34(4): 171-179.
[12]	蔡君1,2，余顺争2. 有效提高Internet传输性能的社团结构改善策略[J]. 通信学报, 2013, 34(4): 21-179.