基于共同邻居的链路预测新指标

郭婷婷，赵承业

(中国计量学院 理学院， 浙江 杭州 310018)



基于共同邻居的链路预测新指标

郭婷婷，赵承业

(中国计量学院 理学院， 浙江 杭州 310018)

【摘要】提出一个新的链路预测相似性指标——局部社团结构指标(Local Community Structure，LCS).在已知网络局部信息的前提下，LCS指标刻画了网络中任意两个节点的共同邻居节点与这两个节点的聚集关系.在基于真实网络的实验中，我们计算并比较了CN、AA、RA和LCS四个指标在7个不同真实网络中的AUC评价指标，发现在簇系数较大的真实网络中LCS指标的预测结果好于其他三个指标.

【关键词】链路预测；局部相似性；社团结构；AUC评价指标；簇系数

网络中的链路预测是指如何通过已知的网络节点以及网络结构等信息，预测网络中尚未产生连边的两个节点之间产生连接的可能性[1].链路预测在很多领域受到广泛关注，实现链路预测的方法也有很多，可以从不同的角度对网络中的已知数据尽可能地进行刻画.在计算机领域，链路预测的研究思路和方法主要基于马尔科夫链和机器学习，后来Zhu[2]等人将马尔科夫链的预测方法扩展到了WWW网络的预测中；之后，应用节点属性的预测方法在实验中得到了很好的预测效果，Lin[3]基于节点的属性定义了节点间的相似性，可以直接用来进行链路预测.但是在很多情况下这些属性信息的获取非常困难，而且即使获得了节点的属性信息也很难保证信息的可靠性(可信性)；相比节点的属性信息，网络的结构信息更容易获得、更可靠，所以基于网络结构的预测方法在最近几年越来越受关注.其中，基于网络局部信息进行链路预测的方法比较常用，基于局部信息的相似性指标[4]是指那些只通过节点局部信息即可计算得到的相似性指标，基于共同邻居的相似性指标很多学者从不同方面构造了不同的指标来进行相似性检验.在此，我们提出局部社团结构指标这一链路预测新指标.

1链路预测

网络是一个包含大量个体及个体间相互作用的系统，是把某种现象或关系抽象为个体(节点)及个体之间相互作用(边)而形成的用来描述这一现象或关系的图.对任意真实网络我们能得到一个观测网络，但在记录网络的过程中由于信息的不完全性，观测网络往往会有链路的缺失问题：1).实际存在但未被探测到(信息丢失)；2).暂时不存在但应该存在或很可能存在(涉及私密刻意隐藏).网络中的链路预测[1,5]就是通过已知的网络节点以及网络结构等信息来预测网络中尚未产生连边的两个节点之间产生连接的可能性.

Γ(x)：节点x的所有邻居节点集合；

z:z∈Γ(x)∩Γ(y)，节点x,y的共同邻居；

cxz：节点x与节点z共同的邻居数；

dx：节点x的度；

rxz：节点x与z的紧密性；

sxy：节点x与y的相似性.

2基于共同邻居的相似性指标

基于网络局部结构信息的具有代表性的相似性指标主要有：

1)CN[6]，两节点间共同邻居数越多，相似性越大；

2)AA[7]，度小的共同邻居节点的贡献要大于度大的共同邻居节点；

3)RA[8]，该指标来源于资源传递过程中共同邻居作为媒介实行的一个平均分配.

2.1CN指标(Common Neighbor)

在链路预测中应用CN指标的基本假设是，两个未连接的节点如果有更多的共同邻居，则它们更倾向于连边.CN指标被定义为

即两节点之间的相似性就等于它们共同的邻居数.

2.2AA指标(Adamic-Adar)

Adamic-Adar为每个共同邻居节点赋予了一个权重：该邻居节点度的对数的倒数，他们将AA指标定义为

该指标的意思是两个节点都与一个度比较小的节点相连，那么这两个节点相连的概率将会增大.即度小的共同邻居节点的贡献要大于度大的共同邻居节点，例如在社交网络中，共同关注一个比较冷门的人或物的两个人之间相连的概率往往会比关注同一个关注度较高的人或事物的两个人之间相连的概率要高.

2.3RA指标(Resource Allocation)

这是周涛[8]等人提出的资源分配指标，该指标考虑的是未直接相连的两个节点之间的资源传递过程，它们的共同邻居节点作为传递的媒介.RA指标也是考虑两个节点共同邻居的度的信息，与AA指标有异曲同工之妙.周涛等人为每个共同邻居节点赋予了一个权重值：该邻居节点度的倒数，他们将RA指标定义为

RA指标相对AA指标来说，只是赋予共同邻居节点权重的方式不同，当网络的平均度较大的时候两者的效果才会显示较大的区别.

3LCS指标的构建

社团结构[9]是指网络由很多社团构成，社团内部连边紧密，社团之间连边甚少.通过研究网络的社团结构，可以揭示网络功能性模块组成结构，刻画网络具有的某些重要性质.众多学者对划分网络中社团结构的算法进行了大量的研究.

网络中任意两节点之间的相似性和它们之间的局部结构密度具有一定的关联度.而社团结构刻画节点之间的亲疏关系.将社团结构的思想引入链路预测，考察两个节点的每一个共同邻居节点与这两个节点本身构成的局部结构的亲疏关系，可以构造新的链路预测算法.

3.1LCS指标(Local Community Structure)

