局部拓扑信息耦合促进网络演化

刘树新季新生②刘彩霞汤红波巩小锐



局部拓扑信息耦合促进网络演化

刘树新*①季新生①②刘彩霞①汤红波①巩小锐①

①(国家数字交换系统工程技术研究中心 郑州 450002)②(移动互联网安全技术国家工程实验室 北京 100876)

为了研究局部拓扑信息耦合对网络演化的促进作用，该文提出一种局部拓扑加权方法，用于表征节点间联系的紧密性及拓扑信息的耦合程度，并从演化模型的宏观统计和实际网络数据测试两方面验证了局部拓扑信息耦合促进网络演化的有效性。首先将该加权方法应用于BA模型，提出TwBA模型及局域世界模型TwLW。仿真实验表明，TwBA的度分布随连边数目的增多，迅速从指数分布转变为幂律分布，验证了现实网络加速增长产生幂律分布的现象，并基于此提出一种加速演化的TwBA模型，其在不同的加速率下呈现出幂律分布；而TwLW则展现了从广延指数分布到幂律分布变化的形式。然后将加权方法拓展到链路预测方法，提出3个加权相似性指标。实际网络数据测试表明，该方法能够大幅度地提高基本算法的预测精度，部分甚至高于全局性指标。

复杂网络；局部拓扑；演化模型；链路预测；信息耦合

1 引言

近年来，复杂网络领域的研究蓬勃发展，越来越多的现实网络已经成为复杂网络的研究对象，包括社交媒体网络[1]、互联网[2]、电力网络[3]、蛋白质网络[4]、交通运输网络[5]等多种复杂性系统。网络演化机制作为网络科学的根本性问题，一直是统计领域的研究热点。尤其是在小世界[6]、无标度[7]等特性的发现之后，极大地丰富了人们对于现实网络的认识，也刺激了各领域研究复杂网络演化机制的热忱[8]。

经典的BA模型揭示了网络的无标度特性，认为网络增长和偏好连接是网络演化的根本动力[7]。在BA模型的基础上，许多学者在连接概率和内部连边等上做了改进[9,10]。考虑到现实网络中个体选择的局限性，文献[11]提出了局域世界演化模型(LW)，模型通过在随机选择的局域世界中进行度优先选择，并呈现出指数分布和幂律分布之间的度分布形式。由于许多真实网络的连接存在权值，文献[12]提出了经典的赋权演化模型BBV模型，该模型采用强度优先连接，新连接添加时会为当前点强度增加一个，产生了标准的无标度网络。基于BBV模型，许多学者进一步提出了不同的含权演化模型，但在权值的赋予上多是在无权网络模型上进行简单的增添，缺乏对局部拓扑信息的耦合，且其取值并不能反映当前连接周围的拓扑结构。

现阶段，网络演化模型的研究均基于宏观统计(度分布等宏观参数)，并没有在实际网络中进行数据验证。因此，相关学者认为链路预测可用于衡量网络演化模型[16]，验证物理演化机制在实际网络中的有效性。并基于拓扑演化机制，提出了大量的链路预测方法，包括共同邻居[17](Common Neighbors, CN), Salton[18]，资源分配[19](Resource Allocation, RA), LHN-II[20]和Katz[21]等相似性指标，一定程度上丰富了人们对真实网络中网络演化机制的认识。研究表明许多实际网络的度分布介于幂律分布和指数分布之间[22]，呈现出近幂律的分布形式如去头的幂律分布、广延指数分布等[23]，且增长过程中表现出了加速增长的趋势(边的增长速度远大于点的增加速度)[24]。具体实际网络中如：政治论坛博客网络[25]为近幂律分布；线虫神经网络[6]则存在单峰[26]，呈现单侧幂律分布；引文网络[27]则为近指数分布；而路由器级互联网[28]则表现为接近广延指数分布的近幂律分布。度优先选择被认为是幂律分布产生的重要机制，但越来越多实证研究发现局部范围内的拓扑信息对新连接的建立也起着重要作用[29,30]。局部拓扑信息耦合程度能够很大程度上影响网络节点的偏好连接，现实网络如人际关系网络中，个体之间新连接的建立往往倾向于个体及其周围社会关系的统合考量，新连接则可以理解为两个节点周围社会关系的偏好选择；同样，在引文网络中，新引用的产生更多是基于文献相互引用构成的影响力(局部拓扑关系构成的综合吸引力)。

