基于广义接近中心性识别网络中多个有影响力的传播源-刘换利.pdf

《基于广义接近中心性识别网络中多个有影响力的传播源-刘换利.pdf》由会员分享，可在线阅读，更多相关《基于广义接近中心性识别网络中多个有影响力的传播源-刘换利.pdf（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、IIIIIL LIIIIII LIIIIlllllll L LIIIIItlIlIII LIIY321 5449墨缒狄孽硕士学位论文学校代码：10357密 级；保密期限：基于广义接近中心性识别网络中多个有影响力的传播源ldentjfying MultiPIe InfluentiaI SpreadersBased on Genera Ii zed C I oseness Centra|i ty学 号姓 名一级学科二级学科指导教师完成时间A14201021刘换利数学应用数学张海峰教授2017年2月万方数据独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，

2、除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得安徽大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：文囊猿销 签字日期： 和门 年，月2-3日学位论文版权使用授权书本学位论文作者完全了解安徽大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权安徽大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。(保密的学位论文在解密后适用本授权

3、书)学位论文作者签名：烫】欤刽 导师签名：签字曰期：20 11年f月幻日 签字日期： lSZ彳久下j缘0，停_办弘知，万方数据摘要IIIIH l U II I II III I IIlY321 5449近年来，对复杂网络的研究已经受到计算机、数学、经济学、传播学和生物学等不同学科领域的关注，网络的结构与动力学是复杂网络科学的两个最基本问题。对于网络结构的探测包括：网络的社团划分，关键节点的识别，链路预测等，其中许多学者都致力于网络中有影响力传播源识别的研究，即找到网络中的一个或者多个节点使得这些节点对网络的影响最大。这一课题在实际生活中对抑制疫情扩散，加速信息传播和推广新产品等都具有重要战略意

4、义。本文主要研究的是寻找一组节点使得这一组节点对网络的影响最大。一个节点到网络中所有节点距离和越小则这个节点越重要，由此我们想到当一组节点到网络中所有节点距离和最小时这组节点对整个网络来说比较重要。基于此思想本文主要有以下两方面工作：1由节点的接近中心性推广到一组节点到所有节点的距离越短越好，进而提出广义接近中心性。因此寻找一组最重要节点的问题转化为寻找目标函数的最优解，之后我们证明可以用Kme&DS聚类模型近似求目标函数的最小值。2用single-contact SIR模型和all-contact SIR及谣言传播模型在实际网络上进行模拟实验，并与度、介数、K一核、着色、最优渗流等方法进行比

5、较分析。结果表明：广义接近中心性指标在signal-contact SIR模型、allcontact SIR模型和谣言传播模型上都表现出较好的结果。关键词：复杂网络：多传播源：广义接近中心性；K-means万方数据Abst ractIn recent years，the study on the complex network has become a hot topicin many disciplines，such as computer science，mathematics，economics，commu-nication，biology and SO onThe structure

6、and the dynamics on the networksare the two fundamental problems in the complex network fieldWith regard-ing to the detection of the structures，which includes the community detec-tion，identifying the key nodes，the link prediction，and SO forthEspecially，howto identify one or more influential spreader

7、s in networks has attracted muchattention，since this issue has significant applications，such as how to curb thespread of the epidemic，accelerate the dissemination of information and pro-mote new productsIn this thesis，we mainly study how to find a set of nodes tomaximize their influence on the netwo

8、rkInspired by the definition of closenesscentrality for a node，which highlights that the importance of a node is charac-terized by the distance of the node to the all other nodes，the smaller distanceleads to the more importance of the nodeSo we proposed a generalized close-ness centrality index for

9、a set of nodes，which emphasize that the set of nodesare more important if their distances to other nodes are smallerBased on thisidea，our thesis includes the following two aspects：1We first put forward a generalized closeness centrality index character-ized by an objective functionTherefore，the prob

