一种基于网络拓扑的关键节点挖掘算法  

A topology-based heuristics algorithm for critical node detection

作　　者：许钦钧 徐龙琴 刘双印 赵学华[4] XU Qinjun;XU Longqin;LIU Shuangyin;ZHAO Xuehua(College of Information Science and Technology,Zhongkai University of Agriculture and Engineering,Guangzhou 510225,China;Intelligent Agriculture Engineering Research Center of Guangdong Higher Education Institutes,Guangzhou 510225,China;Guangzhou Key Laboratory of Agricultural Products Quality&Safety Traceability Information Technology,Guangzhou 510225,China;School of Digital Media,Shenzhen Institute of Information Technology,Shenzhen 518172,China)

机构地区：[1]仲恺农业工程学院信息科学与技术学院,广东广州510225 [2]广东省高校智慧农业工程技术研究中心,广东广州510225 [3]广州市农产品质量安全溯源信息技术重点实验室,广东广州510225 [4]深圳信息职业技术学院数字媒体学院,广东深圳518172

出　　处：《仲恺农业工程学院学报》2023年第2期21-30,共10页Journal of Zhongkai University of Agriculture and Engineering

基　　金：国家自然科学基金(61871475);广东省自然科学基金(2021A1515011994);广州市重点研发计划项目(202103000033,201903010043);广东省科技计划项目(2020A1414050060,2020B0202080002,2016A020210122,2015A040405014);广东省普通高校创新团队项目(2021KCXTD019,2020KCXTD040,2022KCXTD057);广东省普通高校特色创新项目(KA190578826);梅州市科技计划项目(2021A0305010);广州市增城区农村科技特派员项目(2021B42121631);广东省教育科学规划课题(2020GXJK102,2018GXJK072);广东省研究生教育创新计划项目(2022XSLT056,2022JGXM115).

摘　　要：关键节点挖掘在研究网络结构和性能方面具有广泛且重要的应用潜力.提出了一种基于网络拓扑的关键节点挖掘算法,以解决关键节点问题.该算法挖掘网络社区结构,使用基于拓扑的中心性指标选择节点集,通过迭代地交换该节点集和原网络中的部分点来优化网络连通性指标.同时,采用改进的局部搜索和加权随机选择机制,以加强搜索能力和克服局部最优陷阱.此外,为了改进初始解的质量,提出了一种基于网络拓扑的节点中心性指标.在多个合成和真实的网络数据集上与一些先进算法的比较试验表明,本研究提出的算法具有更好的精度和鲁棒性.The mining of critical nodes has a wide and important potential application in studying network structures and performances.A topology-based critical node mining algorithm is proposed to solve the critical node problem.The algorithm mines the community structure of the network and selects a set of nodes based on topological centrality indicators.Then,this node set and part of the original network are iteratively exchanged to optimize the network connectivity index.At the same time,an improved local search and weighted random selection mechanism are adopted to strengthen the search ability and overcome local optimal traps.In addition,a node centrality indicator based on network topology is proposed to improve the quality of the initial solution.Experiments on multiple synthetic and real network datasets between the proposed algorithm and other advanced algorithms show that the proposed algorithm has better accuracy and robustness.

关 键 词：复杂网络 网络拓扑 关键节点 启发式算法 

分 类 号：O157.5[理学—数学]