网络节点重要度的快速评估方法

对网络节点进行重要性评估, 快速发掘重要性节点已经成为数据挖掘、复杂网络中的一个基本问题, 现有的节点重要度评估方法对于大型网络而言, 计算速度较慢. 基于电阻网络提出一种快速实用的节点重要度评估方法, 该方法利用节点对网络电能消耗的影响来评估节点的重要度, 如果由于一个节点的存在而导致网络平均电能消耗减少, 则该节点就越重要, 反之则该节点重要度就低. 该方法的时间复杂度为O(n³), 在分布式扩展的情况下可达到O(n), 实验分析证明了该方法的有效性, 而且运算速度快, 能处理大规模网络.

Fast method for node importance evaluation in network

Node importance evaluation is one of the important network analyses in complex network and data mining. However most of the existing methods are complex and slow for large networks. In this paper, a practical method based on resistive network for fast node importance evaluation was proposed. Node importance was evaluated based on its influence on the average power dissipation in a resistance network, a node was important because it reduced the average energy dissipation of the network. The time complexity of the algorithm is O(n³) in the worst situation, and is O(n) in the distributed computing environment. Experimental results testify that the algorithm is efficient and effective.