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

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

复杂网络关键节点与关键连边在网络中均起着十分重要的作用,目前的识别方法往往无法做到同时识别,并且识别指标角度较为单一。为解决上述问题,提出一种基于最小连通支配集(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.