并行社区发现算法的可扩展性研究

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

通信学报 ›› 2018, Vol. 39 ›› Issue (4): 13-20.doi: 10.11959/j.issn.1000-436x.2018052

并行社区发现算法的可扩展性研究

刘强¹(),贾焰¹,方滨兴^1,²,周斌¹,胡玥¹,黄九鸣¹

¹ 国防科技大学计算机学院，湖南长沙 410073
² 北京邮电大学计算机学院，北京 100876

修回日期:2017-12-02 出版日期:2018-04-01 发布日期:2018-04-29
作者简介:刘强（1981-），男，江苏句容人，国防科技大学博士生，主要研究方向为社交网络分析、数据挖掘、复杂网络等。|贾焰（1960-），女，四川成都人，国防科技大学教授、博士生导师，主要研究方向为社交网络分析、信息安全等。|方滨兴（1960-），男，江西万年人，中国工程院院士，北京邮电大学教授、博士生导师，主要研究方向为社交网络分析、信息安全等。|周斌（1971-），男，江西南昌人，国防科技大学教授、博士生导师，主要研究方向为社交网络分析、信息安全等。|胡玥（1993-），女，陕西宝鸡人，国防科技大学硕士生，主要研究方向为社交网络分析。|黄九鸣（1981-），男，福建安溪人，国防科技大学讲师，主要研究方向为社交网络分析、信息安全等。
基金资助:
国家重点研发计划基金资助项目(2017YFB0803303);国家自然科学基金资助项目(61502517);国家自然科学基金资助项目(61472438)

Research on the scalability of parallel community detection algorithms

Qiang LIU¹(),Yan JIA¹,Binxing FANG^1,²,Bin ZHOU¹,Yue HU¹,Jiuming HUANG¹

¹ College of Computer,National University of Defense Technology,Changsha 410073,China
² College of Computer,Beijing University of Posts and Telecommunications,Beijing 100876,China

Revised:2017-12-02 Online:2018-04-01 Published:2018-04-29
Supported by:
The National Key Research and Development Program of China(2017YFB0803303);The National Natural Science Foundation of China(61502517);The National Natural Science Foundation of China(61472438)

摘要/Abstract

摘要：

社交网络中往往蕴含着大量用户和群体信息，如话题演化模式、群体聚集效应以及信息传播规律等，对这些信息的挖掘成为社交网络分析的重要任务。社交网络的群体聚集效应作为社交网络的一种特征模式，表现为社交网络的社区结构特性。社区结构的发现已成为其他社交网络分析任务的基础和关键。随着在线社交网络用户数量的急剧增长，传统的社区发现手段已经难以适应，从而催生了并行社区发现技术的发展。对当前主流并行社区发现方法Louvain算法和标签传播算法在超大规模数据集上的可扩展性进行了研究，指出了各自的优缺点，为后续应用提供参考。

关键词: 社区发现, 并行算法, 可扩展性

Abstract:

The social network often contains a large amount of information about users and groups,such as topic evolution mode,group aggregation effect,the law of information dissemination and so on.The mining of these information has become an important task for social network analysis.As one characteristic of the social network,the group aggregation effect is characterized by the community structure of the social network.The discovery of community structure has become the basis and key point of other social network analysis tasks.With the rapid growth of the number of online social network users,the traditional community detection methods have been difficult to be used,which contributes to the development of parallel community detection technology.The current mainstream parallel community detection methods,including Louvain algorithm and label propagation algorithm,were tested in the large-scale data sets,and corresponding advantages and disadvantages were pointed out so as to provide useful information for later applications.

Key words: community detection, parallel algorithm, scalability

中图分类号:

TP311

刘强,贾焰,方滨兴,周斌,胡玥,黄九鸣. 并行社区发现算法的可扩展性研究[J]. 通信学报, 2018, 39(4): 13-20.

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.

图/表 10

表1

表2

图1

图2

图3

图4

图5

图6

图7

图8

参考文献 28

