Improved evaluation method for node importance based on mutual information in weighted networks

doi:10.11772/j.issn.1001-9081.2015.07.1820

Abstract

Abstract:

The existing evaluation methods for node importance in complex network mainly focus on undirected-unweighted complex networks, and can not reflect objectively the reality of some real world status. Focusing on the problems such as the limited scope of evaluation indexes and not enough comprehensive evaluation results in the undirected-weighted and directed-weighted networks, and the node importance evaluation method in undirected-unweighted networks based on mutual information was used for reference, a new evaluation method based on mutual information that is suitable for the undirected-weighted and directed-weighted networks was proposed. In this method, each edge was regarded as a flow of information, the structure characteristics of the corresponding complex networks and the definition method of "amount of information" were considered, then the amount of information was calculated as the node importance evaluation index. The analyses of the instance network show that the proposed algorithm can more detailed describe the differences between nodes in the directed-weighted network under the premise of guaranteeing estimation accuracy. In the evaluation of the ARPA (Advanced Research Project Agency) network nodes, the first five most important nodes number that were evaluated from the proposed algorithm and the previous indexes were especially close, so the algorithm's ability of finding the core nodes was highlighted. The proposed algorithm provides a certain theoretical help for evaluating the core nodes in the undirected-weighted and directed-weighted networks and improving the network invulnerability ability quickly and accurately.

Key words: node importance, mutual information, topology, undirected-weighted network, directed-weighted network

摘要：

现有的复杂网络节点重要性评估研究主要集中在无向无权网络上,不能全面客观反映某些真实复杂网络的情况。针对无向加权和有向加权网络中评估指标适用范围有限、评估结果不够全面等问题,借鉴应用于无向无权网络的基于互信息的节点重要性评估方法,提出适用于无向加权网络和有向加权网络的互信息评估方法。该方法将网络中的每条边看作信息流,结合相应复杂网络的结构特点和"信息量"的定义方法,以求出的节点信息量作为节点的重要性评估指标。对实例网络进行分析可知,所提算法在保证评估准确性前提下,能更加细致刻画有向加权网络节点之间的差异性。在对ARPA网络的节点评估中,所提算法与以往指标所评估出的前5个最重要节点的节点编号尤其相近,凸显出该算法快速发掘核心节点的能力,为快速、准确评估无向加权和有向加权网络核心节点,提高网络抗毁性提供一定理论帮助。

关键词: 节点重要性, 互信息, 拓扑结构, 无向加权网络, 有向加权网络

CLC Number:

TP393
O157.5

WANG Ban, MA Runnian, WANG Gang, CHEN Bo. Improved evaluation method for node importance based on mutual information in weighted networks[J]. Journal of Computer Applications, 2015, 35(7): 1820-1823.

王班, 马润年, 王刚, 陈波. 改进的加权网络节点重要性评估的互信息方法[J]. 计算机应用, 2015, 35(7): 1820-1823.

References

[1] HE N, LI D, GAN W, et al. Mining vital nodes in complex networks [J]. Computer Science, 2007, 34(12): 1-5.(赫南,李德毅,淦文燕,等.复杂网络中重要性节点发掘综述[J].计算机科学,2007,34(12):1-5.)
[2] WANG L, ZHANG J. Centralization of complex networks [J]. Complex Systems and Complexity Science, 2006, 3(1): 13- 20.(王林,张婧婧.复杂网络的中心化[J].复杂系统与复杂性科学,2006,3(1):13-20.)
[3] REN Z, SHAO F, LIU J, et al. Node importance measurement based on the degree and clustering coefficient information [J]. Acta Physica Sinica, 2013, 62(12): 128901-1-128901-5).(任卓明,邵凤,刘建国,等.基于度与集聚系数的网络节点重要性度量方法研究[J].物理学报,2013,62(12):128901-1-128901-5.)
[4] ZHOU X, ZHANG F, LI K, et al. Finding vital node by node importance evaluation matrix in complex networks [J]. Acta Physica Sinica, 2012, 61(5): 050201-1-050201-7).(周漩,张凤鸣,李克武,等.利用重要度评价矩阵确定复杂网络关键节点[J].物理学报,2012,61(5):050201-1-050201-7.)
[5] YAO Z, SHANG K, XU X. Fundamental statistics of weighted net-works [J]. Journal of University of Shanghai for Science and Technology, 2012, 34(1): 18-26.(姚尊强,尚可可,许小可.加权网络的常用统计量[J].上海理工大学学报,2012,34(1):18-26.)
[6] LANDHERR A, FRIEDL B, HEIDEMANN J. A critical review of centrality measure in social networks [J]. Business & information Systems Engineering, 2010, 2(6): 371-385.
[7] CALLAWAY D S, NEWMAN M E J, STROGATEZ S H, et al. Network robustness and fragility: percolation on random graphs [J]. Physical Review Letters, 2000, 85(25): 5468-5471.
[8] BARTHELEMY M. Betweenness centrality in large complex net-works [J]. The European Physical Journal B—Condensed Matter and Complex Systems, 2004, 38(2): 163-168.
[9] ZHU T, ZHANG S, GUO R, et al. Improved evaluation method for node importance based on node contraction in weighted complex networks [J]. Systems Engineering and Electronics, 2009, 31(8): 1902-1905.(朱涛,张水平,郭戎潇,等.改进的加权复杂网络节点重要度评估的收缩方法[J].系统工程与电子技术,2009,31(8):1902-1905.)
[10] WANG J, WU X, LIAO W, et al. Improved method of node importance evaluation in weighted complex networks [J]. Computer Engineering, 2012, 38(10): 74-76.(王甲生,吴晓平,廖巍,等.改进的加权复杂网络节点重要度评估方法[J].计算机工程,2012,38(10):74-76.)
[11] ZHANG K, LI P, ZHU B, et al. Evaluation method for node importance in directed-weighted complex networks based on PageRank [J]. Journal of Nanjing University of Aeronautics & Astronautics, 2013, 45(3): 429-434.(张琨,李配配,朱保平,等.基于PageRank的有向加权复杂网络节点重要性评估方法[J].南京航空航天大学学报,2013,45(3):429-434.)
[12] BRIN S, PAGE L. The anatomy of a large-scale hypertextual Web search engine [J]. Computer Networks and ISDN Systems, 1998, 30(1/2/3/4/5/6/7): 107-117.
[13] ZHANG Y, LIU Y, XU K, et al. Evaluation method for node importance based on mutual information in complex networks [J]. Computer Science, 2011, 38(6): 88-89.(张翼,刘玉华,许凯华,等.一种基于互信息的复杂网络节点重要性评估方法[J].计算机科学,2011,38(6):88-89.)
[14] FU Z. Information theory—principles and applications [M]. 3rd ed. Beijing: Publishing House of Electronics Industry, 2001: 80-86.(傅祖芸.信息论——基础理论与应用[M].3版.北京:电子工业出版社,2001:80-86.)
[15] MIRZASOLEIMAN B, BABAEI M, JALILI M, et al. Cascaded failures in weighted networks [J]. Physical Review E, 2011, 84(4): 046114-1-046114-8.