版权信息
省级大型综合性科技类期刊
主管部门:自治区科技厅
主办单位:自治区科学技术信息研究院 
协办单位:自治区科学技术情报学会
编辑出版:科技期刊编译室
刊社地址:呼和浩特新城西街149号本刊杂志社
邮政编码:010000
电      话:0471-2536371

E-mail  :

nmgkjzz@vip.163.com 

网站地址:www.nmgkjzz.com


往期杂志
当前位置: 首页>往期杂志>详细介绍

复杂网络节点重要性研究概述

时间:2016-07-28来源: 作者: 点击: 253次


摘要 近年来,复杂网络已经成为众多学科共同关注的一个研究热点。大多数人工的、自然的复杂系统都可以根据不同的研究角度,借用复杂网络理论表示为由相互作用的节点组成的网络。在复杂网络中,如何量化节点的重要性是整个复杂网络研究中一个重要的课题,因为发掘复杂网络中的重要节点在社会、政治、医药、信息技术等领域具有十分重要的应用价值。

关键词 复杂网络,节点,重要性

中图分类号 TP393.0        文献标识码 A

overview of the research on the importance of complex network nodes

HUANG Ping  PENG Meng-jing

(Chongqing Traditional Chinese Medicine Hospital,Chong Qing400021,China)

Abstract In recent years, complex network has become a hot research topic in many disciplines. Most artificial and natural complex systems can be expressed by different research angles, and the complex network theory is used to represent the network composed of interacting nodes. In complex networks, how to quantify node importance is an important topic in the study of complex networks, because of the complex to explore an important node in the network in the field of society, politics, medicine, information technology and other has very important application value.

Keywords Complex network, Node, Importance


1引言

理论上讲,复杂网络研究作为新兴的交叉科学,其研究形式、方法和手段都在不断探索与发展之中,任何复杂系统也都可以作为复杂网络来研究。复杂网络作为复杂系统的一种研究方法,可以很好地分析复杂系统内部结构和个体之间的关系。

复杂网络同我们的生活紧密相关,很多方面都可以用复杂网络理论描述。如果将真实世界中形形色色的个体用节点来表示,用边来代表个体之间的联系,许多事物都可以用网络图的理论来分析。

研究表明,现实网络中的节点地位并不平等,存在着明显的差异,同时处于不同地位的节点对网络抗毁性的影响程度不同,即在无尺度网络中当5%的核心节点被攻击时,网络就会陷入瘫痪[1]。研究还表明复杂网络既不是规则网络,也不是随机网络,它具有与这两者都不相同的特性:小世界特性[2]、无标度特性[3]、对于随机攻击的鲁棒性、对于恶意攻击的脆弱性等。

随着复杂网络研究的深入,许多基础问题的探讨显得越发重要。评估节点的重要程度是复杂网络研究中的一个基本问题,在网络中发掘重要节点,对其重要性进行评估具有很高的实用价值。比如搜索引擎的搜索结果排序、疾病传播的控制、防止由相继故障引起的大规模停电、复杂网络社区结构中社区中心的确定等,这些都涉及到节点重要性评估计算问题。

本文主要介绍几种研究复杂网络节点重要性的方法。

2 基于评估方式研究的几种方法

评估复杂网络中节点重要性的方法很多,本质上都是基于图论的。最初的研究起源于社会学领域,随后其他学科的研究人员也开始研究这类问题。归纳起来,主要的研究方法如下[4,9]

社会网络分析方法:将节点的重要性等价为显著性。最著名的指标是度数和介数,节点的度数为网络中与该节点相连的边的数量,介数则反映了一个节点的影响力。在这类方法中,指标的研究不破坏网络的整体性,通过对网络的一些基本信息统计分析,进而量化节点的重要性,例如文献[5]通过综合节点的全局和局部重要性来评价节点重要程度。已有的指标还包括接近度、特征向量、网络直径等[6]。这类研究方法从网络的结构特性出发研究,但方法得出的各种指标都有一定的局限性。

