基于重连机制的复杂网络鲁棒性分析

Robustness Analysis of Complex Network Based on Rewiring Mechanism

随着电力系统、交通系统、通信系统等基础设施网络的广泛使用,提高复杂网络的鲁棒性具有重要意义。重连机制是一种高效且简洁的方法,常用于提高网络的鲁棒性。基于0阶零模型的重连机制通过对边的随机删除和创建操作来提高网络的鲁棒性,其尽管保持了网络的边数,但会引起节点的度值发生变化,如基于香农熵的重连算法;基于1阶零模型的重连机制通过随机选择两条边进行换边操作来提高网络的鲁棒性,其尽管保持了网络的度分布,但随机选边难以准确找到合适的节点,增加了算法的时间成本,如基于最大连通分支的重连算法。因此,为了保持网络的度分布且快速提高网络的鲁棒性,提出了一种基于1阶零模型的快速重连算法(Fast Rewiring Mechanism based on 1-order Null Model,FRM)。FRM算法通过比较每条边的两个端点度值的差异为边加权,根据边的权重优先选择权重较大的两条边,并创建度值相似节点之间的连边来提高网络的鲁棒性。在3个真实网络数据上与4种代表性重连算法相比,对比实验结果表明,FRM算法在度中心性、介数中心性和Page-Rank中心性攻击下最大连通分支中的节点比例s(Q)、基于最大连通分支的鲁棒性指标R和基于香农熵的鲁棒性指标I(G)的表现都更好。

With the widespread use of infrastructure networks such as power systems,transportation systems,and communication systems,it is of great significance to improve the robustness of complex networks.The rewiring mechanism is an efficient and simple method to improve the robustness of the network.The rewiring mechanism based on the 0-order null model improves the robustness of the network by randomly deleting and creating edges.Although the number of edges is maintained,the degree of nodes will change,such as the RM-ES algorithm.The rewiring mechanism based on the 1-order null model improves the robustness of the network by randomly selecting two edges for rewiring,although the degree distribution is maintained,it is difficult to find the appropriate nodes by random edge selection,which increases the running time of algorithms,such as the RM-LCC algorithm.Therefore,in order to maintain the degree distribution and improve the robustness of the network,this paper proposes a fast rewiring mechanism based on 1-order null model,called FRM.The FRM algorithm first weights the edges by degree for each edge,then selects two edges with the probability proportional to the weight of edge,finally,creates the edges between nodes with similar degree.We compare the FRM algorithm with other methods on real network data sets.The experimental results of three real network data show that FRM algorithm performs better than four representative rewiring algorithms under the attack of degree centrality,betweenness centrality and PageRank centrality with respect to the ratio of nodes in largest connected component s(Q),robustness index R and robustness index I(G).