基于上述讨论，本文提出了一种局部拓扑信息加权方法，量化节点间联系的紧密性和拓扑信息的耦合程度，进而使节点可以耦合更多的局部拓扑信息。将该方法应用于经典BA模型，基于拓扑加权后的节点强度进行优先选择，提出了基于局部拓扑加权的TwBA和局域世界模型TwLW。度分布分析表明，不同于BA模型，TwBA呈现出从指数分布到幂律分布变化的形式，并随着连边数的增长，迅速转变为幂律分布，这一定程度上说明了现实网络连边加速增长后产生幂律分布的现象；基于TwBA的度分布特点，进一步提出加速网络模型A-TwBA，度分布统计显示模型在网络加速演化后呈现出幂律分布，部分同时呈现单峰和幂律分布；而TwLW模型则呈现了广延指数分布到幂律分布变化的形式。为了在实际网络中进一步验证局部拓扑加权促进网络演化这一机制的有效性，将拓扑加权应用于基本的链路预测方法CN, Jaccard和RA。多个实际网络数据测试结果表明，局部拓扑加权能够大幅度提高相似性指标的预测精度，部分甚至高于全局性指标。从宏观统计和实际网络数据两个方面验证了局部拓扑信息耦合促进网络演化这一机制的合理性。

2 局部拓扑信息加权方法(TW)

现实网络中，权重一般是根据统计结果进行赋值，比如：节点间交互的频率、作用强度[31]，但并没有进一步反映连接周围的拓扑结构关系。越来越多实际网络数据表明，网络局部范围内的积聚程度对连边的可能性起着重要作用[32,33]。节点周围拓扑集聚程度越高，对其他节点的吸引力越大，它们之间便更倾向于建立连接。对于网络中直接连接的两个节点和，其间接连接可以为当前边提供隐含的拓扑信息和潜在内部联系，增加了节点间的相关联系和信息耦合，一定程度上反映了节点间联系的紧密程度。图1示意了不同情形下的拓扑影响，可分为两种对比情况：一种情形为两个端点拥有相同的连边数目，但间接连接数目不同如：图1(a)和图1(b)，由于图1(b)中含有间接连接多于图1(a)，所以认为图1(b)中节点和间的局部拓扑紧密性更高，故连边权重大于图1(a)；另一种情形为间接连接数目相同，但总连边数目不同：图1(b)和图1(c)，由于图1(c)中连边数目小于图1(b)，虽然间接连接数目相同，局部拓扑紧密性也与其占比例相关，图1(c)中节点和间拓扑关联更紧密，故权重相对更大。

图1 不同局部拓扑情形对比图

基于上述分析，假定每条边可以拥有或支配的资源为1。从间接连接对节点间紧密性的影响上分析，若两节点所有连接的数目为，间接联系数目为，间接联系对当前连接的影响，可以量化表示为，而当前直接连边自身在所有连接中的比重为，如图1(c)中的量化结果分别为4/7和1/7。总之，对于网络中两个节点和，其局部拓扑信息的影响总体加权表示为

3 基于局部拓扑信息加权的网络演化模型

3.1 基于局部拓扑信息加权的网络演化模型

基于局部拓扑加权方法(TW)，对BA模型进行加权拓展，提出TwBA模型和局域世界模型TwLW(局部拓扑加权可以拓展到任何无权网络模型，在此以经典的BA模型为例，说明局部拓扑对拓扑演化的促进作用)。TwBA演化步骤为：

(2)赋权：根据式(1)对初始网络的已有边进行赋权；

(4)权值更新：根据式(1)对变化和新加入的边重新赋权；

