Parallel Algorithm for Overlapping Community Detection in Complex Networks

TENG Fei; DAI Rongjie; REN Xiaochun

doi:10.3969/j.issn.0258-2724.20160478

Volume 54 Issue 1

Feb. 2019

Turn off MathJax

Article Contents

Abstract

References

Journal of Southwest Jiaotong University > 2019 > 54(1): 211-218.

TENG Fei, DAI Rongjie, REN Xiaochun. Parallel Algorithm for Overlapping Community Detection in Complex Networks[J]. Journal of Southwest Jiaotong University, 2019, 54(1): 211-218. doi: 10.3969/j.issn.0258-2724.20160478

Citation:

TENG Fei, DAI Rongjie, REN Xiaochun. Parallel Algorithm for Overlapping Community Detection in Complex Networks[J]. Journal of Southwest Jiaotong University, 2019, 54(1): 211-218. doi: 10.3969/j.issn.0258-2724.20160478

Citation:

PDF( 706 KB)

Parallel Algorithm for Overlapping Community Detection in Complex Networks

doi: 10.3969/j.issn.0258-2724.20160478

TENG Fei^{1,2
,},
DAI Rongjie¹,
REN Xiaochun^{2
,
,}

Received Date: 18 Apr 2016
Rev Recd Date: 21 Mar 2018

Available Online: 27 Mar 2018

Publish Date: 01 Feb 2019

Abstract

Abstract

With the increasing size of complex networks, traditional detection methods are difficult to scale to larger networks. This paper proposes a parallel hierarchical link（PHLink） algorithm to discover overlapping communities. By studying the power-law degree distribution of complex networks, we distinguish the motivations of why two nodes intend to establish a connection so that the complexity for community detection can be reduced. PHLink is implemented using distributed computing for large-scale networks via graph segmentation and redundant storage. Experiments validate that PHLink can accurately discover network communities and the overlaps between them. For scale-free networks, removing 0.1% of the hub nodes reduces the computation time by 94%. Meanwhile, PHLink demonstrates good speed-up and scale-up on Hadoop, which can scale to very large complex networks with millions of edges.
- complex network,
- overlapping community,
- community detection,
- scale-free,
- parallel algorithm,
- Hadoop

FullText(HTML)

References(14)

References

PALLA G, DERÉNYI I, FARKAS I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043): 814-818

ADAMCSEK B, PALLA G, FARKAS I J, et al. CFinder:locating cliques and overlapping modules in biological networks[J]. Bioinformatics, 2006, 22(8): 1021-1023 doi: 10.1093/bioinformatics/btl039

LANCICHINETTI A, FORTUNATO S, KERTESZ J. Detecting the overlapping and hierarchical community structure in complex networks[J]. New Journal of Physicals, 2008, 11（3）: 19-44

李首庆,徐洋. 基于自适应聚概率矩阵的JPDA算法研究[J]. 西南交通大学学报,2017,52(2): 340-347 doi: 10.3969/j.issn.0258-2724.2017.02.018

LI Shouqing, XU Yang. Joint probabilistic data association algorithm based on adaptive cluster probability matrix[J]. Journal of Southwest Jiaotong University, 2017, 52(2): 340-347 doi: 10.3969/j.issn.0258-2724.2017.02.018

刘世超,朱福喜,甘琳. 基于标签传播概率的重叠社区发现算法[J]. 计算机学报,2016,39(4): 717-729

LIU Shichao, ZHU Fuxi, GAN Lin. A label-propagation probability based algorithm for overlappling community detection[J]. Chinese Journal of Computers, 2016, 39(4): 717-729

YANG J, LESKOVEC J. Overlapping communities explain core-periphery organization of networks[J]. Proceedings of the IEEE, 2014, 102(12): 1892-1902 doi: 10.1109/JPROC.2014.2364018

WANG X, LIU G, LI J, et al. Locating structural centers:a density-based clustering method for community detection[J]. Plos One, 2017, 12(1): e0169355 doi: 10.1371/journal.pone.0169355

