陆君安湖北省数学建模会20120707宜昌

网络传播中最具影响力的节点陆君安武汉大学数学与统计学院E-mail:[e-mail]湖北省数学建模会20120707宜昌Abstract本报告讨论什么叫“网络中最具影响力的节点”；对衡量节点影响力的度（degree）、中心度(K-shell)和介数(betweenness）和其它属性，以及PageRank和最新提出的LeaderRank作一评价。Outline1.背景2.衡量节点的影响力:度,中心度(K-shell)和介数(betweenness）3.衡量节点影响力的其它属性4.GooglePageRank算法与其它方法5.总结1.背景复杂网络无处不在万维网(K.C.Claffy)自然科学论文引用网络互联网(WilliamR.Cheswick)复杂网络无处不在酿酒酵母基因调控网人类疾病网络细胞信号网络Cell,2000,100:57-70.Manyrealworldnetworkshavethesameinternalstructure:小世界,无标度,高聚类小世界、无标度特性发现的重大意义从根本上颠覆了传统随机网络（RandomNetwork）模型，在许多领域提出反思。应用广泛，例如：Internet,通信网络，搜索引擎，交通网络，电力网络，社交网络，疾病传播与免疫策略，生物网络，生态网络等。《Science》2009专辑《ComplexSystemsandNetworks》复杂网络是一个日新月异的研究领域，特别是最近十多年来已经取得丰富的成果。但是，待研究的问题和新产生的问题仍然许许多多，特别在应用方面还有很长的路要走。NaturePhysics2012第一期发表Albert-LászlóBarabási题为“Thenetworktakeover”（网络取而代之）,指出:还原论作为一种范式已是寿终正寝,而复杂性作为作为一个领域也已疲惫不堪.基于数据的复杂系统的数学模型正以一种全新的视角快速发展成为一个新学科:网络科学。Reductionism,asaparadigm,isexpired,andcomplexity,asafield,istired.Data-basedMathematicalmodelsofcomplexsystemsareofferingafreshperspective,rapidlydevelopingintoanewdiscipline:networkscience.这几年互联网最活跃的是在线社会网（OnlineSocialNetworks）,全球超过8亿用户的社交网络Facebook即将上市，估计市价将达1000亿美元，瞬间成为世界级巨无霸的企业之一。在中国，新浪微博、腾讯微博等以更快的增长率在一年多时间里吸引了上亿用户，并在一系列重大事件中展示了巨大的影响力。这里有许多重要的理论问题和实际问题需要回答。本报告“网络传播中最具影响力的节点”虽然是网络科学中的一个重要的基本问题，但仍然在探索中，绝不是一句话能够回答的。什么叫节点影响力？衡量节点影响力有哪些指标？具有什么属性？各自的优劣？适合不同场合反映影响力？最具影响力人物2011年，美国《时代》周刊，全球最具影响力人物100强。韩国歌手Rain位居榜首。此外，美国社交网站Facebook首席执行官马克.扎克伯格、谷歌公司首席执行官拉里.佩奇以及新浪网首席执行官曹国伟都入选100强。2010年，美国《福布斯》“全球影响力人物排行榜”。胡锦涛超过奥巴马成为2010年度全球最具影响力人物。沙特国王阿卜杜拉位居第三。普京位居第四。排名依据：看一个人物是否能影响一群人。看所在国家的人口；企业家的雇员规模；媒体受众人数；拥有的财富。2009年“全球最具影响力人物”奥巴马、胡锦涛、普京位列榜单前三位。《福布斯》依据他们影响力所及人数、在最直接影响范围之外发挥力量的能力、对金融资源的控制力以及积极施展能力的程度。问题：给你一个复杂系统（网络），问哪一个（一些）节点最重要、最具有影响力？网络传播中最有影响力的节点实际复杂系统复杂网络最重要的成员最具影响力节点（一个重要的基本问题）应用疾病传播中哪些节点最具有感染力，在疾病疫苗中如何考虑重点人群？在研究攻击和防御中要抓哪些重点节点？在社会传播网络中怎样控制谣言的扩散？在商业市场中如何制定宣传策略、开拓市场？在工程中哪些节点需要优先控制？在电力网络中，对重要的断路器、发电单元等进行保护，可以有效防止由相继故障引起的大范围停电……2012美国大学生数学建模竞赛C题——犯罪克星建模犯罪建模中心（ICM），正在调查一个实施犯罪行为的阴谋。调查人员已经知道策划阴谋的一些成员，但是希望在逮捕嫌疑人之前确定其它的犯罪成员和组织的头目。所有的嫌疑人和可能涉嫌的同谋都受雇于同一家公司，在一个大的综合办公室里工作。ICM已经获得了一些他们的流通信息，这将帮助他们找到最有可能的未知身份的同谋者和组织领导人。83个节点，400条边，超过21000个字符的信息传输，15个主题（7，11和13被视为是可疑的），7个是已知的同谋者，还有8个已知的非同谋者，数据在附件中。应用实例要求：建立一个模型和算法对83个人是罪犯的可能性大小进行排序。要用到：理解文本信息的技术—语义网消息传输分析，人工智能和计算语言学方法。希望提供的方法将有助于解决世界各地重大案件，尤其是那些拥有非常大消息传输的数据库。方法要求能够推广到生物网络中找感染节点，找到感染或患病的细胞的位置？什么叫网络传播中最有影响力的节点？没有统一的定义Influentialspreaders（nodes）incomplexnetworks考虑网络传播中最有影响力的节点一般可以这样定义:如果要比较网络中节点的影响力,则以这个节点为感染源,利用SIS或者SIR模型(描述疾病传播以及信息和谣言传播的模型),通过计算同一时段的传播规模或者网络全部被感染所需时间。那么,传播规模最大或者全部被感染所需时间最短的那个节点称为最有影响力的节点。我们计算的结果表明,传播规模比全部被感染所需时间更适合准确刻画影响力。节点的度（degree）：节点的连边数节点介数(nodebetweenness)和边介数(edgebetweenness),节点介数衡量了通过该点（边）的最短路径的数目,反映了节点（边）在网络中的枢纽性,节点介数越大,说明删除这样的节点（边）会造成大量节点对之间的最短路径变长。K-shell(中心度)：节点位于网络的层次，在核心的位置常用节点属性度大的节点介数不一定大，度小的节点介数也不一定小网络节点的中心度或者核心度（K-shell）Bollobas,B.GraphTheoryandCombinatorics:ProceedingsoftheCambridgeCombinatorialConferenceinhonorofP.Erdos,35(Academic,NewYork,1984)去掉度为1的节点，在此基础再去掉度为1的节点，直到没有度为1的节点，就得到Ks=1的节点；再去掉度为2的节点，依次进行，得到Ks=2的节点;…。这样，网络的外壳和边缘的Ks为1，然后往内像剥洋葱一样进入网络的核心（K-shell值大的区域）。Ks越高就说明这个节点更靠近网络核心。度大的节点k-shell不一定大如果一个hub节点位于网络边缘，它的度很高，但是Ks=1，它在传播过程中的影响可能微乎其微，而某个度数比较小的节点位于网络的核心将对传播过程产生重大影响。目前大多数人相信，具有更多连接的节点（hubs）是大规模网络传播的最具影响力的节点[1-3]。在社会网络理论中，一个节点拥有更多的人际影响往往与高介数(betweenness）相关[4，5]，因为高介数的节点有更多的最短路径通过。于是在疾病控制、免疫、工程控制中要重点控制这样的节点。[1]Albert,R.,Jeong,H.,&Barabasi,A.-L.Errorandattacktoleranceofcomplexnetworks.Nature406,378–482(2000).[2]Pastor-Satorras,R.&Vespignani,A.Epidemicspreadinginscale-freenetworks.Phys.Rev.Lett.86,3200–3203(2001).[3]Cohen,R.,Erez,K.,ben-Avraham,D.&Havlin,S.BreakdownoftheInternetunderinten-tionalattack.Phys.Rev.Lett.86,3682–3685(2001).[4]Freeman,L.C.Centralityinsocialnetworks:Conceptualclarification.SocialNetworks1,215–239(1979).[5]Friedkin,N.E.Theoreticalfoundationsforcentralitymeasures.Am.J.ofSociology96,1478–1504(1991).2010年11月发表在《NATUREPHYSICS》第6卷上的文章《Identifyinginfluentialspreadersincomplexnetworks》，作者是BostonUniversity的MaksimKitsak等7位学者。文章提出不同的看法。识别网络中有影响力的传播者这篇文章的作者调查(1)340万市民的LiveJournal.com友谊网络,(2)伦敦大学计算机科学系的学院电子邮件联系网络,(3)在瑞典收集的医院住院病人的接触网络(CNI),以及(4)由imdb.com标记为在同一电影中有合作的演员网络，并且通过SIR模型和SIS模型的建模分析指出:对于单个传播源低感染率情形，Hubs节点或者高介数的节点不一定是最有影响力的节点，而通过K-shell分解分析确定的网络核心节点（即K-shell值大的节点）才是最有影响力的节点。以CNI网络为例(每一种进行10000次,传染概率0.035)说明感染规模不一定与感染源节点的度k有关,hubs可能不是很好的传播者.灰色背景是网络,图b,c说明传播过程即使从各个度数相同的Hubs开始,结果也可能会非常不同,图b的Ks大.相反,图b,d表明,感染源节点的Ks指数相同,可以更准确地预测感染的规模.平均扩散范围依赖于Ks，而不依赖于K和介数Cb(单个传播源情形)在SIR模型，给定感染源的k，Ks值平均传播规模M(Ks,k).表明:1.固定度,M(Ks,k)的分布广泛,有很多位于网络外围的Hub传播者(高K低Ks);2.固定Ks,M(Ks,k)近似与节点度无关；3.最有效的传播者位于网络的核心(Ks大).介数类似.因此K-shell可以更好地预测疾病传播。当传染病在在网络的核心（大Ks）爆发，病毒总是可以在网络核心通过许多种路径开始感染其它部分，无论该节点的度是多少这个结论是有效的。这些通路的存在反过来也意味着，在从一个随机节点为源的爆发疫情，位于高Ks节点更有可能早于其他节点被感染（疾病预测）.多个传播源情形这个时候传播的规模很大程度依赖于初始传播源之间的距离。尽管高Ks点是最好的单一传播者，但是在多个传播源情况，度大的Hub节点往往比Ks大的节点具有更高传播效率。这是因为Ks大的节点往往在网络的核心聚集在一起，传播中存在交叉感染现象（感染者传染给感染者），而度大的Hub节点可以分散在网络的不同区域。图中虚线表示仅仅考虑不相连的传播源SF,SW理论模型研究许多实际网络具有度分布无尺度和小世界特性，我们针对ER，SW和SF网络研究传播规律。发现对于SF网络Ks能够最好地反映传播能力，而ER和SW网络节点度更反映传播能力Jun-anLu,Chen-gengTian,PeiWang,IdentifyingInfluentialSpreadersInTheoreticalComplexNetworks,sub