系统科学分析方法:移除某个节点对网络造成的破坏性等价于节点的重要性。移除节点对网络造成的破坏是多样的,例如文献[7]提出一种基于全网平均等效最短路径数的网络抗毁度评价方法,它基于抗毁性评价节点重要性;文献[8]通过比较生成树数目的方法来评估节点重要性;文献[9]从节点移除后网络中连通节点对数目下降出发,来量化节点的重要程度。这种系统科学的分析方法并没有完全体现网络拓扑结构的差异,因此对于节点重要性的评估不是很准确。

信息搜索领域分析方法:计算机科学家提出的一些算法考虑得更加全面。最著名的是Google的创始人Larry PageSergey Brin提出的网页排名算法pagerank,它是搜索引擎Google的核心技术之一。pagerank算法将文献检索中的引用理论用到Web中,引用网页的链接数,在一定程度上反映了该网页的重要性。每个到页面的链接都是对该页面的一次投票,被链接得越多,就意味着被其他网站投票越多。pagerank算法能够在网络中准确定位节点的重要程度,并且其计算复杂度不高。

还有其它文献从不同角度来研究,如文献[10]提出在节点正常工作的情况下,收缩与该节点相连的边,收缩后得到的网络凝聚程度越高,则该节点越重要;文献[11]省略了大量迂回路由对可靠性影响的细节,只考虑迂回路由影响的效果,提出了一种跳面节点法。不同的方法从不同的角度来探讨同一问题,所以给出的指标没有好坏之分,每个指标都有自己的优缺点。

3 基于重要度评价矩阵法

3.1 构建重要度评价矩阵

由于网络是由节点和边组成的统一整体,节点的重要度必然要受其相邻节点的影响。如图3.1所示,如果节点6和节点7之间没有连接,那么节点7的存在对节点6并没有多大影响,而一旦节点6和节点7之间建立连接,就会使得整个网络的效率、度值、最短路径等特性发生变化,由此可知节点的相连是存在重要度贡献的;另一方面,节点4和节点7虽然具有相同的度值,但是它们在网络中的重要程度是不一致的,究其原因是由于节点自身在网络中的位置和相邻节点的不同而造成的。显然,单纯地运用度值来衡量节点的重要度是存在明显缺陷的。

介数法和节点删除法[12]同样也只是考虑了节点的全局重要性(位置信息),而忽略了节点的局部重要性(相邻节点信息)。因此,为了克服这些缺陷,在复杂网络节点重要度评价过程中需要综合考虑节点自身在网络中所处位置(全局重要性)和相邻节点的重要度贡献(局部重要性)。


3.1 节点间重要度贡献关系图

 

彼此孤立的节点之间不存在重要度依赖关系,一旦节点间相互连接,就可能会导致节点负载和重要度的变化,通过节点之间的传递,就会形成一个重要度贡献关系的拓扑,它的结构来自于实际网络的拓扑,是实际网络拓扑的一个映射。由于网络的邻接矩阵反映了节点之间直接相邻的情况,而节点间最重要的重要度贡献关系存在于相邻节点之间, 因此节点间的重要度贡献关系可以用邻接矩阵的映射矩阵来表示。

在节点数为n,平均度值为k的无自环无向网络中,若节点Vi的度为Di,则Vi将自身重要度的Di/k2贡献给它的每一个相邻节点。将所有节点对其相邻节点的重要度贡献比例值用矩阵的形式表示出来,就形成了节点重要度贡献矩阵。

 QUOTE                3.1