10、lem of finding a set of the mostimportant nodes is transformed into the optimal solution of the objective function，then we prove that the minimum value of the objective function can beapproximately obtained by Kmean clustering2The simulation experiments are implemented on actual networks usingsingle

11、-contact SIR model，all-contact Sir and rumor propagation model，and theresults are compared with the methods such as degree，betweenness，Kshelldecomposition method，coloring and optimal percolationThe results show thatthe performance of generalized closeness centrality index is generally betterthan the

12、 other centrality indices，no matter of the singlecontact SIR model，II万方数据all-contact SIR model，and the rumor propagation modelKeywords：complex network；multiple spreaders；generalized closeness centrality；KMeansIII万方数据目 录第一章绪论11 引言12识别有影响力的传播源应用前景，13多源传播的最近研究成果，14本文内容及章节安排第二章 复杂网络基本概念及识别有影响力的传播源的主要方法2

13、1引言22复杂网络相关理论与概念，2，21复杂网络的含义，222网络的统计特性23识别多源传播的方法24本章小结，第三章 广义接近中心性及仿真实验 1331 引言，1332广义接近中心性1333仿真实验与结果分析，1734本章小结，26第四章总结与展望 2741总结，27IV4444672万方数据4，2展望。27参考文献致谢攻读硕士学位期间的学术活动及科研成果V293435万方数据第一章绪论第一章 绪论弟一旱 硒比11 引言我们是不是每天都通过邮件、手机、电话、社交网络平台与我们的朋友保持联系?虽然道路越来越宽，我们是不是仍然每天体验拥堵的交通?在炎炎夏日，我们是不是体验过由于局部故障导致的大

14、范围停电?各种传染病(艾滋病，禽流感，非典型肺炎)如何在人类和动物之间传播开来的?我们应该用什么样的免疫策略?为什么谣言传播的很快?怎样的策略是好的营销策略?这些生活中随处可见的例子与我们的复杂网络研究息息相关。网络模型在我们的生活中处处可见，如传统的论文引用网【1】、新陈代谢网【2】、电力网【3】、交通网【4】等加上之后由于社交网络的广泛使用出现的如：国内的人人网|5】、美国的FacebookN等。研究这些网络可以给我们的生产生活带来极大便利，如：抑制疾病、谣言的传播，切断某些线路避免大面积停电，避免局部金融危机引发全球经济动荡等。然而这些问题的解决都需要我们寻找网络中一个或者多个重要节点，

15、控制这些对整个网络有重要影响的节点使我们解决问题更为方便快捷。12识别有影响力的传播源应用前景网络中的传播过程一方面依赖于网络的拓扑性质【718】，另一方面受动力系统影响【9_12l。在传播过程中寻找有影响力的传播者是一个重要课题，初始感染的源节点在网络中的位置对病毒、谣言、新闻等在整个网络的传播范围有重要影响。寻找网络中有影响力的传播者的问题即是寻找网络中影响力较大的单个或者一组节点。寻找单个有影响力的传播源即是关键点识别，寻找多个有影响力的传播源即是寻找一组他们相互之间的影响小，对整个网络的影响大万方数据安徽大学硕士论文：基于广义接近中心性识别网络中多个有影响力的传播源的节点。识别网络中有

16、影响力的节点在许多领域都有应用。在国家政治安全领域比如：恐怖组织网络【13，如果能正确的分析各个节点在网络中的影响力，就能找到具有最大影响力的节点进而有助于快速定位并捉拿恐怖组织的关键人物，更好的维护全球人民安全和政治稳定；在人类社会生活领域比如：随着全球社交网络的迅猛方展，全球有至少四分之一的用户活跃在社交网络上，研究这些社交网络有助于挖掘网络中的核心用户，在谣言发生时能更有效的进行遏制，净化网络空间，也可以利用这些核心用户进行新产品的宣传和推广；在医药领域比如：因为一些传染病疫苗不仅价格不菲，并且数量极其稀少，让每个人都能够接种相应的传染病疫苗是不可能的。怎样最大程度上利用数量稀少的传染疾