(5)返回步骤(3)，直至网络达到指定大小。

TwBA模型说明了新连接的偏好连接不仅仅和其节点度有关，也与其周围拓扑结构相关。同理，在加入局域世界后，把TwBA模型拓展为TwLW模型，其具体演化步骤则表示为：

(2)赋权：根据式(1)对初始网络的已有边进行赋权；

(5)权值更新：根据式(1)对变化和新加入的边重新赋权；

(6)返回步骤(3)，直至网络达到指定大小。

同样，当TwLW中局域世界为整个网络时，TwLW则转变为TwBA模型。TwLW模型中，新节点难以获取整个网络的信息[34]，其建立连接是在一定的社交圈内根据已有节点及其社会关系进行优先选择。

3.2度分布分析

不同于BA模型的标准幂律分布，经过局部拓扑加权后，TwBA呈现了从指数分布到幂律分布变化的度分布形式。图2显示了相同初始网络下BA模型和TwBA模型的度分布对比。BA模型随着连边数的增加始终保持幂律分布，而对于TwBA模型，当值较小时，呈现近指数分布(一些朋友关系网[35]、蛋白质[36]等实际网络的度分布形式)；随着值的增大，TwBA的度分布迅速转变为幂律形式，且插图互余累积度分布曲线中均展现出了指数截断现象[22]。实证研究表明，大多数网络的度分布为近幂律分布且存在加速增长的现象[24]，TwBA随着的增大，迅速趋向于幂律分布，也说明了现实网络的加速演化、平均连接的迅速增多，也是促进网络形成幂律分布的一个内部驱动。TwBA利用局部拓扑信息对BA模型进行了拓展，使其更多地符合了实际网络的演化过程和度分布形式，说明了局部拓扑信息耦合对网络演化的促进作用。

图2 度分布对比 (，插图为互余累积度分布曲线)

由于大量实际网络如万维网、合作网络、蛋白质和引文网络在演化过程中均存在连边数目加速增长的现象[24]。在TwBA的基础上，令，提出一种加速演化模型A-TwBA，其中为初始连边数目(),为加速演化速率()。在不同参数下，加速演化模型的度分布情形如图3所示。多数情形下模型均为幂律分布，部分情形下，甚至同时出现了单峰[26]和幂律分布，这与一类实际网络如线虫神经网络(CE)等网络的度分布较为契合[6]。当初始连边数为0,时(图3(a))，最大连边数，此时连边数目变化较小(从1到3)，模型呈现轻微的指数分布倾向，而随着初始的增大(图3(c)、图3(d))，其度分布均展现为幂律分布，但无论加速演化速率多小，只要网络规模足够大，模型均能演化为幂律分布的形式。图3中所有不同初始连边数目下均显示了模型在演化速率越大时，其幂律指数越大，度分布越陡峭，说明了网络加速增长的速率越快，其度分布下降速度越快，无标度程度越明显。A-TwBA一定程度上反映了网络在加速演化中度分布的无标度特征。

图3 A-TwBA模型的度分布

TwLW模型是在TwBA基础上添加了局域世界。图4显示了不同的局域世界规模和连边数目下的互余累积度分布情况(=10000)。图4(a)中随着局域世界规模的增大，LW模型的度分布由近幂律分布到广延指数分布的变化过程。当局域世界为整个网络大小时，此时为TwBA模型，则依连边数目从指数分布变化为幂律分布。图4(b)中显示了时，不同连边数目下度分布情形，此时总体呈现出近幂律分布(广延指数分布)的形式，并随着连边数目的增加，幂律指数逐渐增大。广延指数分布普遍存在于一些合作网络系统中如淮阳菜肴系统、旅游交通线路系统、以及好莱坞演员网[23]。从上述TwBA, A-TwBA和TwLW的度分布统计结果中，局部拓扑加权使模型进一步符合了实际网络情形，从宏观数据统计上验证了实际网络中局部拓扑耦合能够促进网络演化这一演化机制。

图4 TwLW的度分布 (，插图为互余累积度分布曲线)

