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

doi:10.11896/jsjkx.190200293

计算机科学 ›› 2019, Vol. 46 ›› Issue (12): 322-326.doi: 10.11896/jsjkx.190200293

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

付立东^1,2, 李丹¹, 李占利¹

(西安科技大学计算机科学与技术学院西安710054)¹;
(西安电子科技大学计算机科学与技术学院西安710071)²

收稿日期:2019-02-15 出版日期:2019-12-15 发布日期:2019-12-17
通讯作者: 付立东(1973-),男,博士,副教授,硕士生导师,主要研究方向为复杂网络、网络安全,E-mail:fulidong2005@163.com。
作者简介:李丹(1994-),女,硕士,主要研究方向为复杂网络;李占利(1964-),男,博士,教授,博士生导师,主要研究方向为大数据分析。
基金资助:
本文受国家自然科学基金(61432010,61502363),西安科技大学博士后科研启动项目(2018QDJ049)资助。

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

FU Li-dong^1,2, LI Dan¹, LI Zhan-li¹

(School of Computer Science & Technology,Xi’an University of Science and Technology,Xi’an 710054,China)¹;
(School of Computer Science & Technology,Xidian University,Xi’an 710071,China)²

Received:2019-02-15 Online:2019-12-15 Published:2019-12-17

摘要/Abstract

摘要： 重叠社团检测一直是复杂网络研究领域的重点和难点。由于真实网络普遍存在层次结构,结合层次性的重叠社团检测方法将更适用于现实世界复杂网络的研究分析,但目前这类方法的研究还比较少。因此,在定义复杂网络节点领导度、从属度概念的基础上,结合网络层次性建立数学模型,提出了新颖的从属度树检测重叠社团算法。该算法根据从属度值建立从属度树,通过划分树发现重叠节点和重叠社团。在人工网络实验中证明了从属度树算法可以结合层次性发现重叠节点,在Dolphin网络和Karate网络上的实验验证了其检测重叠社团结果的可靠性。与已有一些算法比较的结果表明,从属度树算法能找到其他算法不能找到的重叠节点,以扩展模块度和实际社团结构作为从属度树算法划分重叠社团结果的评价指标。新算法的扩展模块度值大于对比算法,社团划分结果更接近实际社团结构。

关键词: 从属度树, 分层网络, 复杂网络, 重叠社团

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

中图分类号:

TP399

付立东, 李丹, 李占利. 从属度树算法检测复杂网络重叠社团[J]. 计算机科学, 2019, 46(12): 322-326. https://doi.org/10.11896/jsjkx.190200293

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. https://doi.org/10.11896/jsjkx.190200293

参考文献

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

相关文章 15

[1]	郑文萍, 刘美麟, 杨贵. 一种基于节点稳定性和邻域相似性的社区发现算法 Community Detection Algorithm Based on Node Stability and Neighbor Similarity 计算机科学, 2022, 49(9): 83-91. https://doi.org/10.11896/jsjkx.220400146
[2]	何茜, 贺可太, 王金山, 林绅文, 杨菁林, 冯玉超. 比特币实体交易模式分析 Analysis of Bitcoin Entity Transaction Patterns 计算机科学, 2022, 49(6A): 502-507. https://doi.org/10.11896/jsjkx.210600178
[3]	杨波, 李远彪. 数据科学与大数据技术课程体系的复杂网络分析 Complex Network Analysis on Curriculum System of Data Science and Big Data Technology 计算机科学, 2022, 49(6A): 680-685. https://doi.org/10.11896/jsjkx.210800123
[4]	王本钰, 顾益军, 彭舒凡, 郑棣文. 融合动态距离和随机竞争学习的社区发现算法 Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning 计算机科学, 2022, 49(5): 170-178. https://doi.org/10.11896/jsjkx.210300206
[5]	陈世聪, 袁得嵛, 黄淑华, 杨明. 基于结构深度网络嵌入模型的节点标签分类算法 Node Label Classification Algorithm Based on Structural Depth Network Embedding Model 计算机科学, 2022, 49(3): 105-112. https://doi.org/10.11896/jsjkx.201000177
[6]	赵学磊, 季新生, 刘树新, 李英乐, 李海涛. 基于路径连接强度的有向网络链路预测方法 Link Prediction Method for Directed Networks Based on Path Connection Strength 计算机科学, 2022, 49(2): 216-222. https://doi.org/10.11896/jsjkx.210100107
[7]	李家文, 郭炳晖, 杨小博, 郑志明. 基于信息传播的致病基因识别研究 Disease Genes Recognition Based on Information Propagation 计算机科学, 2022, 49(1): 264-270. https://doi.org/10.11896/jsjkx.201100129
[8]	穆俊芳, 郑文萍, 王杰, 梁吉业. 基于重连机制的复杂网络鲁棒性分析 Robustness Analysis of Complex Network Based on Rewiring Mechanism 计算机科学, 2021, 48(7): 130-136. https://doi.org/10.11896/jsjkx.201000108
[9]	胡军, 王雨桐, 何欣蔚, 武晖栋, 李慧嘉. 基于复杂网络的全球航空网络结构分析与应用 Analysis and Application of Global Aviation Network Structure Based on Complex Network 计算机科学, 2021, 48(6A): 321-325. https://doi.org/10.11896/jsjkx.200900112
[10]	王学光, 张爱新, 窦炳琳. 复杂网络上的非线性负载容量模型 Non-linear Load Capacity Model of Complex Networks 计算机科学, 2021, 48(6): 282-287. https://doi.org/10.11896/jsjkx.200700040
[11]	马媛媛, 韩华, 瞿倩倩. 基于节点亲密度的重要性评估算法 Importance Evaluation Algorithm Based on Node Intimate Degree 计算机科学, 2021, 48(5): 140-146. https://doi.org/10.11896/jsjkx.200300184
[12]	殷子樵, 郭炳晖, 马双鸽, 米志龙, 孙怡帆, 郑志明. 群智体系网络结构的自治调节:从生物调控网络结构谈起 Autonomous Structural Adjustment of Crowd Intelligence Network: Begin from Structure of Biological Regulatory Network 计算机科学, 2021, 48(5): 184-189. https://doi.org/10.11896/jsjkx.210200161
[13]	刘胜久, 李天瑞, 谢鹏, 刘佳. 带权图的多重分形度量 Measure for Multi-fractals of Weighted Graphs 计算机科学, 2021, 48(3): 136-143. https://doi.org/10.11896/jsjkx.200700159
[14]	龚追飞, 魏传佳. 基于改进AdaBoost算法的复杂网络链路预测 Link Prediction of Complex Network Based on Improved AdaBoost Algorithm 计算机科学, 2021, 48(3): 158-162. https://doi.org/10.11896/jsjkx.200600075
[15]	龚追飞, 魏传佳. 基于拓扑相似和XGBoost的复杂网络链路预测方法 Complex Network Link Prediction Method Based on Topology Similarity and XGBoost 计算机科学, 2021, 48(12): 226-230. https://doi.org/10.11896/jsjkx.200800026

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

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

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

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0