17、病疫苗?对甲型流感、艾滋等一些严重的传染疾病，如果首先能够对那些在网络中有重要影响力的节点接种疫苗，就可以达到相对比较好的治疗效果，在分配甲型流感等成本相对较高的疾病疫苗时，尤其对于那些经济落后的发展中国家和地区而言，这种做法可能是最有效的。因此识别网络中有影响力的节点具有广泛的应用前景。13 多源传播的最近研究成果到目前为止，国内外关于寻找网络中具有影响力的传播源已经取得了不少的研究成果。对于单源传播，我们只需找一个在网络中重要性最高【14,15的节点即可。对于多个有影响力的传播源的识别则要求传播源之间尽量比较分散以减少传播源之间的相互影响。在40多年前Corley and Chang【16

18、】开始研究在有向网络中寻找一组影响最大的节点，他们认为当把一组重要节点移除后将导致指定节点对之间的最大流量大幅度减少；之后Corley and Sha【1 7】认为在有权有向网络中，当一组重要节点移除后将导致指定节点对之间的最短距离增加；Flaviano18,19等人提出最优渗流理论，他们认为对网络影响最大的一组2万方数据第一章绪论节点即是移除这组节点之后对网络连通性破坏最大的一组节点；Cook和Karp12021】等人之后提出了反馈集的概念，这些都是基于网络的拓扑结构提出的寻找网络中的多个有影响力的传播源方法。Domingos和Richardson22,23】首先提出了顾客购买特殊产品的可能

19、性是产品内在性质和其他顾客影响力的函数，这个首先开启了研究功能型的影响最大化问题。之后Kempe，Kleinberg andTardos24基于动力传播系统提出了节点变成活跃节点受他邻居节点影响，所以有线性阈值模型【25-2T和独立串联两种广泛应用的模型【28,29】。14本文内容及章节安排本文以复杂网络理论为基础，通过阅读大量相关文献，研究了许多识别网络中多个传播源的方法，在此基础上，提出了新的多源传播的方法：广义接近中心性的模型，并在四个网络上进行验证，都取得了较好的效果。本文主要章节内容安排如下：第一章：主要介绍了复杂网络中多个有影响力的传播源的研究意义和应用前景以及研究现状，最后给出了

20、本文的章节安排。第二章：首先介绍了复杂网络的定义，以及网络中包含的节点、度、边等的概念，在这个基础上，之后介绍了几种网络模型即规则网络、ER随机网络、小世界网络和无标度网络随后介绍了聚类系数、同配系数等。然后介绍了几种经典的节点重要性排序算法，包括特征向量中心性、接近中心性、介数中心性、K一核分解等最后重点介绍了着色和最优渗流和度折扣理论。第三章：介绍广义接近中心性模型，并用KMeans聚类方法对我们提出的广义接近中心性算法迸行近似求解，最后在Email、PB、Power、Router四个网络上进行仿真实验和结果分析。第四章：对本文的工作进行了小结，提出展望。3万方数据安徽大学硕士论文：基于广

21、义接近中心性识别网络中多个有影响力的传播源第二章 复杂网络基本概念及识别有影响力的传播源的主要方法21 引言网络虽然只有点和边两个因素组成，但是网络是相当复杂的。首先对于点来说，网络中的点可能代表不同类型的个体，比如对于学生选课这样一个二分网络，节点既可以代表学生类，又可以代表课程；另外网络中的点可能具有混沌或分岔等复杂非线性行为动力系统。其次网络中的边连接错杂混乱，并且随着时间的推移网络中的边连接情况可能也会发生变化。网络的复杂性决定了对于同个问题，不同研究思路就会有不同的方法，对于寻找网络中有影响力的传播源我们就可以提出许多种方法，在这一章中我们从不同的方面列出了主要的6中方法。22复杂网