其中, QUOTE  为网络邻接矩阵中对应的元素,称为贡献分配参数,当ViVj直接相连时取值为1,否则取值为0;对角线上的数表示节点对自身的重要贡献比例值为1。矩阵 QUOTE  与网络的邻接矩阵具有相同的结构,它是网络邻接矩阵的一个映射,映射规则为:

 QUOTE            (3.2

它反映的是网络重要度贡献关系的拓扑,这种结构能够充分利用邻接矩阵的信息,便于计算机实现。为了体现节点在网络信息传输过程中所起的作用,依据网络效率的定义,规定节点k的效率Ik为:

 QUOTE             (3.3

其中,n为网络中节点数目,dki为节点ki之间的距离,从Ik的定义中可以看出,一个节点的效率表达了该节点到网络中其他节点的平均难易程度,体现了该节点对网络信息传输所做的贡献。所以节点效率值越大,表明该节点在网络信息传输过程中所处位置越重要,移除此节点导致网络信息传输性能下降的可能性就越大,由此可见节点的效率在一定程度上反映了节点的重要程度。

这里利用度来构建节点之间的重要度关联,用节点的效率来表征节点的位置信息。融合节点的效率值,并用节点的重要度贡献值来代替 QUOTE  中的重要度贡献比例值,就可以得到节点重要度评价矩阵 QUOTE  

 QUOTE         (3.4

其中 QUOTE  表示节点j对节点i的重要度贡献值。可以看出,一个节点对其相邻节点的重要度贡献值与节点自身的效率和度值有关,节点的效率值越大、度值越高,则它对相邻节点的重要度贡献越大。运用节点重要度评价矩阵 QUOTE  ,综合考虑节点自身的效率和相邻节点的重要度贡献,可以定义节点i的重要度Ci

 QUOTE             (3.5

3.2 关键节点确定算法

评估节点重要度的简单算法步骤:

输入:复杂网络邻接矩阵 QUOTE  

输出:节点i的重要度Ci

Begin

1)    计算所有节点对之间的最短距离矩阵Dis=[dij]

2)    确定节点重要度贡献矩阵HIC

3)    确定节点重要度评价矩阵HE

4)    计算每个节点的重要度C

End

3.3 实验结果

实验采用网络拓扑结构如图3.1所示,网络中有8个节点、8条边。评估结果如表3.1所示:

3.1 节点重要度评估结果

节点

连接度

重要度评价矩阵

V1

1

0.157

V2

1

0.157

V3

3

0.254

V4

2

0.461

V5

3

0.535

V6

3

0.417

V7

2

0.404

V8

1

0.152

 

从表3.1可以看出,基于重要度评价矩阵来确定复杂网络关键节点对图3.1中的这个网络取得了一些效果,能够很好地区分各节点之间的重要程度。

4 基于网络凝聚度的节点收缩法

4.1 节点收缩及网络凝聚度

假设Vi是图G=VE)中的一个节点,我们用G*Vi表示将节点Vi收缩后得到的图。将节点Vi收缩是指将与节点Vi相连接的Ki个节点都与节点Vi融合,即用一个新结点代替这Ki+1个节点,原先与他们关联的边现在都与新结点关联,如图4.1所示。

直观上可以这样理解节点的收缩:我们把与节点Vi相连接的Ki个节点通过收缩都与节点Vi融合,这相当于节点Vi将它周围的Ki个节点凝聚成了一个节点。如果节点Vi是一个很重要的核心节点,那么将它收缩后整个网络将更好的凝聚在一起。最典型的例子就是如果我们将星形网中的中心节点收缩,整个网络就收缩成了一个节点,而将其它节点收缩整个网络的凝聚程度不会发生太大的改变。所以我们可以认为收缩后使得网络凝聚程度越高的节点就越重要。

网络的凝聚程度首先取决于网络中各个节点之间的连通能力,我们用节点之间的平均路径长度I来衡量,即所有节点对之间最短距离的算术平均值。其次,网络的凝聚程度还取决于网络中节点数目n。例如在一个社会关系网里人员之间联系越方便(l越小)、人数越少(n越小),整个网络的凝聚程度就越高。我们将网络的凝聚度定义为节点数n与平均路径长度l乘积的倒数。


4.1 节点收缩示意图

