一种基于局部社团和全局信息的链路预测算法

杨旭华，凌 非

(浙江工业大学 计算机科学与技术学院，浙江 杭州 310023)

一种基于局部社团和全局信息的链路预测算法

杨旭华，凌 非

(浙江工业大学 计算机科学与技术学院，浙江 杭州 310023)

以往复杂网络的链路预测研究常常只考虑了公共邻居等局部网络的拓扑信息，不能很好的反映网络整体上的情况.在考虑局部社团网络拓扑信息的基础上，将同配系数等全局信息也引入预测算法中，提出了一种基于局部社团和全局信息的LCII预测算法.应用该算法对多个真实网络进行了链路预测，发现与其他几种经典链路预测算法相比，LCII预测算法有较好的预测效果和准确度.可见，综合考虑局部社团和全局信息可以挖掘出候选节点间更多的信息，从而能在一定程度上提升预测的命中率.

复杂网络；链路预测；局部社团；全局信息

网络科学已成为现阶段研究领域的热门学科，网络科学的基本观点是从拓扑结构入手，用网络来描述系统[1].利用这种方法，把系统中的个体看成节点，个体间的相互作用看成连接节点的边，我们就得到了一个描述系统内部关联的网络[2].利用网络，我们可以研究对应系统的某些静态或动态的拓扑特性[3]，并帮助我们能更有效地预测[4]甚至控制复杂系统[5].而链路预测是网络科学的一个重要分支，它是通过已知的各种信息预测网络中尚不存在连边的两个节点在网络进化过程中产生连边的可能性[6].其中，单一拓扑结构中拥有多个局部社团的网络是广大科研工作者研究的重点[7]，而这种网络被称为局部社团范式(Local community paradigm, LCP).LCP网络[8]主要是由节点间的弱相互作用形成的，并同时刻画了以自组织为适应策略的动态系统.考虑到LCP网络的普遍存在，研究针对LCP网络的链路预测算法也是很有必要的.

目前，已经有许多基于局部网络拓扑信息的链路预测方法被提出来了，其中公共邻居(Common neighbors)算法[9]描述的是，两个节点的共同邻居数量越多，这两个节点就越倾向于连接，文中用连接可能性来表征节点间倾向于连接的程度，它是由x节点和y节点的公共邻居节点属性体现.而Cannistraci等提出了一个把关注点从节点转变到连边的新方法，他们认为该方法可用来解决复杂网络中的链路预测问题，并且他们的CAR算法是在公共节点及其公共节点间连边关系的基础上提出的[8].CAR算法表示，如果两个节点的公共邻居节点组成了一个内部有连边的局部社团(Local community, LC)，他们更可能相连，其中，LC的内部连边叫作局部社团连边(Local community links, LCL).他们在一些真实网络的仿真中，得出了CAR算法的效果明显比CN算法要优的结果.那么，在公共节点和公共节点之间连边的基础上，是否可以继续挖掘局部社团网络(Local community network, LCN)中更进一步的关系，比如平均最短路径长度和边聚类系数？是否引入同配系数以及节点度值大小关系就可以更有效的链路预测呢？笔者对此问题进行了研究，结果显示：平均最短路径长度、边聚类系数、同配系数以及节点度值大小关系这些因素能在一定程度上提升链路预测的精度.

1 基于局部社团和全局信息的LCII预测算法描述

LCII算法旨在根据网络中节点之间的连边关系，为尚未产生连边的两个节点预测可能会在未来产生的连边.通过分析节点所在网络的同配系数，考虑两个候选节点的度值，以及局部社团网络中边聚类系数和LCN中的平均最短路径长度，构成LCII算法(图1).

图1 LCII算法预测的过程图示Fig.1 The image of prediction process of LCII

LCII不仅考虑了整个网络的同配系数以及无连边节点对的节点度大小关系，还考虑了LCN中边聚类系数p以及平均最短路径长度对链路预测算法的影响，LCII算法定义为

LCII=CN·LCL·LCC·DU

(1)

其中：CN为候选节点间的共同邻居数；LCL为局部社团网络的连边总数；LCC为局部社团系数；DU为候选节点间度关系的值.为了体现全局信息与局部社团信息的平等，LCII由CN，LCL，LCC和DU以相乘的形式得出，其中LCC综合了边聚类系数和平均最短路径长度，其定义为

(2)

(3)

边聚类系数p表示一个网络中连边聚集程度的系数[10]，其定义为网络中邻居节点间的实际连边数量与网络中所有节点可能存在最大连边数之比.一个网络中的边聚类系数越大，网络中节点越接近，节点间的联系越紧密.在局部社团网络中，边聚类系数p则具体化为式(3).