22、络相关理论与概念221 复杂网络的含义自然界和人类社会中存在大量的复杂系统都可以通过形形色色的网络加以描述。一个典型的网络是由许多节点和连接两个节点之间的边组成，其中节点(也可以称为顶点)代表真实系统的不同个体，边则表示个体间的关系。如果两个个体之间有某种特定的关系，则节点之间有一条边。反之，则不连边。有边相连的两个节点是邻居。一个具体网络可抽象为一个由点集y和边集E组成的图G=(K E)。节点数记为N=Iyl，边数记为M=IEI。E中每条边都有y中一对节点与之相对应。如果节点对(忱，)与(，忱)对应同一条边，则该网络称为无向网络，否则称4万方数据第二章 复杂网络基本概念及识别有影响力的传播源

23、的主要方法为有向网络。如果给每条边都赋予相应的权值，那么该网络就称为加权网络，否则该网络称为无权网络。本文所研究的网络都是无权无向网络，因此下文所提到的网络均指无权无向网络。我们生活中常见的网络大体可以分为四类：第一类是技术网络如；电力网络、交通网络等；第二类是社会网络如：人际关系社会网络【30】、Facebook、，Twitter等；第三类是信息网络如：万维网、论文引用网等；第四类是生物网络如：蛋白质交互网32】、新陈代谢网络【33】等。在复杂网络中我们通过对实际网络的结构进行研究可以把网络分为规则网络，ER随机图，小世界网络，无标度网络四类。(1)规则网络【34】全局耦合网络：网络中任意两

24、个节点间都有一条边相连。最近耦合网络：网络中每个节点只和它的邻居节点相连。星型耦合网络：网络中有一个中心节点，其余节点都只与中心节点相连，而他们彼此之间不连接。(2)随机图【35，36】与完全规则网络相对的是完全随机网络，其中最经典的是ER随机图模型，它有两种形式：一种是具有固定边数的G(，M)的随机图，从个节点中每次随机选取一对节点相连，重复M次后得到一个包含个节点，M条边的ER随机图模型；另外一种是边数不固定，连边概率一定的G(，p)随机图，把个节点中任意两个以概率P相连。(3)小世界网络模型【3738】介于完全规则网络和完全随机图的之间的是WS小世界模型。WS小世界模型构造算法为：首先，

25、取一个含有个点的环状最近邻耦合网络，其中每个节点都与它左右相邻的各K2节点相连，K是偶数然后以概率p随机地重新连接网络中的每个边，即将边的个端点保持不变，而另一个端点随机从网络中剩下的节点中5万方数据安徽大学硕士论文：基于广义接近中心性识别网络中多个有影响力的传播源选择。其中规定，任意两个不同的节点之间最多有一条边，且每一个节点不能与自身相连。实际上当p=0时就是完全规则网络，P=l对应于完全随机网络。通过对参数p的调节可以实现从规则网络到随机网络的过渡。(4)无标度网络模型【39】不同于ER随机图和WS小世界模型的度分布近似于泊松分布(在度平均值处有一峰值，之后呈指数递减)像Internet

26、、WWW、科研网等不同领域的众多网络的度分布具有幂律形式，这类没有明显特征长度的网络称为无标度网络。无标度网络考虑了实际网络的两种特性，一个是增长特性即网络是不断有新的边和点加入；一个是优先连接特性即新的节点更倾向于与大度节点相连。这种现象即是所说的“富者更富”或“马太效应”。这两个特性也构成了无标度网络的构造算法。222 网络的统计特性(1)度【351节点的度是指网络中与该节点连接的边的数目，它表示个体在网络中的影响力和重要程度，度越大的个体，其影响力也就越大，在整个组织中的作用也就越大，反之亦然。节点Vi的度k仇定义为：i=Z atj (21)j=l其中，忱和之间有边相连时，aij=l，反