4 基于局部拓扑信息加权的链路预测方法及实证分析

4.1基于局部拓扑信息加权的链路预测方法

通过局部拓扑加权对网络所有节点间的联系加权后，基于基本无权网络预测指标，分别把3个链路预测方法拓展为含权的预测方法[31]，包括CN, Salton和RA等相似性指标(局部拓扑加权可以拓展到多种相似性预测指标，在此以CN等指标为例，说明局部拓扑促进演化这一机制在实际网络中的有效性)，其中CN指标可以拓展为TwCN，具体相似度表示为

(3)

4.2 衡量指标及网络数据

评价链路预测算法精确程度的指标为AUC。AUC可以简单地理解为在测试集中随机选择一条边的分数值大于未连接边的分数值高的概率[16]。若测试集中边大于未连接边的分数()，则加1分，若两者相等()，则加0.5分，表示为

为了更好地体现在现实网络中局域信息加权对相似性指标的优化作用，选择了7个不同类型的实际网络数据进行测试包括：(1)Politicalblogs (PB)[25]：美国某政治论坛的博客首页之间通过超链接构成的网络；(2) Hamster[35]: 在hamsterster.com网页上的用户朋友关系网络；(3)Yeast[36]：蛋白质相互作用网络，节点表示蛋白质，边为相互作用关系；(4) Caenorhabditis Elegans (CE)[6]：线虫神经网络，节点代表线虫的神经元，边为神经元突触(synapse)或间隙连接(gap junction)；(5)Power[6]：美国西部电力网络，节点表示变电站或换流站，连边为高压线；(6)Kohonen[27]：有关自组织映射主题或Kohonen T的论文引用网络；(7)Router[28]：路由器层次的Internet。上述网络具体的特征参数如表1所示，包含节点数目()，边的数目()，平均度，集聚系数()[6]和匹配系数[37]。在试验测试中，设置集合中边数占比为0.9，则为0.1，测试结果均为100次结果的均值。

表1 网络数据特征参数

4.3实证分析

为了在实际网络中验证局部拓扑信息耦合促进网络演化的有效性，分别对比了局部拓扑加权和非加权的链路预测指标在实际网络中的预测准确度，其中相似性指标包括CN, Salton和RA。

表2的数据对比可以看出，拓扑加权后的预测精度均高于未加权的预测指标，这一定程度上验证了局部拓扑加权在实际网络中的有效性。在Router等稀疏网络中，AUC的增大是显著的，尤其是TwRA可以把RA指标的AUC从0.65提高到0.96。相比全局性指标Katz()，LHN-II()，大多数情况下TwCN等含权指标的预测精度高于LHN-II，部分高于Katz，但从CN拓展到TwCN等并没有在时间复杂度上有量级的变化(Tw的复杂度与CN同一个量级)。由于全局性算法复杂度较高，在大规模网络中使用便受到一定的限制。同时，局部指标可以应用于大规模实际网络，但预测精度不足。通过局部拓扑加权后，既能使局部预测指标的预测精度接近全局性指标，又能够使其应用于大规模网络，具有重要的实际应用价值。实际含权网络的预测中，相似性指标预测并没有表现出很好的结果，权值高的边起的作用反而难以界定，甚至出现了“弱连接”(weak tie)效应[31]，而局部拓扑加权则有效促进了相似性指标的预测精度。综上所述，在不改变当前相似性指标时间复杂度量级的基础上，局部拓扑加权能够有效提高相似性指标的预测精度，其中部分甚至高于全局性指标，验证了实际网络中局部拓扑信息耦合促进网络演化这一机制的有效性。

表2 局部拓扑加权和非加权的相似性指标AUC结果对比

5 结论

