一种改进的二分网络链路预测算法

马吴迪， 胡学钢， 何 伟

（合肥工业大学 计算机与信息学院，安徽 合肥 230009）

0 引 言

复杂网络是由数量巨大的节点和节点之间错综复杂的关系共同构成的网络结构。复杂网络中节点之间关系会随时间的流逝不断变化，这种动态特性，使网络整体的拓扑结构不断进行着演化。链路预测［1］是利用网络的拓扑结构来预测网络中节点对之间缺失［2－4］或可能产生的链接，是探索和分析网络结构演化的重要手段。如在社交网络中好友关系链路预测利用已存在的好友关系预测将来哪些用户会成为好友；会员参与互动话题的关系网络［5］通过目前会员参与话题的情况预测会员未来会参与哪些话题等。

根据目标网络中的节点类型，已有的复杂网络研究可以分为单分网络和二分网络2类。如果一个网络中包含2类节点，并且网络中的边只存在于不同类型的节点间，称为二分网络［6］，其抽象的拓扑图为二部图。现实世界中二分网络的普遍性，使得针对二分网络不同类型节点间的链路预测具有广泛的应用价值。单分网络中的链路预测算法往往是基于节点对的结构相似度来进行预测的［7］。二部图中产生链接的节点对属于不同类别，其邻居节点也分别属于不同类别，这使得单分网络的链路预测算法无法直接应用在二分网络中。

ILP［8］是一种有效的二分网络链路预测方法，但是由于其采用单向的投影策略即底部投影，容易导致信息丢失。本文在内部链路预测算法ILP的基础上，提出一种改进的链路预测算法ILPExt，采用底部和顶部双向投影策略，避免了丢失信息，从而提高了链路预测的精度。

1 相关工作

已有的二分网络链路预测算法中，大都是通过计算节点之间的相似性进行预测，主要分为2类，如图1所示。

图1 二分网络链路预测算法类别

（1）基于图邻接矩阵的代数运算［9］。通过对整个网络的邻接矩阵分解［10］，不仅仅得到节点近邻的信息，还能够计算整个网络的信息，在图邻接矩阵的转换中能够用来进行链路预测，该类方法称为代数链路预测算法。假设A代表图的链接矩阵，在Ai中（u，v）位置代表了节点u到节点v的步数为i的路径数。在二分网络中链接的节点对都是奇数个，因此i都取奇数。

代数链路预测算法由于其可扩展性和可学习性的特点，得到广泛的关注。其可伸缩性特点是由于其依赖的邻接矩阵模型只需要一次建立，在推荐算法中速度较快，模型对应的矩阵分解能够通过迭代计算进行更新。其可学习性表现在其参数都用相同的方法训练得到。但是该类算法在计算时内存开销比较大。

（2）基于局部信息的方法，采用与节点度有关联的指标。单分网络中提出来的基于局部信息的指标中，有限链接PA（Preferential Attachment）是唯一应用在二分网络中的链路预测算法。它基于这样的假设：若2个节点的邻居越多，则它们之间越有可能产生连边。节点对（u，v）的相似度计算为2个节点度的乘积除以边数：d（u）×d（v）／2｜E｜，其中，d（u）表示节点u的邻居个数；E表示网络中已有的边数。PA算法的特点在于所需要的信息较少，但其适用的网络具有一定的局限性。

除了基于相似性的算法，一些更复杂的算法不断地被提出。文献［2］提出了一个基于层次化网络结构的算法，根据节点在层次网络中的深度预测其横向连接概率的依赖性，并对其进行排序来预测缺失边；文献［11－12］分别将物理过程中的能量扩散和热传导引入信息推荐方面，虽然相关的问题还没有被充分研究，但为提高链路预测算法的精度和效率提供了一种有效的途径。

本文基于内部链路的算法与上述所列的算法不同，它们是计算节点对的相似度值，然后根据值的大小排序，值越大的越有可能产生链接。内部链路预测算法是通过定义内部链边，找出所有的内部链边，这些内部链边就是所要预测的边。内部链接的定义是基于如下假设：如果2个底部节点有共同邻居，那么它们以后会有更多的共同邻居；否则，如果它们没有共同邻居，那么它们将来也不会有共同邻居。

2 改进的内部链路预测ILPExt算法

2.1 基本定义

一个动态变化的二部图，在n个时间点能够得到一个链边集合：D＝｛（ti，ui，vi），i＝1，…，n｝。用G＝（⊥，T，E）表示一个从时刻a到时刻b（b＞a）的二部图，其中，⊥＝｛u，∃（t，u，v）∈D，a≤t＜b｝为底部节点集合，Τ＝｛v，∃（t，u，v）∈D，a≤t＜b｝为顶部节点集合，以E＝｛（u，v），∃（t，u，v）∈D，a≤t＜b｝为边集。G是参考图，［a，b］为参考时段，是研究问题需要利用的信息。在之后的任一时刻c（c＞b），［b，c］这段时间内，图G中将出现一个新边集E′＝｛（u，v），∃（t，u，v）∈D，b≤t＜c｝∩（⊥×Τ－E）为测试边集，也就是只考虑（⊥×Τ－E）中的节点对哪些会生成连边，忽略在［b，c］时间段新出现的节点。