27、之，aij=O。网络的平均度即是网络中所有节点的度的平均值称为，记为(尼)，分布函数P(后)描述的是网络中节点度的分布情况，分布函数P(尼)意思是随机选择一个节点，它的度恰好为k的概率，也表示网络中度为k的节点数量占网络节点总个数的比值。(2)聚类系数【35】聚类系数表示网络中节点的聚集程度的系数，度量某个节点的两个邻居6万方数据第二章 复杂网络基本概念及识别有影响力的传播源的主要方法是邻居的平均概率。网络中节点破的聚类系数GG 2毒2鑫 仁2，其中，节点虢的度为乃，E是节点钦的忌个邻节之间实际存在的边数；赢是邻居间最多可能存在的边数。表示网络的聚类系数。1 c=专Gi=1(23)(3)同配系

28、数【35网络的同配性即是属性相近的节点更倾向于互相连接。这里说的节点属性可以是度值，也可以也是我们说的其他的如：信仰、年龄等特性。比如社会关系网中精英人士更多的与精英人士建立关系；大度节点倾向于与大度节点相连等。已有研究表明，网络的同配或者异配对于网络的鲁棒性和传播具有显著的影响。本文用到的同配系数采用如下定义： r=最豢禹笨糕眨412M ，r：=二二=一 I Z I。 M。l烈Ji+蟹)一( -1i j+砬)】2 r7其中，ji和ki分别为第i条边的两个端点的度数，M为网络中边的条数。若同配性系数70，则网络是同配的，否则网络是异配的。实际网络中，技术网络一般是异配的，而社会网络通常是同配的

