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

Fast method for node importance evaluation in network

作　　者：肖卫东[1] 谭文堂[1] 葛斌[1] 李芳芳[1] 

机构地区：[1]国防科技大学信息系统工程重点实验室,长沙410073

出　　处：《系统工程理论与实践》2013年第7期1898-1904,共7页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(60903225);国防科技大学优秀研究生创新基金(S100502)

摘　　要：对网络节点进行重要性评估,快速发掘重要性节点已经成为数据挖掘、复杂网络中的一个基本问题,现有的节点重要度评估方法对于大型网络而言,计算速度较慢.基于电阻网络提出一种快速实用的节点重要度评估方法,该方法利用节点对网络电能消耗的影响来评估节点的重要度,如果由于一个节点的存在而导致网络平均电能消耗减少,则该节点就越重要,更之则该节点重要度就低.该方法的时间复杂度为O(n^3),在分布式扩展的情况下可达到O(n),实验分析证明了该方法的有效性,而且运算速度快,能处理大规模网络.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（n3） in the worst situation, and is O（n） in the distributed computing environment. Experimental results testify that the algorithm is efficient and effective.

关 键 词：网络 节点重要度 电阻网络 电能消耗 

分 类 号：TP31[自动化与计算机技术—计算机软件与理论] N949[自动化与计算机技术—计算机科学与技术]