受网络社团结构的启发，由节点x，y及其所有邻居节点组成的小网络中，定义共同邻居节点z与节点x，y的归属关系分别为

rxz表示节点z和由z，x共同邻居组成的局部结构之间的亲疏关系，值越大表明关系越密切.

我们定义如下的LCS指标：

显然，LCS指标刻画了基于每一个共同邻居构成的局部结构相似程度的节点相似性.

3.2LCS指标的矩阵计算

根据吕林媛和周涛在文献[4]中给出的链路预测实验方案和基于相似性的链路预测程序，我们首先给出LCS的矩阵计算方式(Matlab语言).

将观测网络中的连边随机划分为训练集ET和测试集EP，E=ET+EP，且ET∩EP=φ.随机选取90%的边作为训练集，剩余10%的边作为测试集，通过AUC评价指标来计算各算法的预测精度.对不同的指标在不同真实网络中的预测精度100次随机实验取平均.

因为

则有如下相似度矩阵计算的Matlab语句:

3.3真实网络数据

我们在如下7个真实网络中计算LCS指标及相关的三个指标(CN、AA、RA)的预测精确度(以AUC指标衡量).实验基本参数设置、测试主程序、相关的三个指标(CN、AA、RA)的实现均采用文献[5]的标准.

表1　真实网络数据

网络的簇系数[10](在图论中也叫集聚系数)，该系数通常用来刻画网络的局域结构性质，上述网络根据簇系数，可大概分为两类：前五个网络的集聚性表现得较为明显，可视为一些具有社团结构的网络；而路由器网络和美国西部电力网具有明显的稀疏性，不仅簇系数很低，网络节点的平均度也很小.

3.4实验结果

我们将上述四个相似性指标在7个真实网络中的预测精确度(AUC指标衡量)记录在表2中.

表2　预测精确度比较(AUC)

从上表中可以看出LCS指标在前五个网络中的预测精确度(AUC指标衡量)好于其他三个指标，而在后两个网络中表现平平.

4结论

网络的社团结构是内部联系高度聚集，外部联系相对稀疏的网络局部结构.一个网络的簇系数越高，说明该网络在某种意义下的聚集度越高.网络中两个节点x和y的LCS指标刻画了它们的所有共同邻居z属于x和z(y和z)构成的局部结构的聚集程度.因此，我们分析LCS指标可以在一些簇系数较高的真实网络中具有较好的预测效果.

对7个拥有不同簇系数的真实网络仿真实验表明我们的分析是合理的，LCS指标能够在簇系数较大的网络中提高链路预测的精确度.

【参考文献】

[1]吕琳媛.复杂网络链路预测[J].电子科技大学学报，2010,39(5):651-661.

LYU Linyuan. Link prediction in complex networks[J]. Journal of University of Electronic Science and Technology,2010,39(5):651-661.

[2]ZHU J, HONG J, HUGHES J G. Soft-Ware 2002:Computing in an Imperfect World[M]. Berlin Heidelberg: Springer,2002:60-73.

[3]LIN D. An information-theoretic definition of similarity[C]// Proceedings of the Fifteenth International Conference on Machine Learning. San Francisco: Morgan Kaufman Publishers,1998:296-304.

[4]NOWELL D L, KLEINBERG J. The link-prediction problem for social networks[J]. Journal of American Society for Information Science and Technology,2007,58(7):1019-1031.

[5]吕琳媛,周涛.链路预测[M].北京：高等教育出版社,2013：8.

[6]LORRAIN F, WHITE H C. Structural equivalence of individuals in social networks[J]. The Journal of Mathematics Sociology,1971,1(1):49-80.

[7]ADAMIC L A, ADAR E. Friends and neighbors on the web[J].Social Networks,2003,25(3):211-230.

[8]ZHOU T, LYU L, ZHANG Y C. Predicting missing links via local information[J]. The European Physical Journal B,2009,71(4):623-630.

[9]郭世泽,陆哲明.复杂网络基础理论[M].北京：科学出版社,2012:265-270.

[10]FENG X, ZHAO J C, XU K. Link prediction in complex networks: a clustering perspective[J].The European Physical Journal B-Condensed Matter and Complex Systems,2012,85(1):1-9.

A new measurement of link prediction based on common neighbors

GUO Tingting，ZHAO Chengye

(College of Sciences, China Jiliang University, Hangzhou 310018, China)

Abstract:We presented a new similarity measurement, the local community structure(LCS)in networks. Under the premise of local information on networks, the LCS measurement characterized the relationship between any two nodes in a network with their common neighbors. By a comparison of AUC, CN, AA, RA and LCS in seven real networks, we found that the accuracy of LCS was better than the other three measurements in the networks with big clustering coefficients.

Key words:link prediction; local similarity; community structure; AUC; clustering coefficient

【文章编号】1004-1540(2015)01-0121-04

DOI:10.3969/j.issn.1004-1540.2016.01.022

【收稿日期】2015-09-23《中国计量学院学报》网址：zgjl.cbpt.vnki.net

【基金项目】国家自然科学基金面上项目(No. 61173002)，浙江省自然科学基金资助项目(No. LY14F020040).

【作者简介】郭婷婷(1991-)，女，山西省平遥人，硕士研究生，主要研究方向为图论、算法设计与分析、复杂网络链路预测．

【中图分类号】TN711;O157.6

【文献标志码】A

Email：tean_g@163. com

通信联系人：赵承业，男，副教授.Email: cyzhao@cjlu. edu. cn