[1]	李建华, 汪晓锋, 吴鹏 . 基于局部优化的社区发现方法研究现状[J]. 中国科学院院刊, 2015,30(2): 238-247.
	LI J H , WANG X F , WU P . Review on community detection methods based on local optimization[J]. Bulletin of Chinese Academy of Sciences, 2015,30(2): 238-247.
[2]	CORNEIL D G , GOTLIEB C C . An efficient algorithm for graph isomorphism[J]. Journal of the ACM, 1970,17(1): 51-64.
[3]	NEWMAN M E J . Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004,69(6):066133.
[4]	NEWMAN M E J , . Modularity and community structure in networks[C]// The National Academy of Sciences of the United States of America. 2006: 8577-8582.
[5]	ROSVALL M , BERGSTROM C T . Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems[J]. Plos One, 2011,6(4):e18209.
[6]	NEWMAN M E J . Spectral methods for community detection and graph partitioning[J]. Physical Review E , 2013,88(4):042822.
[7]	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.
[8]	赵卓翔, 王轶彤, 田家堂 ,等. 社会网络中基于标签传播的社区发现新算法[J]. 计算机研究与发展, 2011,48(S3): 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(S3): 8-15.
[9]	刘世超, 朱福喜, 甘琳 . 基于标签传播概率的重叠社区发现算法[J]. 计算机学报, 2016,39(4): 717-729.
	LIU S C , ZHU F X , GAN L . A label-propagation-probability-based algorithm for overlapping community detection[J]. Chinese Journal of Computers, 2016,39(4): 717-729.
[10]	LANCICHINETTI A , FORTUNATO S,KERTéSZ J . Detecting the overlapping and hierarchical community structure in complex networks[J]. New Journal of Physics, 2009,11(3):033015.
[11]	LIU Q , LIU C , WANG J ,et al. Evolutionary link community structure discovery in dynamic weighted networks[J]. Physica A:Statistical Mechanics and its Applications, 2017,466: 370-388.
[12]	FARKAS I , áBEL D , PALLA G . Weighted network modules[J]. New Journal of Physics, 2007,9(6):180.
[13]	高学东, 王立敏, 马红权 ,等. 基于共享最近邻探测社团结构的算法[J]. 系统工程理论与实践, 2009,29(10): 102-109.
	GAO X D , WANG L M , MA H Q ,et al. Detecting community structure based on shared nearest neighbor[J]. Systems Engineering Theory and Practice, 2009,29(10): 102-109.
[14]	刘文远, 王佳楠, 王林 . 基于局部扩张查询的重叠社区发现[J]. 小型微型计算机系统, 2015,36(10): 2229-2234.
	LIU W Y , WANG J N , WANG L . Community detection based on local expansion query[J]. Journal of Chinese Computer Systems, 2015,36(10): 2229-2234.
[15]	WICKRAMAARACHCHI C , FRINCU M , SMALL P ,et al. Fast parallel algorithm for unfolding of communities in large graphs[C]// 2014 IEEE High Performance Extreme Computing Conference (HPEC). 2014: 1-6.
[16]	乔少杰, 郭俊, 韩楠 ,等. 大规模复杂网络社区并行发现算法[J]. 计算机学报, 2017,40(3): 687-700.
	QIAO S J , GUO J , HAN N ,et al. Parallel algorithm for discovering communities in large-scale complex networks[J]. Chinese Journal of Computers, 2017,40(3): 687-700.
[17]	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(10):P10008.
[18]	STAUDT C L , MEYERHENKE H . Engineering parallel algorithms for community detection in massive networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2016,27(1): 171-184.
[19]	LU H , HALAPPANAVAR M , KALYANARAMAN A . Parallel heuristics for scalable community detection[J]. Parallel Computing, 2015,47: 19-37.
[20]	AKSHAY U B . Scalable community detection using label propagation and map-reduce[R]. 2012.
[21]	从玉相 . 基于MapReduce的社区挖掘算法[D]. 上海:上海交通大学, 2013.
	CONG Y X . Community detection based on MapReduce[D]. Shanghai:Shanghai Jiao Tong University, 2013.
