从属度树算法检测复杂网络重叠社团

doi:10.11896/jsjkx.190200293

Abstract

Abstract: Overlapping community detection is a key and difficult issue in complex network research field.Due to the widespread hierarchical structures in real networks,the hierarchical overlapping community detection methods are more suitable for studying and analyzing complex networks in the real world.However,these researches of this kind of method are not many now.This paper proposed a new overlapping community detection algorithm named following-degree tree based on the definition of complex network node leadership and subordination concept.Combined with the hierarchical characteristic,this algorithm constructs the following-degree tree by calculating the following degree of eve-ry nodes and finally finds the overlapping nodes and overlapping communities by dividing the tree.The feasibility of the algorithm was proved by an artificial network experiment,and its effectiveness was verified by the experiments on Dolphin network and Karate network.The proposed algorithm has high extended modularity and more reasonable division,which can find overlapping nodes that other algorithms cannot find.

Key words: Complex networks, Following-degree tree, Hierarchical networks, Overlapping community

CLC Number:

TP399

FU Li-dong, LI Dan, LI Zhan-li. Following-degree Tree Algorithm to Detect Overlapping Communities in Complex Networks[J].Computer Science, 2019, 46(12): 322-326.

References

[1]FU L D,NIE J J.Dynamic Community Detection Based on Evolutionary Spectral Method [J].Computer Science,2018,45(2):171-174.(in Chinese)
付立东,聂靖靖.基于进化谱分方法的动态社团检测[J].计算机科学,2018,45(2):171-174.
[2]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.
[3]FARKAS I,ÁBEL D,PALLA G,et al.Weighted network mo- dules [J].New Journal of Physics,2007,9(6):180.
[4]LANCICHINETTI A,FORTUNATO S,KERTÉSZ J.Detecting the overlapping and hierarchical community structure of complex networks [J].New Journal of Physics,2009,11(3):19-44.
[5]ZHANG J P,DING X Y,YANG J.Revealing the role of node similarity and community merging in community detection [J].Knowledge-Based Systems,2019,165:407-419.
[6]LANCICHINETTI A,FORTUNATO S.Benchmarks for tes- ting community detection algorithms on directed and weighted graphs with overlapping communities [J].Physical Review E,2009,80(1):016118.
[7]ELYASI M,MEYBODI M,REZVANIAN A,et al.A fast algorithm for overlapping community detection[C]//Eighth International Conference on Information and Knowledge Technology.Hamedan,Iran:IEEE,2016.
[8]DENG K,LI W P,YU F H,et al.Overlapping community detection in complex networks based on multi kernel label propagation [J].Journal on Communications,2017,38(2):53-66.(in Chinese)
邓琨,李文平,余法红,等.基于多核心标签传播的复杂网络重叠社区识别方法[J].通信学报,2017,38(2):53-66.
[9]WANG Y,YANG Y,ZHENG Z,et al.An overlapping community detection algorithm based on hierarchical label of semantic[C]//International Conference on Future Information Enginee-ring.Beijing,China:IERI Procedia,2014.
[10]JIN H,YU W,LI S J.Graph regularized nonnegative matrix tri-factorization for overlapping community detection [J].Physica A:Statistical Mechanics and its Applications,2019,515(C):376-387.
[11]LI X M,XU G Q,TANG M H.Community detection for multi-layer social network based on local random walk [J].Journal of Visual Communication and Image Representation,2018,57:91-98.
[12]ZHOU H F,ZHANG Y,LI J.An overlapping community detection algorithm in complex networks based on information theory [J].Data & Knowledge Engineering,2018,117:183-194.
[13]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,2008(10):P10008.
[14]WU Z,LIN Y,WAN H,et al.Efficient overlapping community detection in huge real-world networks [J].Physica A Statistical Mechanics & Its Applications,2012,391(7):2475-2490.
[15]WU Z H,LIN Y F,WAN H Y,et al.An efficient method to find overlapping communities in networks [J].Journal of Computational Information Systems,2011,7(16):5650-5659.
[16]HUANG L,WANG G,WANG Y,et al.Link Clustering with Extended Link Similarity and EQ Evaluation Division [J].Plos One,2013,8(6):e66005.
[17]AHN Y Y,BAGROW J P,LEHMANN S.Link communities reveal multiscale complexity in networks [J].Nature,2010,466(7307):761.
[18]MA X,SUN P G,ZHANG Z Y.An integrative framework for protein interaction network and methylation data to discover epi-genetic modules [J].IEEE/ACM Transactions on ComputationalBiology & Bioinformatics (Early Access),2018,PP(99):1-1.
[19]MA X,SUN P,QIN G.Identifying condition-specific modules by clustering multiple networks [J].IEEE/ACM Transactions on Computational Biology & Bioinformatics,2018,15(5):1636-1648.
[20]BAI L,LIANG J,DU H,et al.A novel community detection algorithm based on simplification of complex networks [J].Knowledge-Based Systems,2018,143:58-64.
[21]XIE J,SZYMANSKI B K,LIU X.SLPA:Uncovering Overlapping Communities in Social Networks via a Speaker-Listener Interaction Dynamic Process[C]//2011 11th IEEE International Conference on Data Mining Workshops.Vancouver,Canada:IEEE Computer Society,2011.