二部图是由1个顶部节点集合（用符号⊥表示）、1个底部节点集合（用符号Τ表示）和1个由顶部节点和底部节点的链接边集（用符号E表示）组成的图。二部图中节点的邻居，定义为N（u）＝｛v∈（⊥∪Τ），（u，v）∈E｝，节点u的邻居是在二部图中所有与u相连的节点。在二部图投影的图中如果2个节点有至少1个共同邻居，它们在投影的图中就产生链接，那么二部图G投影的节点由底部节点构成，用G⊥表示，顶部节点的投影用GΤ表示。例如，图2所示为二部图，图3所示为二部图投影。

图2 二部图G

图3 二部图投影图

基于内部链边的链路预测算法ILP首先找出所有可能的内部链边（internal link），然后通过附加的权值函数以及权值阈值过滤掉权值较低的边。剩下的边即是要预测的边。它基于的思想是如果2个底部节点有共同邻居，那么它们会有越来越多的共同邻居。ILP算法在第1步节点投影过程中，通过投影利用了网络中底部节点的拓扑信息，没有对顶部节点投影，从而丢失了顶部节点所包含的信息。

下面来说明丢失顶部信息的情况。观察图2中节点对（B，l），首先，对二部图底部投影，投影图如图3a，（B，l）诱导的节点对集｛（B，C），（B，D），（B，E）｝在图3a中都有连边，因此（B，l）在底部投影时是内部链边。然后对图2进行顶部节点投影，投影出来的拓扑图如图3b所示，由节点对（B，l）诱导的节点对集｛（i，l），（j，l），（k，l），（m，l）｝，前面3个投影图中都有连边，而节点对（m，l）由于在图2中没有共同邻居，在投影图中不存在这个边，所以节点对（B，l）就不是内部连边。

节点对（B，l）在采用底部节点投影时是内部链边，而采用顶部节点投影时不是内部链边。同理，这种情况节点对也可能在顶部投影中是内部链边，而在底部投影中却不是内部链边。因此采取单一类节点投影总会丢失另一类节点所包含的信息。

2.2 ILPExt算法描述

本文提出改进的基于内部链边链路预测ILPExt算法，将同时采用顶部节点投影和底部节点投影，由此产生顶部内部链边集合和底部内部链边集合，将这2个集合合并，相同的边只保留1条，运算的结果即是要预测的边集。ILPExt算法步骤描述如下：

（1）对二部图G分别进行顶部和底部投影，得到顶部投影边集E⊥和底部投影边集EΤ。

（2）在G中遍历所有未链接的节点对，找出所有的内部链边，集合记为Ei1。

（3）过滤2个投影边集EΤ和E⊥，将权值小于指定阈值的边都删除，得到EΤ和E⊥。

（4）过滤内部链边集合Ei1：如果内部链边的引起边至少有1条属于（E⊥∪EΤ） ，则保留该边，否则删除。

（5）筛选出来的内部链边集合Ei1就是该算法的预测边集。

假设网络中顶部节点数为N，底部节点数为M，边数为R。ILPExt算法总的时间复杂度由投影和内部链边的查找构成。

计算顶部和底部投影，需要分别遍历顶部节点和底部节点的邻居来生成投影图的边。对顶部节点投影时，判断顶部节点对是否有共同邻居，如果有则在投影图中有边；反之，则没有。底部节点的邻居是顶部节点，一个底部节点的邻居之间，都拥有该底部节点作为共同邻居，这样一个底部节点的邻居中随机取2个节点在顶部投影中都会有边。在顶部节点投影中，只要遍历底部节点的邻居就可以产生顶部节点的投影图，时间复杂度是O（M）。同样，底部节点投影的时间复杂度是O（N）。故顶部和底部节点投影的时间复杂度为O（N＋M）。所有未连边的节点对为N×MR个，找出内部链边过程的时间复杂度为O（N×M）。过滤2个投影边集的时间复杂度为O（R）。过滤内部链边集合，遍历所有内部链边，找出每一条链边是否在过滤后的边集EΤ和E⊥中，因此遍历内部链边集合的同时会遍历过滤后的边集EΤ和E⊥，因此时间复杂度为O（R×2）。所以，整个算法的时间复杂度为O（N×M＋R×2＋N＋M）。

3 实验结果及分析

本文的实验采用2个数据集，一个是Southern Women Data，另一个是类似facebook社交网站的用户话题网络。