29、。23识别多源传播的方法我们希望找到一组重要节点，当这组节点作为传播源时对整个网络影响最大，这实际上就是影响最大化问题即IMP(Influence maximization problem)：对于给定的一个网络G(K E)其eey表示网络节点的集合，E表示网络中边的集合。寻找一组节点S，(其中S冬y且I S I=7,o他=I V I，nO表示选择一组7万方数据安徽大学硕士论文：基于广义接近中心性识别网络中多个有影响力的传播源节点的个数)使得函数，(回达到最大值，(印或者与网络的拓扑结构相关，或者受动力系统影响，受网络拓扑结构影响的IMP是结构型IMP，受动力系统影响的是功能型IMP。影响最大化

30、问题是一个NP-hmd问题，因此我们找不到精确解，只能用近似解代替。我们这里介绍6种方法来找网络中影响最大的一组节点，一类是我们考虑寻找的一组重要节点时要求每个节点本身都比较重要，因此把网络中的节点按重要性进行排序，选择前礼。个重要性靠前的节点组成S。如：基于路径的介数中心性指标：基于节点近邻的K一核分解方法等；第二种，我们希望寻找的节点在网络中能分散开来，节点之间的距离尽可能大。因此我们介绍了着色理论、度折扣指标、最优渗流三种方法。(1)特征向量中心性【35】在社会网络中，与其他人联系频繁的人一定比与其他人联系少的人更有影响力，这就是我们说的度中心性，度大的节点对网络的影响也比较大。度中心性

31、是节点的邻居赋予其的“中心性值”，那么不同邻居的重要性不同，赋予其的重要性也不同，即某个节点的重要性不仅与邻居的数量有关，也受邻居节点重要性的影响。因此1978年Bonacich提出了特征向量中心性翰=咒f1AijxjJ(25)其中翰表示节点Vt的特征向量中心性，Af表示邻接矩阵中的元素，斤1是邻接矩阵A中特征值最大的非负值。显然，翰的值一方面随着邻居数量变多而变大，另一方面邻居节点越重要，值越大。(2)介数中心性(BC)t351网络中处在枢纽位置的节点具有较高的重要性，为了刻画这种“桥”的属性，1977年Freeman提出了介数的概念介数即是通过某个节点的最短路径的个数。他认为网络中经过某个

32、节点的最短路径越多，这个节点就越重要在消息传递过程中，介数高的节点经过它的消息传递的路径也多，删除这个节点可能8万方数据第二章 复杂网络基本概念及识别有影响力的传播源的主要方法就会影响整个网络的信息传播。介数中心实际就是某个节点对网络中其他节点对之间信息流动的影响力。饥的介数定义为：iBC(i)=F丝， (26)睁。；磊sCt黜其中，仉。为从节点V。到节点Vt的所有最短路径数目，疵。为从1 Av。到仇的吼t条最短路径中经过Vi的最短路径的的数目。介数中心性对设计网络的通信协议、检测网络瓶颈、优化网络部署等具有实际的应用价值。(3)K一核分解(KS)f35】Kitsak等人提出K一核分解方法，他

33、们认为网络中位于中心的节点往往比较重要。实际上K一核分解是一种粗粒化的重要性分类方法，这种方法把太多的节点分到网络的同一壳。K一核分解过程：首先去掉网络中度为l的节点以及与这些节点相连的边。这时网络中可能会出现新的度值为1的节点，我们在再把这些节点以及和他们的连边去掉。重复此操作，直到网络中没有度为1的节点止。我们这种操作形象上剥去了网络的最外面一层壳。这些被除去的节点以及他们的连边称为网络的l一壳(1一shell)。在剥去了1一壳后的新网络中每个节点的度值至少为2。接下来我们继续剥壳操作，即重复把度值为2的节点以及相连的边去掉直至不再有度值为2的节点为止。我们把这一轮所有被除去的节点及他们之

34、间的连边称为网络的2一壳(2shell)。依次类推，我们可以进一步得到指标更高的壳，直到网络中的所有节点最后都被划分到相应的虹壳中，这就是网络的肛壳分解。网络中每一个节点对应于唯一的k一壳指标并且尼壳中所包含的节点的度值不一定相同。特征向量中心性和介数中心性方法以及k-shell分解，对于多个传播源选择时，只需要取中心性指标排名比较靠前的节点即可，方法简单，但是更实用于单个传播源的情况。但是网络中往往重要性比较高的节点(如度大的，介数大的)聚集到一起，那么这样选择的一组节点则容易造成影响力的冗余，我们希望我们的传播源在网络中尽可能的分散。9万方数据安徽大学硕士论文：基于广义接近中心性识别网络中

35、多个有影响力的传播源(4)着色理论140，41不管是度中心性还是介数中心性、K一核分解等方法选择的传播源更适合单源传播，但实际在许多情况下我们需要选择多个传播源(如给多个人发传单)。在这种情况下，传统的方法选择传播源时只能选择排序靠前的节点如：用度中心性的方法时，只能选择度排在前面的节点，但是这些方法选择的传播源比较集中没有分散开来，容易造成冗余。因此赵等人提出了节点着色理论。给定网络G=(K E)，V，E分别代表网络的顶点和边的集合。设V=V1，V2，VN表示网络中节点的总数为，着色函数为7r，色集C=1，2，+1)，代表图中度的最大值。常用的着色算法是最大度优先的WelshPowell的点

36、着色算法。具体步骤如下：步骤1：由度中心性，把节点按度大小顺序排列，不妨设为。kv2)；步骤2：令7r(耽)=1，i=1；步骤3：若i=N，则停；否则令，C(vi+1)=7()I Ji，Vi，吻相邻)设m为叫G+z中的最小正整数(其中叫G+z的意思是集合G减去集G+z)。令万(钦+1)=m：步骤4：令i=i+l，转至步骤3。在以上算法中代表顶点虢的度数，丌池)=m表示顶点着色。给网络中每个节点着色之后，我们把网络分成若干个集合，在每一个集合中任意两个节点之间没有直接的连边。之后我们选择度最大的节点所在的集合中前讫。个节点作为传播源。对于介数着色，K一核着色方法一样，只需把度换成另外两个中心性指

