一种基于效率矩阵的网络节点重要度评价算法

《一种基于效率矩阵的网络节点重要度评价算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第30卷第5期计算物理Vol．30，No．52013年9月CHINESEJOUＲNALOFCOMPUTATIONALPHYSICSSep．，2013文章编号:1001-246X(2013)05-0714-06一种基于效率矩阵的网络节点重要度评价算法范文礼，刘志刚(西南交通大学电气工程学院，四川成都610031)摘要:为了实现对网络节点重要性的有效评价，提出一种基于网络效率矩阵的节点重要度评价算法．该方法综合考虑节点的度值(局部重要度)和网络节点之间的重要性贡献(全局重要度)，利用节点的度和效率矩阵表征网络节点的重要度贡献，克服重要性贡献矩阵法中节点只依赖于邻接节

2、点的不足．考虑实际网络的稀疏性，该算法的时2间复杂度为O(n)．通过算例分析验证了该算法的可行性和有效性，结果表明:该算法能够更加直观、简单有效地区分节点的重要度差异，并且对于大型复杂网络具有较理想的计算能力．关键词:复杂网络;效率矩阵;重要度贡献;节点度中图分类号:N949;TP393文献标识码:A0引言［1］许多复杂系统均可由相互作用的系统部件组成的复杂网络来描述，如万维网、Internet网、交通网以及［2］电力网络等．这些网络在不同的节点攻击模式下，具有不同的抗毁性．相对而言，选择网络“核心、重要节点”攻击，其抗毁性较差．因此，采取有效的方法评价这些网络

3、中节点的重要程度，并进一步加强这些网络中“核心、重要节点”的保护与控制，将有效提高网络的抗毁性．近年来，国内外学者针对网络节点的重要度评价提出了许多有价值方法，主要有:1)信息搜索领域分析方法．该类方法对于有向网络节点重要度评价具有良好的性能，但不适用于无向［3－4］网络．［5－6］2)“破坏性等价于重要性”的系统科学分析方法．代表性的方法有最短路径法、最小生成树数目的［7］［8］节点删除法、节点收缩法等．该类方法是通过破坏网络拓扑结构来分析网络连通性的变化情况，并进一步度量网络节点的重要程度．该方法中由于删除不同节点时可能会造成网络的连通性相同，从而不能准确判

4、断网络节点的重要程度．3)“显著性等价重要性”的社会网络分析方法．各种中心性指标相继被提出并被用于度量节点的重要［9］［10］性，如度中心性(degreecentrality)、介数中心性(betweennesscentrality)、紧密度中心性(closeness［11］［12］［13］centrality)、子图中心性(subgraphcentrality)以及半局域中心性(semi-localcentrality)等．度中心性指标可以判定节点在邻域范围内的直接影响力，但是缺乏考虑节点在网络中的全局重要性，故不能完全准确地对其重要度进行判断(如“桥连接”节

5、点)．介数中心性指标虽然可以反映网络节点在整个网络中的全局重要性，但是计算复杂瓶颈了该方法在大规模网络中的应用．实际上，网络节点的重要度不仅和节点局部重要［14－15］度与网络位置有关，而且和节点之间的相互依赖程度密切相关．基于以上考虑，本文在文献［14］算法的基础上进行了修正和改进，提出一种评价网络节点重要度的新方法．该方法不仅考虑节点的度值、邻接节点之间的相互作用，而且考虑非邻接节点通过最有效路径对评估节点的相互作用程度，使得网络节点重要度评价更为精确．最后通过算例分析验证该方法的有效性．收稿日期:2012－10－31;修回日期:2013－01－27基金项目

6、:国家自然科学基金(U1134205，51007074);教育部新世纪优秀人才支持计划(NECT-08-0825)及中央高校基本科研业务费专项资金(SWJTU11CX141)资助项目作者简介:范文礼(1980－)，男，博士生，主要研究方向为复杂网络理论在电力系统中的应用，E-mail:fanwenlihp@163．com第5期范文礼等:一种基于效率矩阵的网络节点重要度评价算法7151理论基础假设无向无权网络用图G=(V，M)表示．其中，图G中包含n个节点，m条边，V={v1，v2，…，vn}表示图中节点的集合，M={m1，m2，…，mm}V×V表示图中边的集合

7、．定义1:节点度值ki(i∈n)是指节点vi与邻接节点的连接边的数量．定义2:最有效路径lij(i∈n，j∈n)是指节点对(vi，vj)间传输信息或能量效率最高的路径．节点间的最有效路径是网络中信息传播的最直接、最有效的路径．在本文所研究的无权网络中，最有效路径等价于最短路径，即节点对之间所含边数最少的路径．相应路径上边的数量用来定义节点对之间的距离，用dij表示．定义3:效率eij(i∈n，j∈n)是指节点vi至vj距离的倒数，即eij=1/dij．当i=j或节点对(vi，vj)不存在最短路径时，eij=0;当节点对(vi，vj)互为邻接节点时，其传输效率值最

8、大，即，eij=1;当节