[22]	ZHANG Q , QIU Q , GUO W ,et al. A social community detection algorithm based on parallel grey label propagation[J]. Computer Networks, 2016,107: 133-143.
[23]	BAE S H , HOWE B . GossipMap:a distributed community detection algorithm for billion-edge directed graphs[C]// The International Conference for High Performance Computing,Networking,Storage and Analysis. 2015: 1-12.
[24]	李春英, 汤庸, 林海 ,等. 基于标签传播的可并行复杂网络重叠社区发现算法[J]. 中国科学:信息科学, 2016,2: 212-227.
	LI C Y , TANG Y , LIN H ,et al. Parallel overlapping community detection algorithm in complex network based on label propagation[J]. Science China Information Sciences, 2016,2: 212-227.
[25]	PENG C , ZHANG Z , WONG K C ,et al. A scalable community detection algorithm for large graphs using stochastic block models[C]// The 24th International Joint Conference on Artificial Intelligence. 2015: 2090-2096.
[26]	YANG J , LESKOVEC J . Defining and evaluating network communities based on ground-truth[J]. Knowledge and Information Systems, 2012,42(1): 181-213.
[27]	KWAK H , LEE C , PARK H ,et al. What is Twitter,a social network or a news media?[C]// The 19th International Conference on World Wide Web. 2010: 591-600.
[28]	LEUNG I X Y , HUI P , LIO P ,et al. Towards real-time community detection in large networks[J]. Physical Review E, 2009,79(6):066107.

测试数据	节点数/个	边数/条
Orkut数据集	3 072 441	117 185 083
Sina数据集1	20 000 000	269 117 041
Sina数据集2	115 205 577	3 504 379 868
Twitter数据集	48 012 340	1 468 365 182

并行社区发现算法的可扩展性研究

Research on the scalability of parallel community detection algorithms

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 28

相关文章 13

Metrics

推荐阅读 0

[1]	高阳, 张宏莉. 基于随机游走的社区发现方法综述[J]. 通信学报, 2023, 44(6): 198-210.
[2]	陈浩, 杨芫, 徐明伟, 裴丹, 尤艺霖. 支持多模态网络的可扩展异构服务功能链并行编排部署系统[J]. 通信学报, 2022, 43(9): 1-11.
[3]	胡志蕊, 毕美华, 许方敏, 何美霖, 郑长亮. 基于APG合并及拓扑势优化的启发式用户关联策略[J]. 通信学报, 2022, 43(6): 98-107.
[4]	吉祖勤,沈军,丁德林,崔效玮. 可扩展网络服务模型的服务扩展能力分析[J]. 通信学报, 2019, 40(5): 39-46.
[5]	史艳翠,王嫄,赵青,张贤坤. 基于局部扩展的社区发现研究现状[J]. 通信学报, 2019, 40(1): 149-162.
[6]	付永红,毕军,张克尧,吴建平. 软件定义网络可扩展性研究综述[J]. 通信学报, 2017, 38(7): 141-154.
[7]	陈晶,万云. 社交网络中基于模块度最大化的标签传播算法的研究[J]. 通信学报, 2017, 38(2): 25-33.
[8]	周爱平，程光，郭晓军，朱琛刚. 长持续时间数据流的并行检测算法[J]. 通信学报, 2015, 36(11): 156-166.
[9]	吕少卿1，张玉清1,2，倪平2. 基于公开信息的社交网络隐私泄露[J]. 通信学报, 2013, 34(Z1): 25-196.
[10]	吕少卿,张玉清,倪平. 基于公开信息的社交网络隐私泄露[J]. 通信学报, 2013, 34(Z1): 190-196.
[11]	杨望,龚俭,吴雄. 基于同步点的IDS评估评分方法[J]. 通信学报, 2008, 29(9): 1-9.
[12]	柳薇,马争鸣. 网络视频编码技术[J]. 通信学报, 2005, 26(9): 85-92.
[13]	陈庆奎,那丽春. 基于动态冗余机制的数据并行型计算网格模型[J]. 通信学报, 2005, 26(12): 110-116.

源节点	目标节点
1	2
2	3
2	4
3	5
#	#