计算机科学 ›› 2020, Vol. 47 ›› Issue (6A): 461-466.doi: 10.11896/JsJkx.191100215
董明刚, 弓佳明, 敬超
DONG Ming-gang, GONG Jia-ming and JING Chao
摘要： 多目标优化算法在复杂网络社区发现中具有很强的竞争力,然而,在处理社区结构较为模糊、网络数据规模大的问题时难以得到满意的效果。为克服现有多目标方法的不足,提出一种基于谱聚类的多目标复杂网络社区发现算法。该算法先用谱聚类对编码后的复杂网络进行初始种群划分,利用子图聚类特性生成高质量的初始种群。采用一种网格约简的数据归减方法在进化过程中对种群进行约减,有效降低算法复杂度,以满足大规模网络社区发现需求。在仿真网络和9个真实网络上的实验结果表明,该算法在社区发现精度性能和计算复杂度方面,都要优于MRMOEA,RMOEA,MCMOEA 3种代表性的基于多目标的社区发现算法。
中图分类号:
| [1] PALLA G.CFinder:locating cliques and overlapping modules in biological networks.Bioinformatics,2006,22(8):1021-1023. [2] PIZZUTI C,ROMBO S E.Algorithms and tools for protein-protein interaction networks clustering,with a special focus on population-based stochastic methods.Bioinformatics,2014,30(10):1343-1352. [3] PASTOR-SATORRAS R,VESPIGNANI A.Evolution andStructure of the Internet:A Statistical Physics Approach//Evolution and Structure of the Internet.2004. [4] WASSERMAN S.Social network analysis:Methods and applica-tions//Cambridge University Press,1994:181-190. [5] YANG B,LIU D Y,JIN D,et al.Complex network clustering method .Journal of Software,2009,20(1):54-66. [6] PIZZUTI C.A Multi-obJective Genetic Algorithm for Community Detection in Networks//IEEE International Conference on Tools with Artificial Intelligence.2009. [7] RAHIMI S,ABDOLLAHPOURI A,MORADI P.A multi-obJective particle swarm optimization algorithm for community detection in complex networks.Swarm and Evolutionary Computation,2018,4(39):297-309. [8] LIU C,LIU J,JIANG Z.A MultiobJective Evolutionary Algorithm Based on Similarity for Community Detection From Signed Social Networks.IEEE Transactions on Cybernetics,2017,44(12):2274-2287. [9] ZHANG L,PAN H,SU Y,et al.A Mixed Representation-Based MultiobJective Evolutionary Algorithm for Overlapping Community Detection.IEEE Trans Cybern,2017,PP(99):1-14. [10] WEN X,CHEN W N,LINY,et al.A Maximal Clique Based MultiobJective Evolutionary Algorithm for Overlapping Community Detection.IEEE Transactions on Evolutionary Computation,2016,PP(99):1-1. [11] ZHANG X,ZHOU K,PAN H,et al.A Network Reduction-Based MultiobJective Evolutionary Algorithm for Community Detection in Large-Scale Complex Networks.IEEE Transactions on Cybernetics,2018,PP(99):1-14. [12] CORNE D W,JERRAM N R,KNOWLES J D,et al.PESA-II:region-based selection in evolutionary multiobJective optimization// Conference on Genetic & Evolutionary Computation.2001. [13] ZHANG S,LIU W Q,ZHAO N.Research of Consensus inMulti-agent Systems on Complex Network .Journal of Frontiers of Computer Science,2019,46(4):101-105. [14] ANGELINI L,BOCCALETTI S,MARINAZZO D,et al.Identification of network modules by optimization of ratio association.Chaos,2007,17(2):175. [15] DEB K,PRATAP A,AGARWAL S,et al.A fast and elitistmultiobJective genetic algorithm:NSGA-II.IEEE Transactions on Evolutionary Computation,2002,6(2):182-197. [16] ZHOU A,QU B Y,LI H,et al.MultiobJective evolutionary algorithms:A survey of the state of the art.Swarm & Evolutionary Computation,2011,1(1):32-49. [17] LI J Y,ZHOU J G,GUAN J H,et al.Research progress of spectral clustering algorithm .Journal of Intelligent Systems,2011,6(5):405-414. [18] NEWMAN M E J.Modularity and community structure in networks.Proceedings of the National Academy of Sciences of the United States of America,2006,103(23):8577-8582. [19] LANCICHINETTI A,FORTUNATO S,KERTSZ J.Detec-ting the overlapping and hierarchical community structure in complex networks.New Journal of Physics,2009,11(3):19-44. [20] ZHANG L,PAN H,SU Y,et al.A Mixed Representation-Based MultiobJective Evolutionary Algorithm for Overlapping Community Detection.IEEE Transactions on Cybernetics,2017,47(9):2703-2716. [21] ZHANG X,ZHOU K,PAN H,et al.A Network Reduction-Based MultiobJective Evolutionary Algorithm for Community Detection in Large-Scale Complex Networks.IEEE Transactions on Cybernetics,2018,50(2):703-716. [22] LANCICHINETTI A,FORTUNATO S,RADICCHIF.Benchmark graphs for testing community detection algorithms.Physical Review E Statistical Nonlinear & Soft Matter Physics,2008,78(4 Pt 2):046110. [23] DANON L,DAZGUILERA A,DUCH J,et al.Comparing community structure identification//Research and Innovation.Policies and Strategies in the Age of Globalization.2005. [24] LUSSEAU D.The emergent properties of a dolphin social network.Proceedings Biological Sciences,2003,270(2):S186. [25] ZACHARY W W.An Information Flow Model for Conflict and Fission in Small Groups.Journal of Anthropological Research,1976,33(4):452-473. [26] GLEISER P M,DANON L.Community Structure in Jazz.Advances in Complex Systems,2003,6(4):565-573. [27] GONG M,CAI Q,CHEN X,et al.Complex Network Clustering by MultiobJective Discrete Particle Swarm Optimization Based on Decomposition.IEEE Transactions on Evolutionary Computation,2014,18(1):82-97. |
| [1] | 郑文萍, 刘美麟, 杨贵. 一种基于节点稳定性和邻域相似性的社区发现算法 Community Detection Algorithm Based on Node Stability and Neighbor Similarity 计算机科学, 2022, 49(9): 83-91. https://doi.org/10.11896/jsjkx.220400146 |
| [2] | 杨波, 李远彪. 数据科学与大数据技术课程体系的复杂网络分析 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 |
| [3] | 何茜, 贺可太, 王金山, 林绅文, 杨菁林, 冯玉超. 比特币实体交易模式分析 Analysis of Bitcoin Entity Transaction Patterns 计算机科学, 2022, 49(6A): 502-507. https://doi.org/10.11896/jsjkx.210600178 |
| [4] | 何亦琛, 毛宜军, 谢贤芬, 古万荣. 基于点割集图分割的矩阵变换与分解的推荐算法 Matrix Transformation and Factorization Based on Graph Partitioning by Vertex Separator for Recommendation 计算机科学, 2022, 49(6A): 272-279. https://doi.org/10.11896/jsjkx.210600159 |
| [5] | 王本钰, 顾益军, 彭舒凡, 郑棣文. 融合动态距离和随机竞争学习的社区发现算法 Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning 计算机科学, 2022, 49(5): 170-178. https://doi.org/10.11896/jsjkx.210300206 |
| [6] | 唐春阳, 肖玉芝, 赵海兴, 冶忠林, 张娜. 面向双层网络的EWCC社区发现算法 EWCC Community Discovery Algorithm for Two-Layer Network 计算机科学, 2022, 49(4): 49-55. https://doi.org/10.11896/jsjkx.210800275 |
| [7] | 陈世聪, 袁得嵛, 黄淑华, 杨明. 基于结构深度网络嵌入模型的节点标签分类算法 Node Label Classification Algorithm Based on Structural Depth Network Embedding Model 计算机科学, 2022, 49(3): 105-112. https://doi.org/10.11896/jsjkx.201000177 |
| [8] | 杨旭华, 王磊, 叶蕾, 张端, 周艳波, 龙海霞. 基于节点相似性和网络嵌入的复杂网络社区发现算法 Complex Network Community Detection Algorithm Based on Node Similarity and Network Embedding 计算机科学, 2022, 49(3): 121-128. https://doi.org/10.11896/jsjkx.210200009 |
| [9] | 赵学磊, 季新生, 刘树新, 李英乐, 李海涛. 基于路径连接强度的有向网络链路预测方法 Link Prediction Method for Directed Networks Based on Path Connection Strength 计算机科学, 2022, 49(2): 216-222. https://doi.org/10.11896/jsjkx.210100107 |
| [10] | 李家文, 郭炳晖, 杨小博, 郑志明. 基于信息传播的致病基因识别研究 Disease Genes Recognition Based on Information Propagation 计算机科学, 2022, 49(1): 264-270. https://doi.org/10.11896/jsjkx.201100129 |
| [11] | 陈湘涛, 赵美杰, 杨梅. 基于子图结构的局部社区发现算法 Overlapping Community Detection Algorithm Based on Subgraph Structure 计算机科学, 2021, 48(9): 244-250. https://doi.org/10.11896/jsjkx.201100010 |
| [12] | 穆俊芳, 郑文萍, 王杰, 梁吉业. 基于重连机制的复杂网络鲁棒性分析 Robustness Analysis of Complex Network Based on Rewiring Mechanism 计算机科学, 2021, 48(7): 130-136. https://doi.org/10.11896/jsjkx.201000108 |
| [13] | 胡军, 王雨桐, 何欣蔚, 武晖栋, 李慧嘉. 基于复杂网络的全球航空网络结构分析与应用 Analysis and Application of Global Aviation Network Structure Based on Complex Network 计算机科学, 2021, 48(6A): 321-325. https://doi.org/10.11896/jsjkx.200900112 |
| [14] | 王学光, 张爱新, 窦炳琳. 复杂网络上的非线性负载容量模型 Non-linear Load Capacity Model of Complex Networks 计算机科学, 2021, 48(6): 282-287. https://doi.org/10.11896/jsjkx.200700040 |
| [15] | 马媛媛, 韩华, 瞿倩倩. 基于节点亲密度的重要性评估算法 Importance Evaluation Algorithm Based on Node Intimate Degree 计算机科学, 2021, 48(5): 140-146. https://doi.org/10.11896/jsjkx.200300184 |
|
||
首页