AHN Y Y, BAGROW J P, LEHMANN S. Link communities reveal multiscale complexity in networks[J]. Nature, 2010, 466(7307): 761-764 doi: 10.1038/nature09182

SUN H, LIU J, HUANG J, et al. LinkLPA:a link-based label propagation algorithm for overlapping community detection in networks[J]. Computational Intelligence, 2017, 33(2): 308-331 doi: 10.1111/coin.12087

乔少杰,郭俊,韩楠,等. 大规模复杂网络社区并行发现算法[J]. 计算机学报,2017,40(3): 687-700

QIAO Shaojie, GUO Jun, HAN Nan, et al. Parallel algorithm for discovering communities in large-scale complex networks[J]. Chinese Journal of Computers, 2017, 40(3): 687-700

BU Z, WU Z, CAO J, et al. Local community mining on distributed and dynamic networks from a multiagent perspective[J]. IEEE Transactions on Cybernetics, 2017, 46(4): 986-999

CLAUSET A, SHALIZI C R, NEWMAN M E J. Power-law distributions in empirical data[J]. Siam Review, 2012, 51(4): 661-703

YANG J, LESKOVEC J. Defining and evaluating network communities based on ground-truth[J]. Knowledge & Information Systems, 2012, 42(1): 745-754

CLAUSET A, NEWMAN M E J, MOORE C. Finding community structure in very large networks[J]. Physical Review E, 2004, 70(2): 066111-1-066111-6

Relative Articles

