Evaluation of Node Importance in Complex Networks
-
摘要: 为提高复杂网络中重要节点评估的效率和有效性,提出了一种基于节点接近度和节点在其邻域中的关键度评估复杂网络中节点重要度的方法.该方法综合了节点的全局和局部重要性,即在复杂网络中,节点的接近度越大,该节点越居于网络的中心,在网络中就越重要;节点在其邻域中的关键度越大,该节点对其邻域越重要.根据该方法设计了复杂网络中节点重要度评估算法,该算法的复杂度为O(n3).实例分析证明了该方法的有效性.Abstract: To improve the efficiency and validity of node importance evaluating,a new evaluation method for node importance in complex networks was proposed based on node closeness and node key degree in its neighborhood. In this method,the global importance and the local importance of nodes are combined. The basic thought of the method is that the bigger the closeness of a node is,the closer to center of a complex network the node is and the more important it is; the bigger the key degree of a node in its neighborhood is,the more important in the neighborhood the node is. An evaluation algorithm corresponding to the method was designed. This algorithm has a time complexity of O(n3). Finally,the validity of the proposed method was verified by experiments.
-
Key words:
- complex network /
- node importance /
- closeness /
- neighborhood /
- key field /
- key degree
-
WATTS D J,STROGATZ S H.Collective dynamics of‘small-world'networks[J].Nature,1998,393:440-442[2] 郭雷,许晓鸣.复杂网络[M].上海:上海科技教育出版社,2006:1-283.[3] 汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社,2006:1-130.[4] 谭跃进,吴俊,邓宏钟.复杂网络中节点重要度评估的节点收缩方法[J].系统工程理论与实践,2006,11(11):79-83.TAN Yuejin,WU Jun,DONG Hongzhong.Evaluation method for node importance based on node contraction in complex networks[J].Systems Engineering-Theory Practice,2006,11(11):79-83.[5] 吴俊,谭跃进,邓宏钟,等.考虑级联失效的复杂负载网络节点重要度评估[J].小型微型计算机系统,2007,28(4):627-630.WU Jun,TAN Yuejin,DONG Hongzhong,et al.Evaluating node importance considering cascading failure in complex load-networks[J].Journal of Chinese Computer Systems,2007,28(4):627-630.[6] 刘艳,顾雪平.基于节点重要度评价的骨架网路重构[J].中国电机工程学报,2007,27(10):20-26.LIU Yan,GU Xueping.Node importance assessment based skeleton-network reconfiguration[J].Proceedings of CSEE,2007,27(10):20-26.[7] WEST D B.Introduction to graph theory[M].[S.l.]:Prentice Hall,2001.[8] CALLAWAY D S,NEWMAN M E J,STROGATEZ S H,et al.Network robustness and fragility:percolation on random graphs[J].Phys.Rev.Lett.,2000,85(25):5468-5471.[9] FREEMAN L C.A set of measures of centrality based upon betweenness[J].Sociometry,1977,40(1):35-41.[10] 陈勇,胡爱群,胡俊,等.通信网络中最重要节点确定方法[J].高技术通讯,2004,1:573-575.CHEN Yong,HU Aiqun,HU Jun,et al.A method for finding the most vital node in communication networks[J].Chinese High Technology Letters,2004,1:573-575.
点击查看大图
计量
- 文章访问数: 2146
- HTML全文浏览量: 78
- PDF下载量: 1181
- 被引次数: 0