（1）Southern Women Data［13］。该数据集由Davis在1930年收集，他采集了18个南部女性参加社会活动的情况。网络结构如图4所示，其中圆点代表女性个体，方点代表社会活动，节点间的边表示女性参加了活动。网络中代表妇女的节点数为18，代表活动的节点数为14，边数为89。

图4 Southern Women Data数据集的网络图

在此网络上进行链路预测，首先选出10条边作为测试集，还剩下79条边，见表1所列。

该实验分别做了20次，每次都随机抽取10条作为测试边集，实验结果见表2所列，表2中加星号的数字表示ILPExt比ILP算法效果好。每行有2个加星号表示效果一样。从实验结果中可以看出，采用顶部和底部投影产生出的内部链边并集时（ILPExt）预测出来的边较多，而采用交集时预测效果比较差。这很容易理解，内部链边并集时同时包含了2类节点的内部链边，比仅采用一类节点投影时加上了另外一类节点所产生的内部链边预测出来的也多，而交集则取2个集合的共同部分的边集仅仅是采用一类节点的一部分，预测出来的因而会少。

（2）Facebook－like Forum Network，该数据集是like－Facebook在线社交网络网站数据，该网络是由会员参与话题的关系而不是会员之间发送信息的行为来形成。网络中有899个会员和522个主题，网络中的权值是会员在参与主题中发布的消息数目，见表3所列。

表1 Southern Women Data数据集概况

表2 Southern Women Data实验详细结果

实验做了20次，实验结果见表4所列，表4中加星号的数字表示ILPExt比ILP算法效果好，每行有2个加星号表示效果一样。从表4中可以看到取2个集合的并集时（ILPExt）准确预测的边数要比分别用底部或者顶部节点投影 （ILP）准确预测出来的边要多。

表3 Facebook－like Forum Network数据集概况及结果

表4 Facebook－like Forum Network数据集实验详细结果

通过上述2组实验的结果可以看出，相比于ILP算法，改进后的ILPExt算法由于结合了2类节点的投影图，能够更加充分地利用网络蕴含的拓扑结构信息，从而能够找出更多的边，这一优势在节点较多的网络中体现更加明显。

该算法的改进是通过增大内部链边的范围，因此搜索遍历的范围增大了不少，相应的时间方面消耗过多，因此时间性能有待提高。

4 结束语

在ILP算法中，只采用了底部节点投影，找出最有可能产生边的节点对，因此丢失了顶部节点所包含的信息。本文针对ILP算法的这一不足，提出改进的ILPExt算法，将底部节点和顶部节点都投影，投影后将2个部分的内部链边集合合并，然后产生出预测边集。实验证明能够找出更多可预测的边，而且召回率甚至是原算法的2倍多。

［1］ LüL，Zhou T.Link prediction in complex networks：a survey［J］.Physica A：Statistical Mechanics and its Applications，2011，390（6）：1150－1170.

［2］ Clauset A，Moore C，Newman M E J.Hierarchical structure and the prediction of missing links in networks［J］.Nature，2008，453（7191）：98－101.

［3］ Liben－Nowell D，Kleinberg J.The link－prediction problem for social networks［J］.J Am Soc Inf Sci，2007，58：1019－1031.

［4］ Getoor L，Diehl C P.Link mining：a survey［J］.ACM SIGKDD Explorations Newsletter，2005，7（2）：3－12.

［5］ 吴亚晶，张 鹏，狄增如，等.二分网络研究［J］.复杂系统与复杂性科学，2010，7（1）：1－12.

［6］ Holme P，Liljeros F，Edling C R，et al.Network bipartivity［J］.Physical Review E，2003，68（5）：056107.

［7］ 吕琳媛.复杂网络链路预测［J］.电子科技大学学报，2010，39（5）：651－661.

［8］ Allali O，Magnien C，Latapy M.Link prediction in bipartite graphs using internal links and weighted projection［C］／／Computer Communications Workshops （INFOCOM WKSHPS），2011IEEE Conference on，2011：936－941.

［9］ Kunegis J，De Luca E W，Albayrak S.The link prediction problem in bipartite networks［C］／／Computational Intelligence for Knowledge－based Systems Design.Berlin：Springer，2010：380－389.

［10］ Chung F.Spectral graph theory［M］.Providence，Rhode Island：American Mathematical Society，1997.

［11］ Zhou T，Ren J，Medo M，et al.Bipartite network projection and personal recommendation［J］.Physical Review E，2007，76（4）：5－7.

［12］ Zhang Y C，Blattner M，Yu Y K.Heat conduction process on community networks as a recommendation model［J］.Physical Review Letters，2007，99（15）：154301（1－5）.

［13］ Freeman L C.Finding social groups：a meta－analysis of the southern women data［J］.Dynamic Social Network Modeling and Analysis，2003：39－97.