许多网络演化模型认为度优先选择是幂律分布产生的重要机制。然而，越来越多的研究表明，新连接的选择更多的是基于节点及其周围拓扑关系的优先选择。基于局部拓扑信息耦合对网络网络演化的促进作用，本文提出了一种局部拓扑加权方法，将其应用于拓扑演化模型，分别拓展为TwBA, A-TwBA和TwLW模型，产生了从指数分布到幂律分布，部分出现单峰和广延指数分布形式，宏观统计上实证了模型的有效性；然后，将其应用与链路预测，分别拓展了CN, Salton和RA相似性指标(加权方法可以应用于任何相似性指标)。实际网络数据测试表明，拓展后的相似性指标的预测效果较好，这一定程度上验证了在实际网络中局部拓扑加权确实能够揭示实际网络连边机理。由于演化模型的研究一直基于宏观统计，没有统一的衡量标准，很多学者认为链路预测可以对演化模型进行评价，也普遍认同每一种演化模型就对应一个预测方法。本文从局部拓扑耦合促进网络演化这一机制出发，分别将局部拓扑加权应用于经典的网络演化模型和链路预测，从宏观统计和实际网络数据两个方面验证了演化机制的合理性，也说明了复杂网络演化模型和链路预测在同一演化机制上的统一。

[1] BIAN Jiang, XIE Mengjun, TOPALOGLU U,. Social network analysis of biomedical research collaboration networks in a CTSA institution[J]., 2014, 52(1): 130-140.doi:10.1016/j.jbi. 2014.01.015.

[2] WANG Shengjun, WANG Zhen, JIN Tao,. Emergence of disassortative mixing from pruning nodes in growing scale-free networks[J]., 2014, 4(7): 7536-7541. doi:10.1038/srep07536.

[3] ZHANG Yudong, BAO Zhejing, CAO Yijia,. Long-term effect of different topology evolutions on blackouts in power grid[J].&, 2014, 62(4): 718-726.doi:10.1016/j.ijepes.2014. 04.056.

[4] TESCHENDORFF A E, BANERJI C R S, SEVERINI S,. Increased signaling entropy in cancer requires the scale-free property of protein interaction networks[J]., 2015, 5(9), article number: 9646.doi: 10.1038/srep09646.

[5] SUN Li, LIU Like, XU Zhongzhi,. Locating inefficient links in a large-scale transportation network[J].:, 2015, 419(2): 537-545.doi:10.1016/j.physa.2014.10.066.

[6] WATTS D J and STROGATZ S H. Collective dynamics of ‘small-world’ networks[J]., 1998, 393(6684): 440-442.doi: 10.1038/30918.

[7] BARABÁSI A L and ALBERT R. Emergence of scaling in random networks[J]., 1999, 286(5439): 509-512.doi: 10.1126/science.286.5439.509.

[8] 方锦清, 汪小帆, 郑志刚, 等. 一门崭新的交叉科学:网络科学(上)[J]. 物理学进展,2007, 27(3): 239-343.

FANG Jinqing, WANG Xiaofan, ZHENG Zhigang,. New interdisciplinary science: network science (1)[J]., 2007, 27(3): 239-343.

[9] ALBERT R and BARABÁSI A L. Topology of evolving networks: local events and universality[J]., 2000, 85(24): 5234-5237. doi:10.1103/PhysRevLett. 85.5234

[10] BIANCONI G and BARABÁSI A L. Bose-einstein condensation in complex networks[J]., 2001, 86(24): 5632-5635. doi: 10.1103/PhysRevLett.86.5632.

[11] LI Xiang and CHEN Guanrong. A local-world evolving network model[J]., 2003, 328(1): 274-286.doi: 10.1016/S0378- 4371(03)00604-6.

[12] BARRAT A, BARTHÉLEMY M, and VESPIGNANI A. Weighted evolving networks: coupling topology and weight dynamics[J].2004, 92(22): 228701-228706. doi: 10.1103/PhysRevLett.92.228701.

[13] YANG Chunxia, TANG Minxuan, TANG Haiqiang,. Local-world and cluster-growing weighted networks with controllable clustering[J]., 2014, 25(5): 1440009-1440021.doi: 10.1142/S0129183114400099.

