一种基于K-Shell的复杂网络重要节点发现算法

An Algorithm of Important Nodes Finding for Complex Network Based on K-Shell

复杂网络中的重要节点通常数量较少,但是对网络的影响却很大。为了能够有效地发现网络拓扑结构中的重要节点,文中基于K-Shell算法,在考虑节点自身重要度的基础上,考虑了邻居节点对自身节点的重要度贡献,提出KSA(K-Shell-Affect)算法。该算法引入影响度概念,用节点自身的K-Shell值和与对其邻居节点的影响度来表征其对邻居节点的重要度贡献。对具有明显社团结构的Zachary网络进行仿真表明,该算法可行有效,克服了K-Shell划分结果的粗粒化,能够正确找到网络中的重要节点,具有一定的合理性,尤其在具有社团结构的网络中,能够十分有效地找到社团内部的核心节点。

There are only a few important nodes in the complex network,which have a great impact on the complex network. In order to discover the important nodes in the complex network effectively,propose a novel algorithm-KSA（ K-Shell-Affect） based on K-Shell. The algorithm considers the property of node itself,as well as the important contributions of the adjacent nodes by introducing the concept of affect. The important contribution to the adjacent nodes is characterized by K-Shell and affect to the adjacent nodes. The simulation on the Zachary network,which has a significant community structure,shows that the algorithm is feasible,effective and reasonable,and over-comes the coarse result of the K-Shell . Especially for a network of community structure,can find the core node of the community struc-ture effectively.