基于自规避随机游走的节点排序算法

A ranking method based on self-avoiding random walk in complex networks

评估复杂网络系统的节点重要性有助于提升其系统抗毁性和结构稳定性.目前,定量节点重要性的排序算法通常基于网络结构的中心性指标如度数、介数、紧密度、特征向量等.然而,这些算法需要以知晓网络结构的全局信息为前提,很难在大规模网络中实际应用.基于自规避随机游走的思想,提出一种结合网络结构局域信息和标签扩散的节点排序算法.该算法综合考虑了节点的直接邻居数量及与其他节点之间的拓扑关系,能够表征其在复杂网络系统中的结构影响力和重要性.基于三个典型的实际网络,通过对极大连通系数、网络谱距离数、节点连边数和脆弱系数等评估指标的实验对比,结果表明提出的算法显著优于现有的依据局域信息的节点排序算法.

Evaluation of node importance is helpful to improve the invulnerability and robustness of complex networked systems.At present,the classic ranking methods of quantitatively analyzing node importance are based on the centrality measurements of network topology,such as degree,betweenness,closeness,eigenvector,etc.Therefore,they often restrict the unknown topological information and are not convenient to use in large-scale real networked systems.In this paper,according to the idea of self-avoiding random walking,we propose a novel and simplified ranking method integrated with label propagation and local topological information,in which the number of labels that node collects from propagating process quantitatively denotes the ranking order.Moreover,the proposed method is able to characterize the structural influence and importance of node in complex networked system because it comprehensively considers both the direct neighbors of node and the topological relation of node to other ones.Through performing the experiments on three benchmark networks,we obtain interesting results derived from four common evaluating indices,i.e.,the coefficient of giant component,the spectral distance,the links of node,and the fragility,which indicate that the proposed method is much more efficient and effective for ranking influential nodes than the acquaintance algorithm.