[14] DAI Meifeng and ZHANG Danping. Weighted evolving network with aging-node-deleting and local rearrangements of weights[J]., 2014, 25(2): 1350093-1350102. doi:10.1142/S0129183 113500939.

[15] 王丹, 金小峥. 可调聚类系数加权无标度网络建模及其拥塞问题研究[J]. 物理学报, 61(22): 228901-228910.

WANG Dan and JIN XiaoZheng. On weightd scale-free network model with tunable clustering and congesstion[J]., 2012, 61(22): 228901-228910.

[16] LÜ Linyuan and ZHOU Tao. Link prediction in complex networks: a survey[J].:, 2011, 390(6): 1150-1170.doi:10.1016/ j.physa.2010.11.027.

[17] LORRAIN F and WHITE H C. Structural equivalence of individuals in social networks[J].1971, 1(1): 49-80.doi: 10.1080/ 0022250X.1971.9989788.

[18] SALTON G and MCGILL M J. Introduction to Modern Information Retrieval[M]. New York: McGraw-Hill, 1983: 30-31.

[19] ZHOU Tao, LÜ Linyuan, and ZHANG Yicheng. Predicting missing links via local information[J].2009, 71(4): 623-630.doi:10.1140/epjb/ e2009-00335-8.

[20] LEICHT E A, HOLME P, and NEWMAN M E J. Vertex similarity in networks[J]., 2006, 73(2): 026120-0261125.doi: 10.1103/PhysRevE.73.026120.

[21] KATZ L and POWELL J H. A proposed index of the conformity of one sociometric measurement to another[J]., 1953, 18(3): 249-256. doi:10.1007/ BF02289063.

[22] 汪小帆, 李翔, 陈关荣. 复杂网络理论及其应用[M]. 北京：清华大学出版社, 2006: 35-85.

WANG Xiaofan, LI Xiang, and CHEN Guanrong. Complex Networks Theory and Its Applications[M]. Beijing: Tsinghua University Press, 2006: 35-85.

[23] ROBERTS J A, IYER K K, FINNIGAN S,. Scale-free bursting in human cortex following hypoxia at birth[J]., 2014, 34(19): 6557-6572.

[24] ZHANG Zhongzhi, FANG Lujun, ZHOU Shuigeng,. Effects of accelerating growth on the evolution of weighted complex networks[J].:2009, 388(2): 225-232. doi: 10.1016/j. physa.2008.10.008.

[25] ADAMIC L A and GLANCE N. The Political blogosphere and the 2004 US election: divided they blog[C]. Proceedings of the 3rd ACM International Workshop on Link Discovery,New York, NY, USA, 2005: 36-43.doi: 10.1145/1134271. 1134277.

[26] WANG Qing and GUO Jinli. Human dynamics scaling characteristics for aerial inbound logistics operation[J].:, 2010, 389(10): 2127-2133.doi:10.1016/j.physa.2010.01.009.

[27] TAN Fei, XIA Yongxiang, and ZHU Boyao. Link prediction in complex networks: a mutual information perspective[J]., 2014, 9(9): e107056-e107061. doi: 10.1371/ journal.pone.0107056.

[28] SPRING N, MAHAJAN R, and WETHERALL D. Measuring ISP topologies with rocketfuel[J]., 2002, 32(4): 133-145. doi:10.1145/964725.633039.

[29] 崔爱香, 傅彦, 尚明生, 等. 复杂网络局部结构的涌现: 共同邻居驱动网络演化[J]. 物理学报, 2011, 60(3): 803-808.

CUI Aixiang, FU Yan, SHANG Mingsheng,. Emergence of local structures in complex network: common neighborhood drives the network evolution[J]., 2011, 60(3): 803-808.

[30] 刘树新, 季新生, 刘彩霞, 等. 一种信息传播促进网络增长的网络演化模型[J]. 物理学报, 2014, 63(15): 158902.

LIU Shuxin, JI Xinsheng, LIU Caixia,. A complex network evolution model for network growth promoted by information transmission[J].2014, 63(15): 158902.