Related Articles 15

[1]	LI Jia-wen, GUO Bing-hui, YANG Xiao-bo, ZHENG Zhi-ming. Disease Genes Recognition Based on Information Propagation [J]. Computer Science, 2022, 49(1): 264-270.
[2]	CHEN Xiang-tao, ZHAO Mei-jie, YANG Mei. Overlapping Community Detection Algorithm Based on Subgraph Structure [J]. Computer Science, 2021, 48(9): 244-250.
[3]	WANG Xue-guang, ZHANG Ai-xin, DOU Bing-lin. Non-linear Load Capacity Model of Complex Networks [J]. Computer Science, 2021, 48(6): 282-287.
[4]	MA Yuan-yuan, HAN Hua, QU Qian-qian. Importance Evaluation Algorithm Based on Node Intimate Degree [J]. Computer Science, 2021, 48(5): 140-146.
[5]	YIN Zi-qiao, GUO Bing-hui, MA Shuang-ge, MI Zhi-long, SUN Yi-fan, ZHENG Zhi-ming. Autonomous Structural Adjustment of Crowd Intelligence Network: Begin from Structure of Biological Regulatory Network [J]. Computer Science, 2021, 48(5): 184-189.
[6]	ZHAO Man-yu, YE Jun. Synchronization of Uncertain Complex Networks with Sampled-data and Input Saturation [J]. Computer Science, 2021, 48(11A): 481-484.
[7]	LOU Zheng-zheng, WANG Guan-wei, LI Hui, WU Yun-peng. Community Mining Based on KL-Ball [J]. Computer Science, 2021, 48(11A): 236-243.
[8]	NING Yi-xin, XIE Hui, JIANG Huo-wen. Survey of Graph Neural Network in Community Detection [J]. Computer Science, 2021, 48(11A): 11-16.
[9]	XUE Lei, TANG Xu-qing. Algorithm for Detecting Overlapping Communities Based on Centered Cliques [J]. Computer Science, 2020, 47(8): 157-163.
[10]	ZHANG Qin, CHEN Hong-mei, FENG Yun-fei. Overlapping Community Detection Method Based on Rough Sets and Density Peaks [J]. Computer Science, 2020, 47(5): 72-78.
[11]	WANG Shuai-hui, HU Gu-yu, PAN Yu, ZHANG Zhi-yue, ZHANG Hai-feng, PAN Zhi-song. Community Detection in Signed Networks with Game Theory [J]. Computer Science, 2020, 47(11A): 449-453.
[12]	ZHANG Qin, CHEN Hong-mei, FENG Yun-fei. Overlapping Community Detection Method Based on Rough Sets and Distance Dynamic Model [J]. Computer Science, 2020, 47(10): 75-82.
[13]	ZHAO Lei, ZHOU Jin-he. ICN Energy Efficiency Optimization Strategy Based on Content Field of Complex Networks [J]. Computer Science, 2019, 46(9): 137-142.
[14]	LIU Xiao-dong, WEI Hai-ping, CAO Yu. Modeling and Stability Analysis for SIRS Model with Network Topology Changes [J]. Computer Science, 2019, 46(6A): 375-379.
[15]	LIU Chun, ZHANG Guo-liang. Software Feature Extraction Method Based on Overlapping Community Detection [J]. Computer Science, 2019, 46(12): 201-207.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

Following-degree Tree Algorithm to Detect Overlapping Communities in Complex Networks

PDF (PC)