基于Erdos1合著网络和论文引用网络的复杂网络节点特征研究

竞赛论坛基于Erdosl合著网络和论大引用网络的复杂网络节点特征研究2014年6月数学建模及其应用Vol.3 No.2Jun.2014Mathematical Modeling and Its Applications万方数据变赛论坛基于Erdosl合著网络和论文引用网络的复杂网络节点特征研究王新赠U2,闫斌杨红卫V，常正波w(1山东科技大学数学与系统科学学院，山东青岛266590;2.山东科技大学数学建模研究中心，山东青岛266590)摘要：首先，研究了 Erdosl合著网络的特征属性，一方面使用节点的度、介数、接近中心性来描述Erdosl合著网 络节点重要性，另一方面使用特征向量t心性和本文提出的高阶度参数来描述Erdosl合著网络节点影响力；然 后，分别用逼近理想解的排序（TOPSIS算法）算法和主成份分析（PCA)对节点重要性和影响力排序；最后，利用修 改的网页排名（PageRank)算法讨论了网络科学原创性论文中最具影响力的论文。关键词：高阶度;TOPSIS算法；主成份分析；修改的PageRank算法；权威-人气模型中图分类号：0241.3;X8文献标志码：A文章编号：2095-3070(2014)02-0052-120引言复杂网络理论研究的是复杂网络之间的共性和处理它们的普适方法1，复杂网络研究正渗透到数理科 学、生命科学和工程科学等众多不同领域M。对复杂网络定性和定量特征的科学理解已成为网络时代科学 研究中一个极其重要的挑战性课题。在各种复杂网络之中，用定量分析的方法寻找超大规模复杂网络中哪一个节点最重要，或者节点对邻居 节点或者整个网络的影响力，是复杂网络研究中的一个重要问题。但复杂网络描述节点现有的特征属性参 数或多或少不能体现节点的所有属性。度是单个节点的属性中简单而又重要的特征属性8，但一个节点的度仅描述了该节点对于其他节点的 直接影响力，因此有很大的片面性;有些重要的核心节点并不一定具有较大的连接度，比如只有两条边相连 的桥节点。接近中心性M定义为该节点到其他所有节点距离之和的倒数，更多地只是反映了节点在网络中 的居中程度。介数1是指通过节点最短路径的数量，反映了节点对其他节点之间联络的控制作用。节点介 数的计算非常复杂，一般只能采用近似算法特征向量中心性12则是从网络节点的地位或声望角度考 虑，将单个节点的声望看成是所有其他节点声望的线性组合。本文结合上述特征属性参数引入髙阶度参数 来描述网络节点影响力。本文的安排如下:第一部分说明了所研究的两个复杂网络的数据来源和网络构建方法;第二部分介绍了 几个常用的复杂网络特征属性参数，并引入了高阶度的定义，给出了无向网络节点重要性和影响力的定义和 描述参数及算法、有向网络的修改的PageRank算法;第三部分是Erdosl合著网络节点重要性和影响力、网 络科学原创性论文中最具影响力的论文的结果及分析，第四部分是基于结果的一些讨论。1数据来源数据分为两部分，第一部分是Erdos数为1的合作者13，第二部分是网络科学原创性论文。 收稿日期：2014-05-ll基金项目：山东科技大学教育教学研究“群星计划”项目（qx2013226)通讯作者：王新赠，E-mail: wangelxzhotmail_ com 52 第3卷第2期数学建模及其应用Vol_3No.2 Jun.2014首先明确了 511个Erdos数为1的数学家，并对他们按姓名字母排序，编号1，2,，511。假设数学家 之间的关系只由他们是否曾经合作来确定，而与合作次数(在有过合作的情况下)无关，利用公式_ (1,第i个数学家和第）个数学家合作过论文 % = io，第个数学家和第j个数学家没有合作过论文 得到Erdos数为1的合作者网络的邻接矩阵A = a,y5nx511，构建了 Erdosl合作者网络，如图1所示。图1展 示了其中466个节点构成的大组件，其余45个节点要么是孤立点，要么仅仅与45个节点中的另一个相连，删 除它们对节点重要性和影响力是没有影响的。图1 Erdos数为1的合作者网络图第二部分是网络科学原创性论文数据。数据部分来源于2014年ICM附表NetSciFoundation. pdf,并对 它们分别编号1,2,，16。但该附表论文只有16篇，之间的相互引用较少，16篇论文之间仅有20多条有向边，甚至编号7的论文 “Odda T. On properties of a well-known graph or what is your ramsey number? J. Annals of the New York Academy of Sdences，1979,328(l) :166-172” 是孤立节点*。网络中较少的边不能充分体现影响力的 传播，不便于相对影响力研究，所以本文添加了 10篇论文。添加的网络科学原创性论文主要来源于我国复杂 网络方面较为权威的专著复杂网络理论及其应用1，具体添加的论文及其他信息见表1。利用谷歌学术搜索得到论文间相互引用关系及每一篇论文的年均被引用量、论文发表期刊影响因子(编 号为3、12、15、21、25的论文所在期刊2012年影响因子査不到，故取2011年影响因子;编号为6和20的论文 所在期刊査不到影响因子，值取0;其余论文所在期刊取2012年影响因子），结果如表2所示。* ICM_2014原问给出的该论文作者信息有误 53 表1添加的网络科学论文表论文编号论文信息Newman M E J，Strogatz S H,Watts D J. Random graphs with arbitrary degree distributions and their applications J. Physical Review E，2001,64(2) :026118.Bar rat A，Barthelemy M, Pastor-Salorras R，e! al，The architecture of complex weighted networksQ. Proceedings of the National18Academy of Sciences of the United States of America，2004,101(11) ：374?-3752.Amaral L A NScala A,Barthelemy M，et al. Classes of small-world networksJ. Proceedings of the National Academy of19Sciences，2000，97 ( 21 : 11149-11152.Sniiders TAB. Markov chain Monte Carlo estimation of exponential random graph modelsQ. Journal of Social Structure，2002，203(2)： 140.19 Watts D J, The new science of networksJ- Annual review of sociology, 2004:243-270.20 Strogatz S H. Exploring complex networksJ. Nature，2001,410(6825):268-276.Bartheliferoy M，Amaral LAN. Small-world networks ： Evidence for a crossover pictureJ, Physical Review Letters, 1999,82(15)；233180 Holland P W, Leinhardt S. An exponential family of probability distributions for directed graphsJ. Journal of the American24Statistical Association, 1981,76(373) ：33-50.21 Granovetter M. The strength of weak tiesJ, American Journal of Sociology,1973781)阶度。显然S = 1时即节点的度，而一个联通图中每个节点的1，2，一，D(D表示网络直径）阶度之和相同，数值 上等于N 1(该连通图网络节点数减去该节点），说明联通图中每一个节点都能够影响到所有节点。下面给出髙阶度的算法。假设网络6 = 3(7，)，邻接矩阵为7 = (%)，中第行第_/列的元素表 示节点i与节点j之间通路长度恰为m的数目（文献），所以节点i与节点i距离不大于m的概率为：|1，节点与节点距离不大于m io，节点与节点距离大于m其中，V表示析取，也就是当，degree i表;i阶高阶度，2.2网络节点的重要性定义2复杂网络特征属性对一个节点的依赖程度称为该网络节点的重要性。当复杂网络中一个节点被移走时，同时移走了与之相连的所有边，不但其邻居节点度都会减小，而且可 能会使网络中其他节点之间的路径中断或者最短路径长度增加，甚至将联通图变为非联通的，从而改变整个 网络的特征属性，具体来说：1) 移走节点的度越大，随之移走的边越多，网络中减少度的节点越多；2) 移走节点的介数越大，可能更改的最短路径越多；3) 移走节点接近中心性越大，节点越靠近“网络中心”，造成网络路径(不单指最短路径）中断的可能性 越大。所以用节点的度、介数以及接近中心性来描述节点在Erdosl合作者网络中的重要性。2.3网络节点的影响力定义3 复杂网络中一个节点在网络信息传播中起到的作用称为该网络节点的影响力。 56 万方数据第3卷第2期数学建模及其应用Vol.3 No.2 Jun.2014 57 万方数据当信息在复杂网络中传播时，每一个节点的传播能力不但与邻居节点的信息传播能力有关，而且会和邻 居节点的邻居节点信息传播能力有关，甚至和更远但存在通路的节点的信息传播能力有关。(1) 特征向量中心性基于一个节点的中心性值由邻接顶点的值决定的思想，使其值越髙，对邻居节点的 影响力越大，从而影响整个网络的信息传播。(2) 个节点高阶度越大，其邻居节点、邻居节点的邻居节点越多，对整个网络的信息传播影响越 大。所以用节点的特征向量中心性、高阶度描述节点在Erdosl合作者网络中的影响力。2.4 TOPSIS 算法TOPSISCtechnique for order preference by similarity to an ideal solution)算法是 Wang 等】71981 年首 次提出的。TOPSIS算法根据有限评价对象与理想化目标值的接近程度进行排序，在现有对象中进行相对优 劣的评价，是一种逼近于理想解的排序法。设研究有限评价对象集(5= G,，G2,，GJ以及每一个个体的标准化描述参数向量G, = (g,gi，-, gi)0 = 1,2,-,m),而描述参数向量的理想化目标值为Gld, = (gl ,g2，-,gt),则评价对象与理想化目标值 的接近程度一般用欧氏距离Qj = V(gi gi)2 + (gi z)2 H1- (gi g,y = l，2，.，m表示，评价对象集的兑值越小，评价对象与理想化目标值越接近，排序越靠前，反之排序越靠后。利用 TOPSIS算法分别对Erdosl合作者网络重要性和影响力排序。2.5 主成份分析主成分分析(principal components analysis,PCA)是一个线性变换，经常用来减少数据集的维数，同时 保持数据集对方差贡献最大的特征。在Erdosl合作者网络使用的主成份分析分别计算节点重要性和影响 力，由于对节点重要性和影响力描述参数分别为3个和2个,本文只取第一主成份，结论部分证明这样做法 是正确的，重要性和影响力第一主成份贡献率分别为80%和89%。主成分分析具体算法如下。Stepl输人网络m个节点描述参数标准化数据if,_ = iha,ha，-,K),Step2 计算参数标准化数据矩阵= (),的相关系数矩阵K =Step3 计算相关系数矩阵特征值A,，A2，A,(A, A2彡彡A, 0)及相应特征向量奶，a2，a,; Step4输出描述节点的第一主成份及节点相应的排序指标fla,。本文将利用主成份分析分别对Erdosl合作者网络重要性和影响力排序。2.6 修改的PageRank算法PageRank算法是Google创始人拉里佩奇和谢尔盖布林于1997年构建早期搜索系统时提出的网页 链接分析算法，目前很多重要的链接分析算法都是在此基础上衍生出来的。PageRank算法假设一个页面节 点接收到的其他网页指向的人链数量越多，这个页面越重要(数量假设）；质量高的页面会通过链接向其他页 面传递更多的权重(质量假设）。在这两个假设条件下，开始賦予每个网页相同的重要性得分，通过迭代递归 计算来更新每个页面节点的PageRank得分，直到得分稳定为止。本文对经典PageRank算法做了以下3个方面的修改：1) 增加了阻尼系数。在一般PageRank算法中，阻尼系数表示不是从网页链接跳到另一个网页，而是直 接从浏览器地址栏输人网址进人新网页。本文的案例中表示节点传出影响力时会有部分的保留，代表论文创 新的部分影响力。2) 迭代初值不再是均值。显然论文发表初始影响力是和所发表期刊有关的，影响因子越髙的期刊论文 受关注程度越高，权威性越髙，所以将论文发表期刊影响因子标准化后作为论文权威性迭代初值。3) 新增自连接。为防止网络所有节点影响力在迭代中衰减，对只有入度没有出度的边连接一条边指向 自己。这和实际是相符的。26篇论文中有7篇论文只被引用，但是没有引用其他论文(原来题目给出的16篇 论文有4篇），说明这7篇论文是26篇论文中创新性最强的，影响力没有传递给其他论文，而是保留下来。具体算法如下。Stepl输人，输人网络m个节点初始排名向量Wi。= (PR,?，及节点有向连接矩阵V =竞赛论坛基于Erdosl合著网络和论文引用网络的复杂网络节点特征研究2014年6月(Vij)；Step2出度为0的节点新增自连接:计算节点出度如果 =0,对节点i新增自连接，令 =1 且 = 1，f = 1，2，m;Step3迭代:假设第是次节点排名向量为PK* =，计算第A + 1次节点j排名分pj?k数视广=?S + (1 9)，）= 1，2,，/，这里的9是阻尼系数，代表节点没有传递出的信息量百分比。则第&+i次节点排名向量= (PR,pRr,-,pRy；Step4 判断:对预先设定的阈值，如果必对，PJ?*) a，转向Step5,否则A = A + 1转向Step3; Step5 输出：输出节点排名向量FR = (PR,PR2，-,PRm)r = PRk,利用修改的PageRank算法来讨论网络科学原创性论文中最具影响力的论文。2.7 建立权威-人气模型以网络科学原创性论文发表期刊影响因子标准化数据IF,uni = -(7F1?/F2，-,/F)T(2)i = i作为初始排名向量，其中，W指第山=1，2,，m)篇论文发表期刊影响因子，使用修改的PageRank算法 得到节点排名向量FR =，来表示论文权威系数。利用每一篇论文的年均被引用量Citedperyear,(i = 1，2，!)作为论文人气指数，构建权威-人气模型：Model_p, = Model_p(PR, .Citedperyear,) ,i = l，2，.，7n。由于两者数据尺度差异较大，通过双对数坐标系展示模型结果。3 结果3.1 Erdosl合作者网络特征厲性本文通过节点的度、介数、接近中心性来描述Erdosl合作者网络节点重要性（表3)，然后分别利用 TOPSIS算法和PCA来综合考虑。其中，TOPSIS算法中3个参数标准化后理想值向量为GidMl = 1，1，1。表3 Erdosl合作者网络节点重要性表排名度介数接近中心性TOPSISPCA节点编号节点度节点编号节点度节点编号节点接近中心性节点编号TOPSIS节点编号PCA110521879 596100. 000 8341870. 185 011875 408.62165444388 9771650. 000 832100. 279 444385 057.73187443858 566440.000 8294380. 283 313854811.0444434498 3121480.000 8281650. 328 344494 677.45378433557 5534380.000 819440. 347 503554 253.5647940106 9154790.000 8021480. 380 03103 909.77148391486 8942870.000 7974790. 475 901483 889. 98438381656 8293780.000 7973550. 523 271653 856.4944035446 7254490.000 7964490. 531 69443 797.710177323416 0774400.000 7943410. 546 833413 427.5只考虑466个节点、1 860条边构成的大组件，其特征属性如下： 平均度7. 982 8,如果利用幂率分布逼近，可得函数0.198 4:c-_8411，但是逼近效果并不理想，而利用指 数分布逼近可得理想的逼近函数0.199(图3)，可见Erdosl合作者网络度分布呈指数分布； 58 万方数据第3卷第2期数学建模及其应用Vol.3 No.2 Jun.20140 180.16Erdosl合作者网络度分布 1 = 1,1,表4 Erdosl合作者网络节点影响力表排名特征向童中心性混合度T0PSISPCA节点编号特征向量中心性节点编号混合度节点编号T0PSIS节点编号PCAl100. 259 7910114.671001081.26823780. 234 05165113.333780.120 7816580.2813440. 208 9644112.17440.196 894479.46441650.203 96148112.171650.215 2314879.45651480.197 28438109.671480.241 6243877.64364790.186 69378106.834790.290 0737875.70674400.179 25479106.674400.321 5147975.55981770.175 77287105. 004620.351 4344074.37394620.173 09440105.001770.377 8228774.358101280.161 16462102.171280. 399 6546272.367Erdosl合作者网络中最具影响力节点为10(ALON,NOGA M. )、44(BOLLOBAS，BELA)和 165(GRAHAM, RONALD LEWIS)等。 59 万方数据竞赛论坛基于Erdosl合著网络和论文引用网络的复杂网络节点特征研究2014年6月3.3网络科学原创性论文彩响力排序结果对于26篇论文的有向引用网络，以公式(2)中的论文发表期刊影响因子标准化向量JFsund为迭代初值， 取阻尼系数9= 0. 85,迭代阈值为a = 0.000 01，利用修改的PageRank算法得到26篇论文权威性排名 (表5)。表5 26篇论文权威性排名表排名权威指数论文编号排名权威指数论文编号10. 401 04014140. 013 978720. 103 5804150.011 5261730. 082 6418160. 006 9642440. 063 41719170. 004 6671850.061 98023180.002 9461160.049 88822190.002 270370.049 7651200.001 2702580. 047 74310210.001 233690. 027 8572220. 000 30916100. 017 44626230. 000 2035110.016 7219240. 000 18721120. 016 28120250. 000 05812130. 015 97413260. 000 05815在权威性指数排名中，权威指数最高的论文为编号14的论文和编号4的论文，这2篇论文被认为是“复 杂网络研究新纪元开始的标志”1。在本文算法中，编号14和4的论文排名靠前得益于以下3个方面： 2篇论文所在期刊的高影响因子。两篇论文分别发表在Nature和Science上； 2篇论文的髙引用率。他引分别12次，11次，其余24篇论文他引最高的为8次(26篇论文内部）； 论文自身因为开创性工作较少地引用了（26篇论文中）其他论文。论文4只引用了论文14,而论文14 并没有引用其他论文(26篇论文中），当然这也是论文14排名比论文4靠前的原因之一。根据论文年均引用量给出了论文的人气指数(表6)。表6 26篇论文人气指数排名表排名人气指数论文编号排名人气指数论文编号11 417.20141492.21821 319.7041586.44131 142.3021676.85341 003. 60111771.50135678.34251871. 10216396.92221958.2167227. 25262040.6358224.00102135.83209183. 23172229.441610176.28192319.672311151.10182417. 942412121.8592515.001513105.5712260. 577在人气指数排名中，权威指数最髙的论文仍然为编号14的论文和编号4的论文，进一步认定了这2篇 60 论文“复杂网络研究新纪元开始的标志”的地位。注意到并不是所有论文的权威指数和人气指数排序都是那么明显，根据权威-人气模型建立了权威-人 气坐标系（图4)。高权威低人气23i7I:高权威高人气143如：:24低权威低人气2命1518425，低权威高人气:1210 10。 10 10J 109 104人气指数的自然对数101010图4权威人气指数图图4显示:编号14,4的论文拥有高权威和高人气，这得益于2篇论文超髙的引用率、几乎最高的发表 期刊影响因子和原创性的工作;编号15的低权威和低人气是因为较低的引用率，引用了较多的其他论文， 发表期刊影响因子较低;编号7的论文虽然具有一定的权威性，但是人气却很低，人气低是因为它超低的 引用率，权威性高是因为没有引用其他论文以及发表期刊影响因子较高;几乎没有明显低权威高人气的论 文，这也和经验相符，低权威论文一般发表在低影响因子期刊，较少受人关注，从而总引用量较少;大部分 论文集中在权威-人气指数图的中部，表现中庸。4讨论4.1 Erdosl合作者网络节点重要性与显著彩响力联系与区别由第三部分结果可知，大部分节点的重要性和影响力差距不大，两者排名差大于100的仅为45个节点， 重要的节点影响力也较大，影响力较大的节点重要性排名也非常靠前。但是还是有一些节点重要性与影响 力（以TOPSIS算法为例)有一些差别。重要性远远高于影响力的节点排名差超过220的共4人（表7)，均为Erdos早期的合作者，且都已 经去世。表7重要性远远离于影响力的节点表合作者编号合作者姓名重要性排名影响力排名与Erdos首次合作时间合作人数(Erdos除外）147FUCHS,W. H. JOHANNES*83311195627352PIRANI AN, GEORGE*187418194726354POLLARD,HARRY STRANGE*104357194618423SHIELDS, ALLEN LOWELL*72310196743影响力远远髙于重要性的节点是编号为483的合作者VALTR，PAVEL,重要性排名250,影响力排名 121，排名差为129,首次与Erdos合作时间为1996年，是Erdos晚期的合作者之一，仅与Erdosl网络其他作 61 者3人合作过。模型显示，Erdos早期的合作者往往在网络中重要性高于影响力，这是因为早期的合作者已经具有自己 健全的合作网络，与他人合作较多(Erdos除外）；而Erdos晚期的合作者往往在网络中影响力高于重要性， 这是因为晚期的合作者还不具有自己健全的合作网络，与他人合作较少(Erdos除外）。4.2网络科学原创性论文彩响力分析与修改的PageRank算法在网络科学原创性论文影响力中使用了权威-人气模型，虽然论文的权威和人气关系不好度量，但是图 4显示它们并不是独立的。从图4的分析不难看出，一篇论文的权威是基础，发表在影响因子较髙的期刊上 的论文权威性往往很高，受关注程度也大于发表在影响因子较低的期刊上的论文。关注程度决定引用量，从 而提高了论文的人气。本文在网络科学原创性论文影响力计算时采用了修改的PageRank算法，增加了阻尼系数、出度为0节 点的自连接、改变算法初值。算法显示了较强的适应能力，很好地度量了网络科学原创性论文影响力。该算 法可推广到其他应用，如犯罪团伙嫌疑排名等4.3网络的增长性与优先连接性虽然Erdosl网络呈现小世界网络的特征，但是也具有无标度网络的增长性和优先连接性。Erdosl网 络增长性体现在合作者的数量(节点）和合作联系（边）的增加，优先连接性体现在合作者倾向于与重要性较 高或者影响力较大的合作者合作。这提示我们在加入某一个专业领域时，挑选重要程度较高或者影响力较 大的合作者，能够快速进入到该领域的核心区域。参考文献1 汪小帆，李翔，陈关荣.复杂网络理论及其应用M.北京：清华大学出版社有限公司，2006.2 Gardner T S, Cantor C R, Collins J J. Construction of a genetic toggle switch in Escherichia coliJ. Nature，2000403 6767):339-342.3 Buchler N E,Gerland U, Hwa T. On schemes of combinatorial transcription logicJ. Proceedings of the National Academy of Sciences,2003,100(9) ：5136-5141.4 Noireaux ViBar-Ziv R，Libchaber A. Principles of cell-free genetic circuit assemblyJ, Proceedings of the National Academy of Sciences,2003,100(22)：12672-12677.5 Cardillo AScellato SLatora V，et al. Structural properties of planar graphs of urban street patternsJ. Physical Review E, 2006,73(6):066107.6 孙林夫.面向网络化制造的协同设计技术J.计算机集成制造系统，2005,11(1):1-6.7 Boginski V，Butenko S, Pardalos P M. On structural properties of the market graph J. Innovations in Financial and Economic Networks 2003： 29-45.8 Callaway D S, Newman M E J, Strogatz S H,et al. Network robustness and fragility： Percolation on random graphs J. Physical Review Letters,2000,85(25)：5468-5471r9 Sabidussi G, The centrality index of a graphQ. Psychometrikaj 2966#31(4) ：582-603,ClOFreeman L C. A set of measures of centrality based on betweennessJ- Sociometry ,1977,40(1) ；35-41.11 Brandes U. A faster algorithm for betweenness centrality* J, Journal of Mathematical Sociology,2001,25(2) *163-177.12 叶春森，汪传雷，刘宏伟.网络节点重要度评价方法研究J.统计与决策，2010(1):22-24,13 Oakland University. Erdosl, Version 2010, October 20,2010EB/OL. 2014-05-08. https：/files. Oakland, edu/users/ grossman/enp/Erdosl. html.14 Newman M E J，Assortative mixing in networksJ, Physical Review Letters,2002,89(20) *2087011-2087014.15 百度百科.詹姆斯布坎南EB/OL. 2014-05-08, https/baike. baidu, com/subview/147399/10774906. htm.16 百度百科.安德鲁杰克逊EB/QL. 2014-05-08. /view/146935.htm.17 Hwang C L, Yoon K S. Multiple attribute decision making: method and applications, a state-of-the-art surveyM. New York ： Springer-Verlag, 1981. 62 万方数据第3卷第2期数学建模及其应用Vol.3 No.2 Jun.2014The Research about Properties of Complex Networks，Nodes Based on ErdoslCo-author Network and Paper Citation NetworkWANG Xinzeng1，2，YAN B