[1]	TIAN Wen, ZHOU Xuefang, FANG Qin, SONG Jinjin. Vulnerability Analysis of En-route Network Based on Cascading Failure[J]. Journal of Southwest Jiaotong University. doi: 10.3969/j.issn.0258-2724.20220755
[2]	TIAN Wen, FANG Qin, ZHOU Xuefang, SONG Jinjin. Identification Method for Key Nodes in En-Route Network[J]. Journal of Southwest Jiaotong University, 2025, 60(1): 233-242. doi: 10.3969/j.issn.0258-2724.20220532
[3]	SHEN Li, ZHANG Dianye, XIANG Yang, WANG Zhouquan, ZHANG Tong. Simulation on Survivability and Cascading Failure Propagation of Urban Subway-Bus Compound Network[J]. Journal of Southwest Jiaotong University, 2018, 53(1): 156-163, 196. doi: 10.3969/j.issn.0258-2724.2018.01.019
[4]	HU Yingyue, CHEN Feng, CHEN Peiwen, WANG Zijia. Critical Station Identification Based on Passenger Propagation in Urban Mass Transit Network[J]. Journal of Southwest Jiaotong University, 2017, 30(6): 1193-1200,1215. doi: 10.3969/j.issn.0258-2724.2017.06.021
[5]	WANG Hui, WU Mingli, LI Wenfeng, WANG Guanhong, LI Ying, TAO Xiangyu. Detection Method of Low-Frequency Oscillation in Traction Power Supply System Based on Single-Phase dq Transformation and Improved PRONY Algorithm[J]. Journal of Southwest Jiaotong University, 2016, 29(5): 878-885. doi: 10.3969/j.issn.0258-2724.2016.05.009
[6]	QIAO Hong, XIA He, DU Xianting. Analytical Method for Calculating Dynamic Response of Coupled Train-Bridge System Based on Duhamel Integral[J]. Journal of Southwest Jiaotong University, 2014, 27(5): 766-771. doi: 10.3969/j.issn.0258-2724.2014.05.004
[7]	FAN Wenli, LIU Zhigang. Ranking Method for Node Importance Based on Efficiency Matrix[J]. Journal of Southwest Jiaotong University, 2014, 27(2): 337-342. doi: 10.3969/j.issn.0258-2724.2014.02.023
[8]	HU Yucong, CHEN Haiwei. Algorithm for Detecting Modular Structures and Diagnosing Hub Sections in Urban Road Network[J]. Journal of Southwest Jiaotong University, 2014, 27(4): 706-711. doi: 10.3969/j.issn.0258-2724.2014.04.023
[9]	YAO Hongguang. Multi-resolution Wavelet Decomposition of Chinese Aviation Network[J]. Journal of Southwest Jiaotong University, 2013, 26(1): 141-146. doi: 10.3969/j.issn.0258-2724.2013.01.022
[10]	GUO Wei, WANG Xiaomin, LIU Jing, HE Dake. One-Way Hash Function Construction Based on Chaotic Message Expansion[J]. Journal of Southwest Jiaotong University, 2010, 23(5): 751-757. doi: 10. 3969/ j. issn. 0258-2724.
[11]	CHEN Jing, SUN Linfu. Evaluation of Node Importance in Complex Networks[J]. Journal of Southwest Jiaotong University, 2009, 22(3): 426-429.
[12]	ZHAO Yue, DU Wen, CHEN Shuang. Evolving Model for Scale-Free Network Based on Travel Choice[J]. Journal of Southwest Jiaotong University, 2008, 21(4): 531-534.
[13]	GUO Qiang, LI Lyo, GUO Yaohuang. Routing Optimization for School Bus Problem[J]. Journal of Southwest Jiaotong University, 2006, 19(4): 486-490.
[14]	LIANG Chun-yong, . Listless SPIHT Image Coding Hardware Algorithm Based on LiftingW avelet[J]. Journal of Southwest Jiaotong University, 2005, 18(4): 492-496.
[15]	YANG Shou-jian. Homoclinic Orbits for a Singular Second Order Planar Hamiltonian System[J]. Journal of Southwest Jiaotong University, 2004, 17(6): 761-763.
[16]	PAN Su, LIU Shu-guang, QIU Bo. Performance Analysis of Multi-code CDMA ALOHA System[J]. Journal of Southwest Jiaotong University, 2004, 17(6): 768-771.
[17]	ZHAO Yu-lin, PENG Qiang, WUXiao-xiong. Study on Parallel Algorithm in H.26L Video Encoder[J]. Journal of Southwest Jiaotong University, 2003, 16(4): 428-432.
[18]	LIUWei, ZHUChang-qian. A New Algorithm for Hard-Decision Parallel Interference Cancellation[J]. Journal of Southwest Jiaotong University, 2002, 15(3): 286-289.
[19]	TANGLin-yong. Generalization of the Accurate Hayman Inequality[J]. Journal of Southwest Jiaotong University, 2001, 14(3): 229-231.
[20]	DU Wen, LIN Shu-rong, ZΗΟUXian-wei. Batch Parallel Algorithm of Assignment Problem of Dynamic Transportation Network Flows for System Optimization[J]. Journal of Southwest Jiaotong University, 2001, 14(5): 453-456.

Supplements(0)

Cited By

Cited by

Periodical cited type(4)

1.	韩永印，王侠，王志晓. 基于节点影响值的社区网络稳定标签传播算法. 沈阳工业大学学报. 2024(02): 184-190 .
2.	彭慧豪，张怡欣，李文豪，刘天宇. 基于复杂网络的社区检测算法研究. 信息技术与信息化. 2024(11): 153-157 .
3.	柴变芳，欧朋成，胡吉朝. 基于Spark的大规模网络结构发现算法. 计算机应用研究. 2021(02): 409-413 .
4.	张玲，吴发辉. 基于多模态融合的加权网络重叠社区划分算法. 黑龙江工业学院学报(综合版). 2021(08): 98-103 .

Other cited types(3)

Proportional views

Proportional views

通讯作者: 陈斌, bchen63@163.com

1.
沈阳化工大学材料科学与工程学院沈阳 110142

Figures(2) / Tables(4)

Get Citation

PDF

XML

Article views(571) PDF downloads(26)