(4)

(5)

如果两个节点之间的路径长度越小，说明这两个节点更接近，节点间的联系更紧密.对于一个网络，如果平均最短路径长度越小，那么LCN节点越接近，而边聚类系数p如果越大，则LCN越接近，故LCC在综合两者后能准确地反映LCN的聚散程度.如果LCC的值越大，说明网络节点越紧密，反之，越松散.另外，真实网络一般有同配和异配之分，同配是指度值相近的节点倾向于互相连接，异配则相反.而同配系数[12]作为一个表征复杂网络是同配还是异配的重要参数，也体现了网络中节点间度值的整体关系.同配系数可表示为

(6)

其中：M为网络中的总边数；j和k分别为第i条连边的两个节点.同配系数r∈[-1,1].如果r>0，则网络是同配的；如果r<0，则网络是异配的.|r|的大小反映了网络同配或异配的强弱程度.因此，LCII中的DU指标可表示为

(7)

如果整个网络的同配系数r<0，表示网络中的节点更倾向与度大的节点相连，DU指标能表征出两个未连接的节点度相乘得到的值越大，两者越容易在接下来的时间里相连；如果整个网络的同配系数r>0，表示网络中的节点更倾向与度小的节点相连，DU指标也能表征出两个未连接的节点度相乘得到的值越小，两者越容易在接下来的时间里相连.

2 仿真结果与分析

为了检验我们提出的算法，我们在几个现实网络上进行了实验.实验选用的网络分别为：Jazz musicians network[13]，Florida bay trophic exchange food web[14]，American college football[15]和Zachary’s karate club[16]四个网络.Jazz musicians网络中节点是198个Jazz俱乐部成员，连边是成员之间的交往关系；karate club网络中节点是34个空手道俱乐部成员，连边是成员之间交往频繁的朋友关系；football网络中节点是115个美国橄榄球俱乐部成员，连边是成员之间交往的朋友关系；Food网络中节点是128个生态系统中的生物，连边是生物之间的捕食关系.表1展示了这几个不同网络之间的基本数据对比.

表1 不同真实网络的基本数据比较

Table 1 The comparison of basic information using different networks in the simulation

真实网络节点总数/个连边总数/个同配系数Food1282106-0．111730Football1156150．173184Karate3478-0．476098Jazz19854840．020237

由于网络数据的局限性，我们将采用一种断边后再进行连边预测的方式来检验我们的算法.而这个方法在实验仿真中是以如下的方式进行：首先，将特定的网络数据集加载进来，并以此构建网络图；接

着，记录网络图中随机选择的连边列表，并删除这些连边列表中的连边；然后，将对应的链路预测算法(如LCII，CAR和CN算法)应用到已经删除连边的网络图中去，每个算法针对各自预测产生的新连边都有一个相似性分数；最后，将新产生的连边列表降序排列，并与之前删除的连边列表进行对比(每个预测算法都有一个新连边列表)，计算各个预测算法的命中率.

如果删除第一层邻居网络的连边超过50%，整个网络就会出现孤立节点，从而导致局部社团的消失.因此，此处将删除的比例保持在50%以下，取2%～20%，间隔2%，即2%,4%,6%,8%,…,20%.对于每一个网络，都将以同一删除比例重复1 000次仿真，以降低随机性对仿真的影响.

采用Precision[17]来表征删除连边前后网络的接近程度，即链路预测算法的命中率.其表达式为

(8)

其中：Dq为删除前网络图中随机选择的连边列表断边列表；Lq为预测算法新产生的连边列表；Lq为Nq连边总数；q为删除的比例，q=0.02,0.04,…,0.2.

为了证明LCII这个想法的正确性，我们把LCII算法与之前提到过的经典的算法CN进行比较.图2展示了分别对每个网络进行1 000次迭代后达到稳定状态时Precision与删边比例之间的变化图(Precision为纵坐标，删边比例为横坐标).

在图2(a)中，LCII算法的效果明显优于CAR算法，也明显优于经典算法，最后在18%的断边比例开始效果趋于相近；在图2(b)中，LCII算法的效果明显优于CAR算法，而CAR算法略微优于经典算法；在图2(c)中，LCII算法的效果明显优于CAR算法，也明显优于经典算法，三者的增长幅度在18%的断边比例后趋于平缓；在图2(d)中，LCII算法在12%的断边比例之前的效果明显优于CAR算法和经典算法，且LCII算法预测的结果都保持在14%的命中率以上，尽管在12%的断边比例之后呈现了一定的下降趋势.

