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

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

Abstract

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

CLC Number:

TP311

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.

Figures/Tables 10

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

测试数据	节点数/个	边数/条
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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 28

Related Articles 15

Metrics

Recommended 0

[1]	Yang GAO, Hongli ZHANG. Survey on community detection method based on random walk [J]. Journal on Communications, 2023, 44(6): 198-210.
[2]	Hao CHEN, Yuan YANG, Mingwei XU, Dan PEI, Yilin YOU. Parallel orchestration and deployment system for scalable heterogeneous service function chain supporting polymorphic network [J]. Journal on Communications, 2022, 43(9): 1-11.
[3]	Zhirui HU, Meihua BI, Fangmin XU, Meilin HE, Changliang ZHENG. APG mergence and topological potential optimization based heuristic user association strategy [J]. Journal on Communications, 2022, 43(6): 98-107.
[4]	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.
[5]	Yong-hong FU,Jun BI,Ke-yao ZHANG,Jian-ping WU. Scalability of software defined network [J]. Journal on Communications, 2017, 38(7): 141-154.
[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.
[7]	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.
[8]	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.
[9]	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.
[10]	. Parallel detection algorithm on long duration data streaming [J]. Journal on Communications, 2015, 36(11): 156-166.
[11]	. Improved shuffled frog-leaping algorithm based network community detection method [J]. Journal on Communications, 2014, 35(Z2): 8-52.
[12]	Tong WANG,Xin-lin ZHAO. Improved shuffled frog-leaping algorithm based network community detection method [J]. Journal on Communications, 2014, 35(Z2): 48-52.
[13]	. Privacy leakage in online social networks based on public information [J]. Journal on Communications, 2013, 34(Z1): 25-196.
[14]	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.
[15]	Jie HUANG,Bei HUANG. Public key based key distribution scheme for wireless sensor networks [J]. Journal on Communications, 2011, 32(10): 52-58.

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