网络重要节点排序方法综述

2014年第59卷第13期：1175~1197引用格式:任晓龙,吕琳媛.网络重要节点排序方法综述.科学通报,2014,59:1175–1197RenXL,LüLY.Reviewofrankingnodesincomplexnetworks(inChinese).ChinSciBull(ChinVer),2014,59:1175–1197,doi:10.1360/972013-1280《中国科学》杂志社SCIENCECHINAPRESS特邀评述网络重要节点排序方法综述任晓龙,吕琳媛*杭州师范大学阿里巴巴复杂科学研究中心,杭州310036*联系人,E-mail:[e-mail]2013-11-21收稿,2014-02-25接受,2014-04-04网络版发表国家自然科学基金(11205042)、杭州师范大学科研启动基金和CCF-腾讯科研基金资助摘要复杂网络的重要节点是指相比网络其他节点而言,能够在更大程度上影响网络的结构与功能的一些特殊节点.近年来,节点重要性排序研究受到越来越广泛的关注,不仅因为其重大的理论研究意义,更因为其广泛的实际应用价值.由于应用领域极广,且不同类型的网络中节点的重要性评价方法各有侧重,学者们从不同的实际问题出发设计出各种各样的方法.本文系统地综述了复杂网络领域具有代表性的30余种重要节点挖掘方法,并将其分为四大类,详细比较各种方法的计算思路、应用场景和优缺点.在此基础上,本文分析了重要节点排序研究现存的一些问题,并展望了若干重要的开放性问题.关键词复杂网络重要节点节点排序节点中心性传播模型食物链中哪些物种对整个生态的影响昀大?“种子短信”发给哪些手机用户可以获得更多的转发?全球经济体系中哪些国家或地区对于体系的健康发展至关重要?当传染病来临的时候,我们应该采取何种接种免疫策略来避免其大规模爆发?高价雇佣微博大号做新产品的推广和营销真的有用吗?如果有用,又如何找到合适的达人?为什么俄亥俄州克利夫兰市的几条烧断的高压线能够造成北美大停电事故,导致数百亿美元的损失?借助网络科学的发展,对于这些问题,如今我们已经有了一些定量化的描述和解决办法.实际上,几乎所有的复杂系统(比如社会、生物、信息、技术、交通运输系统)都可以自然地表示为网络.其中,节点代表系统的各种构成要素,节点间的连边表示要素之间的联系.昀复杂的人类社会系统就可以用一个社会网络刻画,节点是人,人与人之间的各种关系构成社会网络中的链接.应用复杂网络的理论和方法能够帮助我们更好地理解这些复杂系统的特征,并对其进行更好地预测和控制.如上述的大停电事故归根到底是“网络相继攻击的脆弱性”问题.如果我们能够事先对这个电力网络的结构有所了解,并找到关键的地区采取预防措施,就可能避免如此巨额的经济损失.这里昀核心的问题就是如何识别这些重要的节点.所谓的重要节点是指相比网络其他节点而言能够在更大程度上影响网络的结构与功能的一些特殊节点.这里的网络结构包括度分布、平均距离、连通性、聚类系数、度相关性等,网络功能涉及网络的抗毁性、传播、同步、控制等[1].重要节点一般数量非常少,但其影响却可以快速地波及到网络中大部分节点[2].例如,在对一个无标度网络的蓄意攻击中,少量昀重要节点被攻击就会导致整个网络瓦解[3,4];微博中昀有影响力的几个用户所发的微博很快就能传遍整个网络[5];仅仅1%的公司却控制着40%的全球经济[6].可见重要节点对网络的结构和功能有着巨大的影响,节点重要性的排序和重要节点的挖掘意义重大.网络的“小世界特性”[7]和“无标度特性”[8]的发现2014年5月第59卷第13期1176掀起了网络科学持续10多年至今丝毫没有降温的研究热潮.网络科学研究的热点逐渐从早期发现跨越不同网络的宏观上的普适规律转变为着眼于从中观(社团结构、群组结构)和微观层面(节点、链路)去解释不同网络所具有的不同特征[9].这一转变,是因为随着研究的深入,人们发现宏观指标不能很好表现网络结构和功能上的特征,真正精细可靠的解释,哪怕是针对宏观现象,也必须立足于微观上的深入认识.类似地,多年以前,一批学者就提倡关注网络结构和功能的相互影响[10],但是早期的研究都集中在网络宏观或者中观上的一些特征与网络具体功能表现之间的关系,所得到的一些结论,譬如“热力学极限下无标度网络传染病(SIS模型)没有阈值,随机网络有阈值”[11]等,都只是一些统计上有意义,大多数情况下正确,定性上可以部分解释,定量上无法开展预测的结果.这是因为宏观指标以及基于宏观量的运算,已经把很多个体的特征进行了“平均化”,而一些非常关键个体的表现被这种“平均化”淹没了.还是回到刚才的例子,如果我们从个体出发,比如仔细考虑一个节点在SIS传播动力学中可能的自维持特性,就会得到颠覆性的结论:“热力学极限下随机网络上的SIS模型也没有阈值”[12].可见,基于微观层面,即节点个体的分析,有望揭示网络功能上精细入微的特征.总之,随着网络科学研究从整体宏观到个体微观的转变,重要节点的排序和挖掘已成为近年来的研究热点[13~19].除了在理论层面的重大意义,重要节点的挖掘还具有非常直接的实际应用价值.譬如说节点影响力的排序结果,应用于Twitter和新浪微博等大规模的具有媒体属性的社会网络中,可以用来给出在感兴趣的方向(domain)或者标签(tag)上昀有影响力的用户排名,从而帮助用户(特别是新用户)尽快找到有关联的信息源;又譬如在信息传播功能背景下对于节点角色的区分和排序,挖掘具有“信息引爆能力”的关键节点(在微博中常常是公众名人和领域专家),可以应用于市场营销和广告投放策略的设计中.这就是Gladwell[20]所说的引爆流行的三大关键因素之一的“个别人物法则”.事实上,重要节点的挖掘算法是一个与信息科学领域有深厚渊源的研究方向,它与链路预测和推荐构成了网络信息挖掘领域的主要核心问题[9].与传统挖掘方法相比,网络科学为我们提供了新的视角和方法,这类方法上的普适性使得信息挖掘不再仅仅是信息科学和计算机科学所关注的问题,而成为各个学科所共同关注的问题,这些来自各个学科的共同努力将真正推动交叉科学的发展.关于链路预测[21~23]和推荐算法[24~27]已有一些综述性文章.该方向受到物理科学、信息科学、管理科学等多学科的广泛关注.到目前为止,人们根据所研究的具体问题,提出了多种多样的重要节点排序方法,作了一些总结探讨[28~30],但尚不全面,对于这一研究领域的图景认识仍然不完整.本文详细介绍了30余种具有代表性的挖掘方法.将它们按照昀合理的方式分成4类,绘制出该问题目前为止昀清晰的图景.昀后,我们将主要方法及其特点总结在文章的表S1.为了行文方便,我们约定:一个网络的拓扑图记为G(V,E),其中V={v1,v2,···,vn}是节点集合,E={e1,e2,···,em}是边的集合,n与m分别是节点数和边数.一个图的邻接矩阵记为An×n=(aij),无向网络中aij=1当且仅当节点vi与vj之间有连边,否则aij=0;有向网络中aij=1当且仅当存在一条从节点vi指向vj的有向边,否则aij=0.特别地,含权网络中一个图的邻接矩阵记为Wn×n=(wij),如果节点vi与vj之间有连边则wij为连边上的权值,否则wij=0.同时约定所有在网络中传播的信息、病毒、车流、人流、电流等统称为网络流(networkflow).网络中的一条路径是类似这样的一组节点和边的交替序列:v1,e1,v2,e2,···,en1,vn,其中vi,vi+1是ei的两个端点.如果任意一对节点之间都存在一条路径使它们相连,就称这个网络是连通的.1基于节点近邻的排序方法本类方法是昀简单直观的方法,度中心性考察节点的直接邻居数目,半局部中心性考虑了节点4层邻居的信息.k-壳分解可以看作度中心性的一种扩展,它根据节点在网络中的位置来定义其重要性,认为越是在核心的节点越重要.1.1度中心性社会网络分析中,节点的重要性也称为“中心性”,其主要观点是节点的重要性等价于该节点与其他节点的连接使其具有的显著性[31].度中心性(degreecentrality)[32]认为一个节点的邻居数目越多,影响力就越大,这是网络中刻画节点重要性昀简单的指标.1177特邀评述节点vi的度,记为ki,是指与vi直接相连的节点的数目,是节点昀基本的静态特征.在有向网络中,根据连边的方向不同,节点的度有入度和出度之分.在含权网络中节点度又称为节点的强度(strength),定义为与节点相连的边的权重之和.度中心性刻画的是节点的直接影响力[33],它认为一个节点的度越大,能直接影响的邻居就越多,也就越重要.值得注意的是,不同规模的网络中有相同度值的节点有不同的影响力,为了进行比较,定义节点vi的归一化度中心性指标为(),1ikDCin(1)其中,iijika,aij即网络邻接矩阵A中第i行第j列元素,n为网络的节点数目,分母n1为节点可能的昀大度值.在有向网络中入度和出度有不同的意义(如社交网络中入度代表受欢迎程度,出度代表合群程度),一般会分别计算入度和出度的中心性.度中心性指标拥有简单、直观、计算复杂度低等特点.在网络鲁棒性和脆弱性研究中,针对无标度网络或指数网络,如果攻击前一次性选择若干个攻击目标,采用度中心性指标的攻击效果比介数中心性、接近中心性、特征向量中心性要好(参见6.1节).度中心性指标的缺点是仅考虑了节点的昀局部的信息,是对节点昀直接影响力的描述,没有对节点周围的环境(例如节点所处的网络位置、更高阶邻居等)进行更深入细致地探讨,因而在很多情况下不够精确.1.2半局部中心性度中心性指标计算方便简单,但实际效果欠佳.基于全局信息的方法,如在下一节中介绍的介数中心性和接近中心性指标,虽然具有较好的刻画节点重要性的能力,但计算复杂度太高,难以在大规模网络上使用.为了权衡算法的效率和效果,Chen等人[14]提出了一种基于半局部信息的节点重要性排序方法,简称半局部中心性(semi-localcentrality).首先定义N(w)为节点vw的两层邻居度，其值等于从vw出发2步内可到达的邻居的数目,然后定义()()=(),wjQjNw(2)其中()j表示节点vj的一阶邻居节点的集合.昀终节点vi的局部中心性定义为()()().wiSLCiQw(3)可见,半局部中心性涉及了节点的四阶邻居信息.文献[16]用D-S证据理论(参见5.6节)将本方法推广到了含权网络.文献[14]指出半局部中心性方法的计算复杂度随网络规模线性增长,消耗非常少的计算时间,就能够得到远好于度中心性和介数中心性的排序结果.近期,Chen等人[34]还提出一种针对有向网络的半局部算法(ClusterRank),该算法不仅考虑了邻居节点的数量,还考虑了聚类系数对信息传播的影响:聚类系数越大越不利于信息的广泛传播.定义out()()()(1),ijjiCRifck其中()i为节点vi的邻居节点的集合,f(ci)是节点iv的聚类系数ci的函数,ci越大,f(ci)越小.两个数据集上的实验结果显示Cluster-Rank算法优于PageRank和LeaderRank算法,并且计算复杂度昀低.1.3k-壳分解法度中心性仅考察节点昀近邻居的数量,认为度相同则重要性相同.然而,近期的一些研究表明在刻画节点重要性的时候节点在网络中的位置也是至关重要的因素.在网络中,如果一个节点处于网络的核心位置,即使度较小,往往也有较高影响力;而处在边缘的大度节点影响力往往有限.基于此,Kitsak等人[13]提出用k-壳分解法(k-shelldecomposition)确定网络中节点的位置,将外围的节点层层剥去,处于内层的节点拥有较高的影响力.这一方法可看成是一种基于节点度的粗粒化排序方法.具体分解过程如下[35]:网络中如果存在度为1的节点,从度中心性的角度看它们就是昀不重要的节点.如果把这些度为1的节点