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

第２７卷第１期　２０１６年３月　中国计量学院学报　Ｖｏ１．２７　ＮＯ．１　Ｍａｒ．２０１６　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｈｉｎａ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｍｅｔｒｏｌｏｇｙ　【文章编号１　１００４—１５４０（２０１５）０１—０１２１—０４　ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１００４—１５４０．２０１６．０１．０２２　基于共同邻居的链路预测新指标　郭婷婷，赵承业　（中国计量学院理学院，浙江杭州３１００１８）　【摘　要】提出一个新的链路预测相似性指标——局部社团结构指标（Ｌｏｃａｌ　Ｃｏｍｍｕｎｉｔｙ　Ｓｔｒｕｃｔｕｒｅ，ＬＣＳ）．在　已知网络局部信息的前提下，ＬＣＳ指标刻画了网络中任意两个节点的共同邻居节点与这两个节点的聚集关　系．在基于真实网络的实验中，我们计算并比较了ＣＮ、ＡＡ、ＲＡ和ＬＣＳ四个指标在７个不同真实网络中的　ＡＵＣ评价指标，发现在簇系数较大的真实网络中ＬＣＳ指标的预测结果好于其他三个指标．　【关键词】链路预测；局部相似性；社团结构；ＡＵＣ评价指标；簇系数　【中图分类号】ＴＮ７１１；Ｏ１５７．６　【文献标志码】Ａ　Ａ　ｎｅｗ　ｍｅａｓｕｒｅｍｅｎｔ　ｏｆ　ｌｉｎｋ　ｐｒｅｄｉｃｔｉｏｎ　ｂａｓｅｄ　ｏｎ　ｃｏｍｍｏｎ　ｎｅｉｇｈｂｏｒｓ　ＧＵＯ　Ｔｉｎｇｔｉｎｇ，ＺＨＡＯ　Ｃｈｅｎｇｙｅ　（Ｃｏｌｌｅｇｅ　ｏｆ　Ｓｃｉｅｎｃｅｓ，Ｃｈｉｎａ　Ｊｉｌｉａｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｈａｎｇｚｈｏｕ　３１００１８，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｗｅ　ｐｒｅｓｅｎｔｅｄ　ａ　ｎｅｗ　ｓｉｍｉｌａｒｉｔｙ　ｍｅａｓｕｒｅｍｅｎｔ，ｔｈｅ　ｌｏｃａｌ　ｃｏｍｍｕｎｉｔｙ　ｓｔｒｕｃｔｕｒｅ（ＬＣＳ）ｉｎ　ｎｅｔｗｏｒｋｓ．　Ｕｎｄｅｒ　ｔｈｅ　ｐｒｅｍｉｓｅ　ｏｆ　ｌｏｃａｌ　ｉｎｆｏｒｍａｔｉｏｎ　ｏｎ　ｎｅｔｗｏｒｋｓ，ｔｈｅ　ＬＣＳ　ｍｅａｓｕｒｅｍｅｎｔ　ｃｈａｒａｃｔｅｒｉｚｅｄ　ｔｈｅ　ｒｅｌａｔｉｏｎｓｈｉｐ　ｂｅｔｗｅｅｎ　ａｎｙ　ｔＷＯ　ｎｏｄｅｓ　ｉｎ　ａ　ｎｅｔｗｏｒｋ　ｗｉｔｈ　ｔｈｅｉｒ　ｃｏｍｍｏｎ　ｎｅｉｇｈｂｏｒｓ．Ｂｙ　ａ　ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ＡＵＣ，ＣＮ，ＡＡ，ＲＡ　ａｎｄ　ＬＣＳ　ｉｎ　ｓｅｖｅｎ　ｒｅａｌ　ｎｅｔｗｏｒｋｓ，ｗｅ　ｆｏｕｎｄ　ｔｈａｔ　ｔｈｅ　ａｃｃｕｒａｃｙ　ｏｆ　ＬＣＳ　ｗａｓ　ｂｅｔｔｅｒ　ｔｈａｎ　ｔｈｅ　ｏｔｈｅｒ　ｔｈｒｅｅ　ｍｅａｓｕｒｅｍｅｎｔｓ　ｉｎ　ｔｈｅ　ｎｅｔｗｏｒｋｓ　ｗｉｔｈ　ｂｉｇ　ｃｌｕｓｔｅｒｉｎｇ　ｃｏｅｆｆｉｃｉｅｎｔｓ．　Ｋｅｙ　ｗｏｒｄｓ：ｌｉｎｋ　ｐｒｅｄｉｃｔｉｏｎ；ｌｏｃａｌ　ｓｉｍｉｌａｒｉｔｙ；ｃｏｍｍｕｎｉｔｙ　ｓｔｒｕｃｔｕｒｅ；ＡＵＣ；ｃｌｕｓｔｅｒｉｎｇ　ｃｏｅｆｆｉｃｉｅｎｔ　网络中的链路预测是指如何通过已知的网络　思路和方法主要基于马尔科夫链和机器学习，后来　Ｚｈｕｌ＿２　等人将马尔科夫链的预测方法扩展到了　ＷＷＷ网络的预测中；之后，应用节点属性的预测　方法在实验中得到了很好的预测效果，Ｌｉ　３＿基于　节点以及网络结构等信息，预测网络中尚未产生连　边的两个节点之间产生连接的可能性ｌ＿１］．链路预测　在很多领域受到广泛关注，实现链路预测的方法也　有很多，可以从不同的角度对网络中的已知数据尽　节点的属性定义了节点间的相似性，可以直接用来　进行链路预测．但是在很多情况下这些属性信息的　可能地进行刻画．在计算机领域，链路预测的研究　【收稿日期】２Ｏ１５一Ｏ９—２３　《中国计量学院学报》网址：ｚｇｊ１．ｅｂｐｔ．ｖｎｋｉ．ｎｅｔ　【基金项目】国家自然科学基金面上项目（Ｎｏ．６１１７３００２），浙江省自然科学基金资助项目（Ｎｏ．ＬＹ１４Ｆ０２００４０）．　【作者简介】郭婷婷（１９９１一），女，山西省平遥人，硕士研究生，主要研究方向为图论、算法设计与分析、复杂网络链路预测　Ｅｍａｉｌ：ｔｅａｎｇ＠１６３．ＣＯＷｌ　＿通信联系人：赵承业，男，副教授．Ｅｍａｉｌ：ｃｙｚｈａｏ＠ｃｊｌｕ．ｅｄｕ．ｃｎ　１２２　中　国计量学　院学报　第２７卷　获取非常困难，而且即使获得了节点的属性信息也　３）ＲＡ；引，该指标来源于资源传递过程中共　同邻居作为媒介实行的一个平均分配．　２．１　ＣＮ指标（Ｃｏｍｍｏｎ　Ｎｅｉｇｈｂｏｒ）　很难保证信息的可靠性（可信性）；相比节点的属性　信息，网络的结构信息更容易获得、更可靠，所以基　于网络结构的预测方法在最近几年越来越受关注．　其中，基于网络局部信息进行链路预测的方法比较　常用，基于局部信息的相似性指标　是指那些只通　过节点局部信息即可计算得到的相似性指标，基于　共同邻居的相似性指标很多学者从不同方面构造　了不同的指标来进行相似性检验．在此，我们提出　在链路预测中应用ＣＮ指标的基本假设是，　两个未连接的节点如果有更多的共同邻居，则它　们更倾向于连边．ＣＮ指标被定义为　Ｓ　一Ｉ　Ｉ、（ｚ）ｎ　ｒ（　）１．　即两节点之间的相似性就等于它们共同的邻　居数．　局部社团结构指标这一链路预测新指标．　１　链路预测　网络是一个包含大量个体及个体间相互作用　的系统，是把某种现象或关系抽象为个体（节点）　及个体之间相互作用（边）而形成的用来描述这一　现象或关系的图．对任意真实网络我们能得到一　个观测网络，但在记录网络的过程中由于信息的　不完全性，观测网络往往会有链路的缺失问题：　１）．实际存在但未被探测到（信息丢失）；２）．暂时　不存在但应该存在或很可能存在（涉及私密刻意　隐藏）．网络中的链路预测［１　就是通过已知的网　络节点以及网络结构等信息来预测网络中尚未产　生连边的两个节点之间产生连接的可能性．　任一网络均可抽象为图Ｇ一（、／，，Ｅ），其中　为网络中所有节点构成的集合，　为网络中所有　边组成的集合．对任意节点ｚ，　∈Ｖ，有　ｒ（ｚ）：节点ｚ的所有邻居节点集合；　：　∈ｒ（ｚ）ｎ　ｒ（　），节点　，　的共同邻居；　ｆ　０，　与Ｙ不相连　’　Ｉ　１，　与　有连边　’　Ｃ　：节点ｚ与节点ｚ共同的邻居数；　ｄ　：节点ｚ的度；　ｒ　：节点ｚ与ｚ的紧密性；　Ｓ　：节点ｚ与Ｙ的相似性．　２　基于共同邻居的相似性指标　基于网络局部结构信息的具有代表性的相似　性指标主要有：　１）ＣＮＥ引，两节点间共同邻居数越多，相似性　越大；　２）Ａ　Ａ［　，度小的共同邻居节点的贡献要大　于度大的共同邻居节点；　２．２　ＡＡ指标（Ａｄａｍｉｃ－Ａｄａｒ）　Ａｄａｍｉｃ—Ａｄａｒ为每个共同邻居节点赋予了一　个权重：该邻居节点度的对数的倒数，他们将ＡＡ　指标定义为　一　～　。∈ｒ（　ｒ（ｖ）ｌｏｇｄ　‘　该指标的意思是两个节点都与一个度比较小　的节点相连，那么这两个节点相连的概率将会增　大．即度小的共同邻居节点的贡献要大于度大的　共同邻居节点，例如在社交网络中，共同关注一个　比较冷门的人或物的两个人之间相连的概率往往　会比关注同一个关注度较高的人或事物的两个人　之间相连的概率要高．　２．３　ＲＡ指标（Ｒｅｓｏｕｒｃｅ　Ａｌｌｏｃａｔｉｏｎ）　这是周涛＿８Ｊ等人提出的资源分配指标，该指　标考虑的是未直接相连的两个节点之间的资源传　递过程，它们的共同邻居节点作为传递的媒介．　ＲＡ指标也是考虑两个节点共同邻居的度的信　息，与ＡＡ指标有异曲同工之妙．周涛等人为每个　共同邻居节点赋予了一个权重值：该邻居节点度　的倒数，他们将ＲＡ指标定义为　ｚＥ　ｒ（　）ｎｒ（　）　去·　ＲＡ指标相对ＡＡ指标来说，只是赋予共同邻　居节点权重的方式不同，当网络的平均度较大的　时候两者的效果才会显示较大的区别．　３　ＬＣＳ指标的构建　社团结构嘲是指网络由很多社团构成，社团　内部连边紧密，社团之间连边甚少．通过研究网络　的社团结构，可以揭示网络功能性模块组成结构，　刻画网络具有的某些重要性质．众多学者对划分　网络中社团结构的算法进行了大量的研究．　第１期　郭婷婷，赵承业：基于共同邻居的链路预测新指标　１２３　网络中任意两节点之间的相似性和它们之间　的局部结构密度具有一定的关联度．而社团结构　刻画节点之间的亲疏关系．将社团结构的思想引　首先给出ＬＣＳ的矩阵计算方式（Ｍａｔｌａｂ语言）．　将观测网络中的连边随机划分为训练集Ｅ　和测试集Ｅ　，Ｅ—Ｅ　＋Ｅ　，且Ｅ　ｎ　Ｅ　一　．随机　入链路预测，考察两个节点的每一个共同邻居节　点与这两个节点本身构成的局部结构的亲疏关　系，可以构造新的链路预测算法．　３．１　ＬＣＳ指标（Ｌｏｃａｌ　Ｃｏｍｍｕｎｉｔｙ　Ｓｔｒｕｃｔｕｒｅ）　选取９０　９／６的边作为训练集，剩余１Ｏ　的边作为　测试集，通过ＡＵＣ评价指标来计算各算法的预测　精度．对不同的指标在不同真实网络中的预测精　度１００次随机实验取平均．　对任意连边（ｉ，Ｊ）∈Ｅ　ｔ—Ｔ　度向量　ｄ—ｓｕｍ（Ｔ，２），贝０　ｆ　一（Ｔ＊丁）　＝＝＝Ｃ　，　受网络社团结构的启发，由节点．７Ｃ，　及其所　有邻居节点组成的小网络中，定义共同邻居节点　ｚ与节点ｚ，　的归属关系分别为　ｒ一一　，，．　一　·　Ｄ—ｒｅｐｍａｔ（ｄ，［１，ｓｉｚｅ（Ｔ，１）］）．　因为　一　表示节点　和由ｚ，ｚ共同邻居组成的局部　结构之间的亲疏关系，值越大表明关系越密切．　我们定义如下的ＬＣＳ指标：　ｓ　（ｒ　＋ｒ　）一　ｚＥｒ（ｚ）ｎ　ｒ（　）　一　一（ｃ·／Ｄ）　：Ｒ　，　垒一－　一　ｒ（Ｊ）ｄ　∈ｒ　ｄ女　）女∈ｒ　，　（　）＋　）　，　ｆ　＋　１＿　∈ｒ（　）则有如下相似度矩阵计算的Ｍａｔｌａｂ语句：　Ｓｉｍ—Ｔ＊（丁·＊Ｒ）＋（Ｔ·＊Ｒ　）＊丁　＼ｄ　。ｄ　／　Ｃｘ＿＿＿ｚＳ　４－　∈ｒ　ｄ　’　∈ｒ　ｒ（　）ｒ（　）ｄ　‘　３．３真实网络数据　显然，ＬＣＳ指标刻画了基于每一个共同邻居　构成的局部结构相似程度的节点相似性．　３．２　ＬＣＳ指标的矩阵计算　我们在如下７个真实网络中计算ＬＣＳ指标　及相关的三个指标（ＣＮ、ＡＡ、ＲＡ）的预测精确度　（以ＡＵＣ指标衡量）．实验基本参数设置、测试主　程序、相关的三个指标（ＣＮ、ＡＡ、ＲＡ）的实现均采　根据吕林媛和周涛在文献［４］中给出的链路　预测实验方案和基于相似性的链路预测程序，我们　用文献［５］的标准．　表１真实网络数据　Ｔａｂｌｅ　１　Ｒｅａｌ　ｎｅｔｗｏｒｋ　ｄａｔａ　网络　线虫神经网络　节点数　边数　平均度　簇系数　佛罗里达海湾雨季的食物链网络　美国政治博客网络　红树林河口湿季的食物链网络　美国足球队网络　Ｉｎｔｅｒｎｅｔ路由器网络　美国西部电力网　网络的簇系数ｍ　（在图论中也叫集聚系数），　明显的稀疏性，不仅簇系数很低，网络节点的平均　度也很小．　３．４实验结果　该系数通常用来刻画网络的局域结构性质，上述　网络根据簇系数，可大概分为两类：前五个网络的　集聚性表现得较为明显，可视为一些具有社团结　构的网络；而路由器网络和美国西部电力网具有　我们将上述四个相似性指标在７个真实网络　中的预测精确度（ＡＵＣ指标衡量）记录在表２中．　１２４　中　国　计量从上表中可以看出ＬＣＳ指标在前五个网络　中的预测精确度（ＡＵＣ指标衡量）好于其他三个　指标，而在后两个网络中表现平平．　４　结　论　网络的社团结构是内部联系高度聚集，外部　联系相对稀疏的网络局部结构．一个网络的簇系　数越高，说明该网络在某种意义下的聚集度越高．　网络中两个节点ｚ和　的ＬＣＳ指标刻画了它们　的所有共同邻居ｚ属于ｚ和　（　和２）构成的局　部结构的聚集程度．因此，我们分析ＬＣＳ指标可　以在一些簇系数较高的真实网络中具有较好的预　测效果．　对７个拥有不同簇系数的真实网络仿真实验　表明我们的分析是合理的，ＬＣＳ指标能够在簇系　数较大的网络中提高链路预测的精确度．　【参　考　文　献】　［１］　吕琳媛．复杂网络链路预测［Ｊ］．电子科技大学学报，２０１０　３９（５）：６５卜６６１．　Ｉ　Ｙｕ　Ｌｉｎｙｕａｎ．Ｌｉｎｋ　ｐｒｅｄｉｃｔｉｏｎ　ｉｎ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋｓ［Ｊ］　Ｊｏｕｒｎａｌ　ｏｆ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｅｌｅｃｔｒｏｎｉｃ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ　２Ｏ１０，３９（５）：６５１—６６１．　学　院学报　第２７卷　［２］ＺＨＵ　Ｊ，ＨＯＮＧ　Ｊ，ＨＵＧＨＥＳ　Ｊ　Ｇ．Ｓｏｆｔ－Ｗａｒｅ　２００２：Ｃｏｍｐｕ’　ｒｉｎｇ　ｉｎ　ａｎ　Ｉｍｐｅｒｆｅｃｔ　Ｗｏｒｌｄ［Ｍ］．Ｂｅｒｌｉｎ　Ｈｅｉｄｅｌｂｅｒｇ：Ｓｐｒｉｎｇ—　ｅｒ，２０Ｏ２：６Ｏ一７３．　ｒ３］ＬＩＮ　Ｄ．Ａｎ　ｉｎｆｏｒｍａｔｉｏｎ—ｔｈｅｏｒｅｔｉｃ　ｄｅｆｉｎｉｔｉｏｎ　ｏｆ　ｓｉｍｉｌａｒｉｔｙ　［ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｆｉ￣ｅｅｎｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ：Ｍｏｒｇａｎ　Ｋａｕｆｍａｎ　Ｐｕｂｌｉｓｈｅｒｓ，１９９８：２９６－３０４．　ｒ４］ＮＯＷＥＬＬ　Ｄ　Ｌ，ＫＬＥＩＮＢＥＲＧ　Ｊ．Ｔｈｅ　ｌｉｎｋ　ｐｒｅｄｉｃｔｉｏｎ　ｐｒｏｂ—　ｌｅｍ　ｆｏｒ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋｓ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ａｍｅｒｉｃａｎ　Ｓｏｃｉｅｔｙ　ｆｏｒ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，２００７，５８（７）：１０１９　１０３１．　［５］　吕琳媛，周涛．链路预ＮＥＭ］．北京：高等教育出版社，２０１３：８．　ｇ６］ＬＯＲＲＡＩＮ　Ｆ，ＷＨＩＴＥ　Ｈ　Ｃ．Ｓｔｒｕｃｔｕｒａｌ　ｅｑｕｉｖａｌｅｎｃｅ　ｏｆ　ｉｎｄｉ—　ｖｉｄｕａｌｓ　ｉｎ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋｓ［Ｊ］．Ｔｈｅ　Ｊｏｕｒｎａｌ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ　Ｓｏｃｉｏｌｏｇｙ，１９７１，１（１）：４９—８Ｏ．　ｒ　７］　ＡＤＡＭＩＣ　Ｌ　Ａ，ＡＤＡＲ　Ｅ．Ｆｒｉｅｎｄｓ　ａｎｄ　ｎｅｉｇｈｂｏｒｓ　ｏｎ　ｔｈｅ　ｗｅｂＥＪ￣．Ｓｏｃｉａｌ　Ｎｅｔｗｏｒｋｓ，２００３，２５（３）：２１卜２３０．　［８］ＺＨＯＵ　Ｔ，ＬＹＵ　Ｌ，ＺＨＡＮＧ　Ｙ　Ｃ．Ｐｒｅｄｉｃｔｉｎｇ　ｍｉｓｓｉｎｇ　ｌｉｎｋｓ　ｖｉａ　ｌｏｃａｌ　ｉｎｆｏｒｍａｔｉｏｎ￣Ｊ］．Ｔｈｅ　Ｅｕｒｏｐｅａｎ　Ｐｈｙｓｉｃａｌ　Ｊｏｕｒｎａｌ　Ｂ，　２００９，７１（４）：６２３－６３０．　Ｅ９］郭世泽，陆哲明．复杂网络基础理论［Ｍ］．北京：科学出版　社，２０１２：２６５　２７０．　［１０］ＦＥＮＧ　Ｘ，ＺＨＡＯ　Ｊ　Ｃ，ＸＵ　Ｋ．Ｌｉｎｋ　ｐｒｅｄｉｃｔｉｏｎ　ｉｎ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋｓ：ａ　ｃｌｕｓｔｅｒｉｎｇ　ｐｅｒｓｐｅｃｔｉｖｅ［Ｊ］．Ｔｈｅ　Ｅｕｒｏｐｅａｎ　Ｐｈｙｓ—　ｉｃａｌ　Ｊｏｕｒｎａｌ　Ｂ－Ｃｏｎｄｅｎｓｅｄ　Ｍａｔｔｅｒ　ａｎｄ　Ｃｏｍｐｌｅｘ　Ｓｙｓｔｅｍｓ，　２Ｏ１２，８５（１）：１　９．