[31] LÜ Linyuan and ZHOU Tao. Link prediction in weighted networks: The role of weak ties[J]., 2010, 89(1): 18001-18006. doi:10.1209/0295-5075/89/18001.

[32] XIE Zhou, LI Xiang, and WANG Xiaofan. A new community-based evolving network model[J]., 2007, 384(2): 725-732.doi:10.1016/j.physa.2007.05.031.

[33] LI Fenhua, HE Jing, HUANG Guangyan,. A clustering-based link prediction method in social networks[J]., 2014, 29(5): 432-442.doi: 10.1016/j.procs.2014.05.039.

[34] YANF Guangyong and LIU Jianguo. A local-world evolving hypernetwork model[J]., 2014, 23(1): 018901-018909. doi:10.1088/1674-1056/23/1/018901.

[35] LÜ Linyuan, PAN Liming, ZHOU Tao,. Toward link predictability of complex networks[J]., 2015, 112(8): 2325-2330.

[36] VON MERING C, KRAUSE R, SNEL B,. Comparative assessment of large-scale data sets of protein-protein interactions[J]., 2002, 417(6887): 399-403.doi: 10.1038/nature750.

[37] SENDIÑA-NADAL I, LEYVA I, NAVAS A,Effects of degree correlations on the explosive synchronization of scale-free networks[J]., 2015, 91(3): 032811-032819.doi: 10.1103/PhysRevE.91.032811.

Information Coupling of Local Topology Promoting the Network Evolution

LIU Shuxin①JI Xinsheng①②LIU Caixia①TANG Hongbo①GONG Xiaorui①

①(National Digital Switching System Engineering and Technological R&D Center, Zhengzhou 450002, China)②(National Engineering Laboratory for Mobile Network Security, Beijing 100876, China)

To study the effects of information coupling of local topology on the complex network evolution, a new weighted method is proposed based on local topology information, which can measure the closeness of connection and the coupling degree of topology information between nodes. In this paper, to demonstrate the efficiency of the information coupling of local topology, an empirical research is made on characteristic statistics of evolving model and real network data testing of link prediction respectively. Firstly, the weighted method is applied to BA model; TwBA and the local world model TwLW are proposed based on the topology weighted method. Simulation experiments show that the degree distribution of TwBA can be rapidly changed from exponential distribution to power law distribution with the increasing of the connection numbers for new added nodes, which confirmes that the phenomenon of accelerating growth appears widely in the evolution of many real scale-free networks. Then, based on TwBA model, an accelerating growth model A-TwBA is proposed, and the A-TwBA model presents power law distribution for different accelerating growth rates. The degree distribution of TwLW is changed from stretched exponential distribution to power law distribution for different sizes of local world. Finally, the proposed weighted method is applied to link prediction methods (including CN, Salton and RA index), and three weighted indices are proposed. Empirical study shows that the weighted proposed method can significantly improve the prediction accuracy of these basic indices, and some of them are higher than those of the global indices.

Complex network; Local topology; Evolving model; Link prediction; Information coupling

N94; TP3; TP391

A

1009-5896(2016)09-2180-08

10.11999/JEIT151338

2015-11-26；

2016-04-07；

2016-05-25

国家自然科学基金创新研究群体项目(61521003)，国家高技术研究发展计划(2014AA01A701)

The Foundation for Innovative Research Groups of the National Natural Science Foundation of China (61521003), The National High Technology Research and Development Program of China (2014AA01A701)

刘树新 liushuxin11@126.com

刘树新： 男，1987年生，博士，研究方向为复杂网络、链路预测、移动网络安全.

季新生： 男，1968年生，教授，博士生导师，研究方向为移动网络安全、移动通信技术、无线网络防护.

刘彩霞： 女，1974年生，副教授，硕士生导师，研究方向为网络安全、社会网络、下一代移动网络.

汤红波： 男，1968年生，教授，硕士生导师，研究方向为移动网络安全、下一代移动网络.

巩小锐： 男，1991年生，博士，研究方向为新型网络体系结构、社会网络.