复杂网络中节点重要度评估的节点收缩方法

Evaluation Method for Node Importance based on Node Contraction in Complex Networks

首先定义了网络的凝聚度,在此基础上提出了一种评估复杂网络节点重要度的节点收缩方法,认为最重要的节点就是将该节点收缩后网络的凝聚度最大,其算法的时间复杂性为O(n3).该方法综合考虑了节点的连接度以及经过该节点最短路径的数目,克服了节点删除法的弊端.最后的实验分析表明该方法直观、有效且运算速度快,对于大型复杂网络可以获得理想的计算能力.

Complex networks with inhomogeneous topology are very fragile to intentional attacks on the ＂hub nodes＂. It is very important and desirable to evaluate the node importance and find these ＂hub nodes＂. The networks agglomeration is defined firstly. A node contraction method of evaluation of node importance in complex networks is proposed based on a new evaluation criterion, i. e. the most important node is the one whose contraction results in the largest increase of the networks agglomeration. With the node contraction method, both degree and position of a node are considered and the disadvantage of node deletion method is avoided. An algorithm whose time complexity is O（ n^3） is proposed. Final experiments verify its efficiency.