37、标即可。(5)度折扣的启发式算法(DDH)假定节点饥是节点的邻居，当我们把节点吻选作传播源后，在我们之后10万方数据第二章 复杂网络基本概念及识别有影响力的传播源的主要方法考虑节点是不是传播源的时候，计算节点Vi的度时应该打一下折扣。这时节点地的度应该等于实际的度k减去即其中仇表示节点虢的邻居中已经是传播源的节点的个数。DDH方法的计算步骤如下142】：S表示传播源的集合，初始状态S=彩；tvi表示节点忱的邻居中已经是传播源的节点的个数，仇的初值为0，p表示在某一时刻节点是传播源时下一时刻节点虢被衫i感染的概率。步骤1：计算所有节点的度d如，此时d也。=kv；步骤2：选择U=argmax班d也

38、；I ViyS)；步骤3：S=S uu)；步骤4：选择节点U的一个邻居Vt，其中ViyS；步骤5：令t咙=t仇+1；步骤6：计算ddvi=dvi一2t仇一(也。一z陇)t陇p；转至步骤2。一直到S中含有我们需要的传播源个数为止。(6)最优渗流【18 19渗流就是把网络中部分顶点以及与这些顶点相连的边去掉。最优渗流：对一个有个顶点，M条边的网络，矢量育=(n1，n2，nu)其中当节点Vi被移除时ni=0，否则啦=1。则被移除节点所占的比例为1g 2 1一专 (27)定义G(g)表示删除比例为q的节点后网络中最大连通片所占网络的比例。最优渗流就是找到最少一组节点使得当这组节点被删除后有a(q)=0

39、，即满足qc=minq【0，1】，G(q)=o) (28)用最优渗流寻找网络中的传播源(CI)万方数据安徽大学硕士论文：基于广义接近中心性识别网络中多个有影响力的传播源给定网络G=(V E)，V，E分别代表网络的顶点和边的集合，S表示传播源的集合，初始状态S=彩，步骤l：计算所有节点的C屯(i)值，其中CIL(i)=(k一1)(一1) (29)jeOBall(i，L)其COBall(i，L)表示L步内到达节点Vi的所有节点的集合，OBall(i，L)表示集合边界上的节点，即L步到达节点i的集合；步骤2：U=argmaxCIL(i)，Vivs，S=S u钆)；步骤3：删除节点U，得到一个新网络，

40、返回步骤2。按照这个循环进行下去，一直到找到需要的传播源数目为止。最优渗流和度折扣算法适当的避免了传播源的聚集，一个接着一个的选择传播源，但是每一次循环都必须重新计算CI值和折扣后的度值，计算复杂性比较高。24本章小结在这一章我们首先介绍了复杂网络的定义并从不同的方面对网络进行分类，之后介绍了了网络的统计特性：度，聚类系数，同配系数。下一小节介绍了特征向量中心性，介数中心性，K核分解三种识别重要节点的方法，以及着色，最优渗流，度折扣三种理论。前三种指标直观明了，计算简单但更适合寻找单个传播源；着色理论找到的传播源之间的距离相对比较近；后面的最优渗流和度折扣算法是一个一个的寻找传播源，效率低，且