从以上仿真结果可以看出：LCII算法的效果明显优于CAR和CN算法，LCC和DU可以在加入CAR指标后起到加强预测的作用，因为LCC和DU可以挖掘出候选节点间更多的信息，在一定程度上可以提升预测的命中率.

图2 LCII，CAR和CN指标的仿真结果Fig.2 The image of simulation results among LCII, CAR and CN

3 结 论

传统的链路预测大多仅考虑基于一种公共邻居节点关系的网络.充分挖掘和利用网络中更深层次的局部信息，是提高链路预测算法精度的一个很好的角度，并提出了一种考虑同配性与度值大小和局部社团网络中的平均最短路径长度和边聚类系数的LCII算法.从对几个具有局部社团的真实网络的仿真结果中发现，LCII算法的预测效果明显优于经典的算法，同时与CAR算法相比也有较好的预测效果.然而，LCII算法没有考虑有向网络以及有权网络，用有向网络以及有权网络来描述网络中节点间的关系将是我们下一步的工作方向.

[1] 龙胜春，龙军.一种应用于无线传感器网络的数据压缩方法[J].浙江工业大学学报，2014,42(2):210-213.

[2] 杨旭华，李传告，陈光.基于K-最短路径的交通网络传输性能分析[J].浙江工业大学学报，2014，42(3):249-256.

[3]WANGWQ,ZHANGQM,ZHOUT.Evaluatingnetworkmodels:alikelihoodanalysis[J].Europhysicsletters,2012,98(2):28004.

[4]WUZ,LINY,WANGJ,etal.Linkpredictionwithnodeclusteringcoefficient[J].PhysicaA,2016,452:1-8.

[5]LIUYY,SLOTINEJJ,BARABSIAL.Controllabilityofcomplexnetworks[J].Nature,2011,473(7346):167-173.

[6]KAYAB,POYRAZM.Supervisedlinkpredictioninsymptomnetworkswithevolvingcase[J].Measurement,2014,56:231-238.

[7]WANGX,XUEZ,XIEZ,etal.MiningtheevolutionofnetworksusingLocal-Cross-Communities-Paradigm[J].Europhysicsletters,2014,104(5):58003.

[8]DAMINELLIS,THOMASJM,DURNC,etal.Commonneighboursandthelocal-community-paradigmfortopologicallinkpredictioninbipartitenetworks[J].Newjournalofphysics,2015,17(11):113037.

[9]ZHAOC,WANGWX,LIUYY,etal.Intrinsicdynamicsinduceglobalsymmetryinnetworkcontrollability[J].Scientificreports,2015,5:8422.

[10] 张霓，陈天天，何熊熊.基于数据场和单次划分的聚类算法[J].浙江工业大学学报，2016,44(1):52-57.

[11] RAO C R, SHI X, WU Y. Approximation of the expected value of the harmonic mean and some applications[J]. Proceedings of the national academy of sciences,2014,111(44):15681-15686.

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

[13] GLEISER P M, DANON L. Community structure in jazz[J]. Advances in complex systems,2003,6(4):565-573.

[14] ARENAS A, DANON L, DIAZ-GUILERA A, et al. Community analysis in social networks[J]. European physical journal B,2004,38(2):373-380.

[15] STOUFFER D B, SALES-PARDO M, SIRER M I, et al. Evolutionary conservation of species’ roles in food webs[J]. Science,2012,335(6075):1489-1492.

[16] ZACHARY W W. An information flow model for conflict and fission in small groups[J]. Journal of anthropological research,1977,33:452-473.

[17] FORTUNATO S. Community detection in graphs[J]. Physics reports,2010,486(3):75-174.

A link prediction algorithm based on local community and global information

YANG Xuhua, LING Fei

(College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China)

The common neighbors index is often used in the study of link prediction in the past research. Based on the topological information of local community networks, global information such as co-ordination coefficients is also introduced into the prediction algorithm, but the LCII prediction algorithm is proposed based on local community and global information. Several real networks are employed to simulate the link prediction. It is found that LCII gets better effectiveness of prediction compared with CAR and CN. The results denote that the new contents of LCII index, which consist of local community and global information, can provide more information between candidate nodes. Therefore the LCII index has better link prediction performance.

complex network; link prediction; local community; global information

(责任编辑：刘 岩)

2016-03-25

国家自然科学基金资助项目(61374152)

杨旭华(1974—)，男，浙江余姚人，教授，研究方向为复杂网络和交通网络，E-mail：xhyang@zjut.edu.en.

TP391

A

1006-4303(2017)01-0010-04