我们称

 QUOTE                      (4.1

为图G的凝聚度,其中n≥2dij代表节点ij之间的最短距离。当n=1时,我们令 QUOTE  =1。显然0< QUOTE  1,当网络中只有一个节点时, QUOTE  取最大值1

4.2 基于网络凝聚度的节点重要度评估

我们称

 QUOTE                         (4.2

为节点vi的重要度,其中G*vi表示将节点vi收缩后所得到的图。由式(4.1)和式(4.2)我们可以得到:

 QUOTE          (4.3

又因为 QUOTE  ,所以

 QUOTE                 (4.4

当且仅当vi为星型网络中的中心节点时,式(4.4)中等号成立。此时 QUOTE   ,   QUOTE  

由式(4.3)可以看出,节点Vi的重要度取决于两个因素:一是节点Vi的连接度ki,另外一个是节点Vi在网络中的位置。相同条件下,如果节点Vi的连接度ki越大,则将该节点收缩以后网络中节点的数目就越少,网络的凝聚度就越大。该节点越重要。另外,如果节点Vi处于“要塞”位置,则很多节点对之间的最短路径都要经过该节点,那么当把Vi收缩以后网络的平均路径长度将大大减少,从而获得较大的网络凝聚度。这与直观上我们判断一个节点的重要度是一致的。

4.3 评估节点重要度的算法

输入:H

输出:IMC

计算所有节点对之间的最短距离矩阵D=[dij]

计算网络初始凝聚度 QUOTE  

Repeat

1)    计算节点vi收缩后所有节点对之间的最短距离矩阵D(i)=[dst(i)]

2)    计算节点vi收缩后网络的凝聚度 QUOTE  

3)    计算 QUOTE  

End

4.4 实验结果

实验采用是网络拓扑结构图如图4.2所示,网络中有10个节点,10条边。


4.2 网络拓扑结构图

 

采用节点收缩法得到的结果如图4.3所示。


4.3 节点收缩后的图

 

其中(a)为节点v1v2v9v10收缩后的图;(b)为节点v3v8收缩后的图;(c)为节点v4v7收缩后的图;(d)为节点v5v6收缩后的图。

节点重要度评估结果如表4.1所示。

 

4.1 节点重要度评估结果

节点

连接度

节点收缩法

V1

1

0.1492

V2

1

0.1492

V3

3

0.4454

V4

3

0.4706

V5

2

0.2005

V6

2

0.2005

V7

3

0.4706

V8

3

0.4454

V9

1

0.1492

V10

1

0.1492

5 总结

现实世界中很多网络都具有复杂网络的特性,如小世界、无尺度、幂律分布等特性。在复杂网络的环境中,发掘网络中节点的重要性,对于网络的安全防护等应用具有非常重要的意义。本文介绍了在复杂网络环境下,对复杂网络中节点重要性发掘的几个领域,并对其中重要的方法进行了讨论和分析。


参考文献

[1] 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.

[2] Watts DJ,Strogatz SH.Collective dynamics of small-world networks[J]. Nature,1998:440-442

[3] Albert-Laszlo Barabasi,Reka Albert.Emergence of scaling in random networks[J]. Science,1999,286:509-512

[4] 赫南,李德毅,淦文燕,朱熙,. 复杂网络中重要性节点发掘综述[J].计算机科学,200734(12)

[5] 陈静,孙林夫. 复杂网络中节点重要度评估[J].西南交通大学学报,200944(3)

[6] Enrico N,Guido P,Peter W .Finding the Most Vital Node of a Shortest Path[J].Theoretical Computer Science,2003,29(6)

[7] 饶育萍,林竞羽,周东方.网络抗毁度和节点重要性评价方法[J].计算机工程,200935(6)

[8] 陈勇,胡爱群,胡啸.通信网中节点重要性的评价方法[J].通信学报,200425(8)

[9] 李鹏翔,任玉晴,席酉民.网络节点()重要性的一种度量指标[J].系统工程,200422(4)

[10] 谭跃进,吴俊,邓宏钟.复杂网络中节点重要度评估的节点收缩方法[J].系统工程理论与实践,2006,11(11)

[11] 郭伟.野战地域通信网可靠性的评价方法[J].电子学报,2000,28(1)

[12] Chen Y, Hu A Q, Hu X 2004 J. China Institute Commun. 25 129 (in Chinese)

 

作者简介:黄平(1974-),男(土家族),重庆秀山人,工学硕士,高级工程师

彭梦晶(1974-),男,重庆市人(通讯作者)

本刊创刊于1982年,是由自治区科技厅主管、自治区科技信息研究院主办,由自治区科技情报学会协办、国内外公开发行的省级综合性科技刊物,是反映内蒙古自治区科技与经济发展的窗口。杂志入选《中国期刊全文数据(CJFD)》全文收录期刊和《中国学术期刊综合评价数据(CAJCED)统计刊源期刊,《中国核心期刊(遴选)数据库》收录。本刊是公开发行的综合性科技期刊,为月刊,大16开本。本刊坚持以科技创新为目标,融科技、经济、信息、产业、市场为一体,是促进科技成果转化、推动科技进步、加强技术创新,促进经济发展的专业性期刊。