41、每次需要重新计算CI和度折扣的值，算法复杂度高。12万方数据第三章广义接近中心性及仿真实验第三章 广义接近中心性及仿真实验31 引言网络中节点的接近中心性即是计算节点与网络中其余节点的距离的平均值，一个节点与网络中其他节点的平均值越小节点的接近中心性就越大。接近中心性实际上是利用信息在网络中的平均传播时长来确定节点的重要性。我们由接近中心性启发，用距离的概念提出了广义接近中心性指标即一组节点到网络中所有节点的距离和最小时这一组节点对网络的影响力比较大。我们发现我们的方法选择的传播源比较分散。32广义接近中心性对于网络中任意一个节点地，可以计算该节点到网络中所有节点的距离也=d(，)vjEV(3

42、1)其中d(vi，)表示节点忱，的距离(也是不相似性，值越小两个节点越相似)。也越小意味着节点优越与其他节点相似，有更好的观察视野，节点越重要。特殊的d(vi，哲j)表示节点间的最短路径，则盔可以表示节点的接近中心性。显然，如果要寻找一个网络中的最重要的节点，则这个节点到每个节点的距离和最短即为：argm。in妣) (32)-oViEy如图31a中，如果两个节点的距离表示他们之间的最短路径长度，则节点1就是最重要的节点。依次类推，如果要寻找网络中一组重要节点v(vq丁节点的个数由我们需13万方数据安徽大学硕士论文：基于广义接近中心性识别网络中多个有影响力的传播源a bI 4 h 勰 。r 罗

43、幽 飞 r 属 氏 图31：在这里两个节点的距离定义为最短路径，则在选择一个重要节点时为节点1，它到每个节点节点的距离和14(节点2或者节点6为15)；当选择两个节点时2、6N其它节点的距离是8(1、2或者1、6是10)。一0000001 7280 1 S9-0塥ji0098】009810 107201072-0 2053-020530226902269024810248l一04749-04749，j一00000一3j7。0，30；600093一O1805-f)180501752O1752000530 005304174一O417404052O4052O012300123(c)钾差K 均000

44、0 0 00001 728 0 31791889 030863617 0 0093098l O18050981 -018051072 017521072 017522053 000532053 000532269 -0 4l_42269 04174248l 040522481 040524749 001234749 00123托 i O1645 03(271i 0 l；9 02,1 1i9jiO3；44 000s91图32：示意图：寻找3个有影响力的节点，(a)一个有16个节点的小网络；(b)拉普拉斯矩阵L两个最大特征值对应的特征向量：(c)由Kmeans聚类得到的三个中心；(d)节点2、3、

45、4被选作传播源：(e)在网络中把节点用红色标示出来。14哪On书0OOO加0OOOc1)书，234io789Ol23410、1、kU，Jld燃倒万方数据第三章广义接近中心性及仿真实验要的传播源个数决定，这里不妨设为扎o)，则这组节点应该距离每个节点的距离也是最短(广义接近中心性)。即需要满足：argmi，nd(V，vj)(矿y) (33) 可V这里需要定义一个集合矿与一个节点的距离：d(V，vj)=mind(，vj)(佤V) (34)则(33)式可以表示为：撇myin历F罚miyn眠) (yV) (35)设瓯，玩，瓦是网络中如个节点，S为y中所有距离罚(罚矿，l=1，2，no)最近的点集。则式

46、(35)可以表示为argm。i，n坻)(矿y) (36)罚矿vj6Sl如图3Ib，如果两个节点的距离表示它们之间最短路径长度，则式(36)寻找的最优节点集合(目标选择2个节点)为节点2和6。Kmeans算法【43，44】对上述的广义接近中心性，我们必须对公式(36)这个最优化问题进行求解。对此发现公式(36)类似模式识别中的Kmeans算法。Kmealzs算法可以表示为七arg mjnJI玛-#l JJ2 (37)i=1 XjSl上式玛是第J个向量属性，S=，&，&。)是把数据分成no个类别，肌为集合&的中心(即地到岛中所有节点的距离最小)。若式(37)中I|玛一p112=d(玛，pz)， (38)15万方数据安徽大学硕士论文：基于广义接近中心性识别网络中多个有影响力的传播源式(36)中的罚表示为S的中心。则(36)式与(37)式的唯一区别就是：式(36)中罚是网络中的节点，而(37)肌不一定会是网络中的点，在以后会进行处理。在Kmeans类算法中需要定义Xj表示节点。f的属性，对此首先计算拉普拉斯矩阵的前h个特征值对应的特征向量M，蚝，虼，=玑1，姚，YiNT，然后取玛=协1，yj2，驺)T作为节点的属性。在图39我们说明了特征向量个数h与传播源个数哟之间的关系。定义距离为：d(vi，vj)=|I五一玛旷 (39)所以式(37