基于最小连通支配集的复杂网络关键节点与连边识别方法  

Identifying key nodes and edges of complex networks based on the minimum connected dominating set

作　　者：李佳威 吴明功 温祥西[1] 刘飞 LI Jiawei;WU Minggong;WEN Xiangxi;LIU Fei(Air Traffic Control and Navigation College,Air Force Engineering University,Xi’an 710051,China;National Key Laboratory of Air Traffic Collision Prevention,Xi’an 710051,China)

机构地区：[1]空军工程大学空管领航学院,陕西西安710051 [2]国家空管防相撞技术重点实验室,陕西西安710051

出　　处：《系统工程与电子技术》2019年第11期2541-2549,共9页Systems Engineering and Electronics

基　　金：国家自然科学基金（71801221）;陕西省自然科学基础研究计划（2018JQ7004）资助课题

摘　　要：复杂网络关键节点与关键连边在网络中均起着十分重要的作用,目前的识别方法往往无法做到同时识别,并且识别指标角度较为单一。为解决上述问题,提出一种基于最小连通支配集(minimum connected dominating set,MCDS)的复杂网络关键节点与连边识别方法,通过使用免疫粒子群(immune particle swarm optimization,IPSO)算法寻找网络最小连通支配集,构建核心骨干网,实现对复杂网络关键节点与连边的同时识别。该算法在求解过程中引入免疫机制指导粒子节点搜索方向、加快算法收敛速度,同时优化搜索节点质量。经实验验证表明,所提识别方法能够有效识别网络中的关键节点与关键连边。The key nodes and vital edges play an important role in complex networks.Current identification methods often cannot identify these at the same time,and the angle of identification indicators is relatively single.To solve these problems,a method for identifying key nodes and connected edges of complex networks based on the minimum connected dominant set is proposed.By using the immune particle swarm optimization algorithm to find the minimum connected dominant set of networks,the core backbone network is constructed to achieve simultaneous identification of key nodes and edges of complex networks.In the process of solving the immune particle swarm optimization algorithm,the immune mechanism is introduced to guide the search direction of particle nodes,accelerate the convergence speed of the algorithm,and optimize the search node quality.The experimental results show that the proposed method can effectively identify the key nodes and edges in the complex network.

关 键 词：最小连通支配集 复杂网络 关键节点 关键边 

分 类 号：N945.12[自然科学总论—系统科学] O243[理学—计算数学]