基于改进资源分配的链接预测算法

杜翠凤 陈少权 蒋仕宝

【摘 要】共同邻居的数量、共同邻居的度数、节点之间的路径长度等传统链接预测忽视邻居之间的关系以及节点本身的拓扑结构，导致其无法解决核心节点与周围节点链接强度不同的问题。采用邻域“结构洞”理论，并且结合节点本身拓扑结构以及共同邻居的拓扑结构的影响来实现网络的链接预测，提出基于改进资源分配的链接预测算法。实验证明，该算法不仅更加准确地反映了动态网络的拓扑结构，还能更加准确地预测节点之间是否存在链接关系。

【关键词】链接预测；邻域“结构洞”；资源强度；拓扑结构

Link Prediction Algorithm based on Improved Resource Allocation

DU Cuifeng， CHEN Shaoquan， JIANG Shibao

[Abstract] Traditional link prediction， such as the number of common neighbors， the degree of common neighbors and the path length between nodes， ignores the relationship between neighbors and the topological structure of nodes themselves. Thus， the different link intensity between the core node and surrounding nodes can not be solved. Using the theory of "structure hole" of the neighborhood， the link prediction of the network is realized by combining the topological structure of nodes themselves with the topological structure of the common neighbors. A link prediction algorithm based on improved resource allocation was proposed in this paper. Experimental results show that the algorithm not only reflects the topological structure of dynamic network more accurately， but also predicts more accurately whether there is a link between nodes.

[Key words]link prediction； "structure hole" of the neighborhood； resource intensity； topological structure

1 引言

在現实中，很多数据如移动通信网络数据、社会关系数据以及生物学数据都能够通过网络进行描述。因此，链接预测有广泛的应用前景[1]：通过分析移动用户的通信社会网络，引入时间序列算法，实现用户链接的动态预测[2]；基于位置社交网络的朋友关系预测研究；结合网络链接和内容的局部社区发现研究；利用链路预测推断中国航空网络演化机制。因此，设计具有扩展性强的网络链接预测模型，并用于社会网络结构变化预测和社会网络节点关系预测具有重要的意义。关于链接预测，以往的大多数研究主要建立在静态社会网络结构基础上，这种静态的研究大多数利用社会网络链接之间的结构信息进行用户关系以及网络结构变化的预测。如基于划分社区和差分共邻节点贡献的链路预测算法[3]；基于节点相似性的手机通信网络链路预测，采用共同邻居、通话时长和通话时长占比作为关键参数来实现用户之间通信的链路预测[4]；采用共同邻居的关系紧密度来进行用户紧密度的链接预测[5]。随着研究的深入，考虑到网络的动态性，学者将动态链接的问题转化成学习问题，引入了半监督技术、集成技术、机器学习等算法实现链接的动态预测。本文在借鉴前人研究的基础上，为了解决传统链接预测忽视共同邻居之间的关系、拓扑结构以及节点本身的拓扑关系的问题，本文邻域“结构洞”结合自身节点的拓扑结构、共同邻居集合中节点间拓扑关系来描述网络链接的可能性，提出基于资源分配的链接预测算法。

2 链接预测的相关研究

2.1 链接预测的定义

链接表示网络中两个节点之间的相互作用或者相互关系，链接预测就是估计网络中两个节点之间存在相关作用或者相互关系的概率大小[5]。从上述的链接预测定义得知，链接预测包括2个方面：

（1）预测未知链接。由于技术或者其他因素的限制，网络中的某些链接并不是都直接可见的，因此需要根据当前的网络结构来预测链接的存在概率，一般把网络形式化成网络静态快照，而不考虑网络的发展变化。

（2）预测未来出现的新链接。通过t时刻的链接关系，预测t+1时刻链接发生的可能性，一般把网络看成动态变化的。实际上，链接预测就是通过节点之间的相互关系或者相互作用揭示社会网络的动态变化趋势。因此，本文研究的链接预测，是在加权网络中采用边的结构权重来衡量节点之间的相互关系，并结合共同邻居集合中节点间的关系紧密程度来描述网络的链接预测。

2.2 链接预测的算法介绍

由于目前大多数社会网络都具有稀疏性的特点，存在链接节点数量与不存在链接节点数量之间的差距很大，如果把链接问题称为分类问题的话，在预测的过程中将会遇到高度不平衡的问题。因此，链接预测的重点是如何解决链接预测中不平衡的问题以便提高链接的准确性。

目前链接预测的主要方法有利用节点本身属性、拓扑结构以及路径等进行相似性的链接预测；采用节点拓扑结构和节点属性作为属性集合进行监督学习的链接预测；利用网络深层次结构最大似然估计的链接预测；采用参数调优方式构建概率模型的链接预测。由于篇幅有限，本文重点介绍基于邻接点相似性和基于路径相似性的链接预测方法。

（1）基于邻接点相似性的链接预测方法

相似性实质上是衡量网络中两个节点的接近程度，相似性链接预测的基本前提是：两个节点的相似性程度越高，那么两者产生链接的可能性越大。基于邻接点的相似性是指通过衡量两个节点的邻居节点或者邻居节点的局部结构密度是否具有一定的关联度，从而预测两个节点的链接概率大小。

1）共同邻居法

共同邻居法是基于两个节点的局部结构的相似性定义方法，该算法的假设前提是：如果两个节点的公共邻居越多，那么该两个节点的相似性越高，那么其之间存在的链接可能性越高[6]。

score（x， y）=|τ（x）∩τ（y）| （1）

其中，τ（x）和τ（y）分别表示与节点x和节点y链接的节点集合元素的个数，也就是节点x和节点y拥有共同邻居的数量。

2）Adamic-Adar法

该算法最先用于计算两个网页的相似性，不仅利用两个节点的共同邻居的数量，同时还利用共同邻居节点自身的重要性。该重要性是采用共同邻居节点度数的倒数来衡量。因此，节点之间的相似性的计算公式为：

score（x， y）= （2）

τ（z）表示节点x和节点y共同邻居的度数，通过共同邻居度数的倒数来衡量节点x与节点y之间链接的可能性。

3）优先链接法

优先链接算法的思想是：节点之间存在链接的可能性与自身节点度数成正比，如果网络中每次引入一个新的节点与一条边，那么网络会按照优先的机制从网络中选取度数较大的节点实现节点之间的链接，因此度数越大的节点，其被链接的可能性越大。其公式为：

score（x， y）=|τ（x）|×|τ（y）| （3）

4）資源分配法

在社会网络中，节点的关系体现的是利益的集中，而资源是指在节点与节点之间、社团与社团之间为了达到某种目的而传递的信息量，或者理解为节点之间为了维持现有的网络结构和拓扑关系所投入的精力。

资源强度就是指节点之间为了维持现有的网络结构和拓扑关系所投入的精力占比。

资源分配是对不存在链接的两个节点x和y，从节点x传到节点y的资源需要以它们的共同邻居为介质，并且资源传递过程中会产生平均分配或者不平均分配。因此，节点x和y的相似性可以定义为节点y从x获得的资源数量。资源数量越多，说明两节点的相似性越大[5]。在现实网络中，资源传递是不对称的，那么从x的角度看y的重要性，也就是y获得的资源数的公式为：

score（x， y）= （4）

（2）基于路径相似性的链接预测方法

1）最短距离法

该算法的思想是：如果两个没有链接节点之间的距离越近，那么节点之间存在的链接可能性越大[7]。

score（x， y）=length（short（x， y）） （5）

其中，length表示路径长度，shorts表示最短路径。

2）Katz算法

该算法考虑网络所有的路径，通过考虑不同路径对节点相似性的影响程度不同，并使用参数β来衡量不同长度的路径对链接预测的影响。

score（x， y）=（βl×|Paths（x， y， l）|） （6）

其中，Paths（x， y， l）表示节点x和节点y之间所有长度为l的路径集合[5]，β为路径衰减系数，表示随着路径长度的增长，相似性的贡献就减少。

上面各种算法都是为了解决节点x和节点y之间存在隐含链接的可能性这个问题。而这隐含链接形成的机制往往是复杂的，它需要充分考虑与节点相连的节点的拓扑结构，还要考虑节点y之间的共同邻居数量。因此，本文提出了一种基于邻域“结构洞”的网络资源分配链接预测方法，该方法不仅考虑共同邻居的链接关联关系，还结合节点自身拓扑结构对资源传播的影响程度。

3 基于改进资源分配的链接预测算法

3.1 “结构洞”理论

“结构洞”的思想是：由于节点之间没有链接关系，因此需要一个中间节点“Ego”充当中间人的角色，以便信息能够在节点之间进行传播。Burt首先提出网络约束系数来衡量网络节点形成结构洞所受到的约束[9]。一旦结构洞存在，那么结构洞两边的“中间人”可以带来累加而非叠加的网络收益。如图1可知，A和B存在结构洞，中间人E充当A和B之间的信息传播的角色，所以节点A和节点B为了维持目前的网络拓扑结构，所投入精力的比例会比其他邻居节点大。

3.2 基于“结构洞”的资源分配算法

“结构洞”认为，节点的关系可视为节点为了维持邻居关系或者网络拓扑结构的关系所投入精力的占比。从图2可知，i作为社会网络中链接数量最多的节点，根据约束系数理论，Ci表示节点i对邻居节点所投入的精力占比的总和，而CiA表示节点i对节点A所投入的精力占比。i的邻居节点为Г（i）={A， B， C， D， E， F， L， M}，pij表示节点i为维持节点j的邻居关系所投入的精力占总精力的占比，piq和pqj分别是指节点i和节点j与共同邻居q维持关系投入的精力占总精力的占比。同理：

Ci=CiA+CiB+CiC+CiD+CiE+CiF+CiL+CiM （7）

（8）

（9）

那么，CiA=（1/8+1/8×1/3+1/8×1/4+1/8×1/4）2，同理可求得CiB、CiC、…。可见Cij越大，i对节点j投入的精力占比越大。

但是，基于“结构洞”约束系数的方法仅仅考虑邻居节点对信息传播的影响，并没有考虑到邻居节点的拓扑结构会影响核心节点对邻居节点信息传播的强度。根据上面的约束系数的计算方式，CiE=CiF=（1/8+1/8×

1/3+1/8×1/4）2，而CFG=CEK=（1/4+1/4×1/3）2，那么CiG=CiF×CFG=CiK=CiE×CEK。显然，由于与G的邻居以及邻居的拓扑结构更加复杂，因此，核心节点i为了维持当前网络的结构必将会对G付出更多的“精力”，也就是分配更多的资源给G。

同理，本文采用传统的方法，如传统的资源分配、共同邻居、Adamic-Adar法、最短距离方式、Katz算法衡量节点之间的链接预测来说明问题。

资源分配法score（i， G）=score（i， K）=1/8×（1/4+

1/3）=7/96；

共同邻居法score（i， G）=score（i， K）=2；

Adamic-Adar法score（i， G）=score（i， K）=1/lg4+1/lg3；

最短距离法score（i， G）=score（i， K）=2；

Katz算法score（i， G）=score（i， K）=4×β2+9×β3+16×β4。

很明显，由于G具有更好“关系”，因此，i在资源分配的过程中，肯定会分配更多的资源给G，以期与G产生链接关系。那么，i在资源传递过程中，传递给F的资源肯定比E的资源多，所以根据传统的相似性链接算法（共同邻居的数量、共同邻居的度数、节点之间的路径长度）很难区分图2链接预测的区别。如果以传统方法进行链接预测，则无法识别复杂网络节点的链接关系的差异。本文参考文献[8]的改进约束系数衡量核心节点把资源传递到不同节点的强度。通过“邻域”结构洞约束系数来体现资源分配不均衡的问题。

3.3 基于改进资源分配的链接预测算法

传统的约束系数僅考虑了自身与最近邻节点之间的关系，没有充分考虑邻居节点的拓扑结构，也就是第二近邻、第三近邻等节点的关系。如果不考虑拓扑结构，那么就会面临上面提到的问题，无法真实反映资源分配不均衡的问题，也就无法反映节点之间资源传递的关系。因此，需要改进结构洞的约束系数，以便更精确衡量节点在复杂网络中的地位。

设无向网络G=（V， E），其中V={v1， v2， …， vn}是网络中节点的集合，节点i的度可以表示为：

（10）

其中，αij=

那么，节点i的邻接度被定义为：

（11）

那么节点i维持与节点j邻居关系所投入的精力占比为：

（12）

其中，Q（j）是节点j的邻接度，Q（q）是节点i的邻居节点的邻接度。

节点i与邻居节点之间的关系仍用公式表示，那么，根据网络结构，τ（i）为i的邻居集合在新的约束系数定义下，i向E传递的资源强度为：

CiE=（piE+piA×pAE+piM×pME）2

=

=0.0447。

i向L传递的资源强度为：

CiL=（piL+piF+pFL）2=

=0.0335。

i向F传递的资源强度为：

CiF=（piF+piA×pAF+piL×pLF）2

=

=0.0645。

i向M传递的资源强度为：

CiM=（piM+piE×pEM）2=

=0.0196。

同理，F向G传递的资源强度为：

CFG=（pFG+pFL+pLG）2=

=0.0356。

L向G传递的资源强度为：

CLG=（pLG+pLF+pFG）2=

=0.0575。

E向K传递的资源强度为：

CEK=（pEK+pEM+pMK）2=

=0.0199。

M向K传递的资源强度为：

CMK=（pMK+pME+pEK）2=

=0.0343。

那么，根据资源分配的链接预测算法为，信息源节点i通过共同邻居节点传递资源，再通过邻居节点传播到节点G。

score（i，G）=CiF×CFG+CiL×CLG=0.0643×0.0356+

0.0335×0.0575=0.00421。

信息源节点i通过共同邻居节点传递资源，再通过邻居节点传播到节点K。

score（i，K）=CiE×CEK+CiM×CMK=0.0447×0.0199+

0.0196×0.0343=0.0016。

可见，虽然i与G的共同邻居数量、路径长度以及共同邻居度数和i与K相同，但是i传递的资源数量却有很大的区别。改进后的资源分配算法更能体现节点在传播资源的过程中会受到节点本身拓扑结构以及共同邻居的拓扑结构的影响。上述公式的共同邻居只有一个，如果节点之间有多个共同邻居，可采取累加的方式评价节点链接的可能性。

4 基于改进资源分配的链接预测的应用

4.1 数据获取

移动用户在发生移动业务的过程中，运营商会记录用户的各种业务信息，包括发生业务的用户ID、开始时间、结束时间、业务类型、接收ID等。

本文提取某运营商5万用户3个月的业务量数据，并按照一定的规则进行预处理，形成满足本文数据分析的表格，如表1所示：

4.2 结合用户间每月发生业务频次剔除无效数据

本文結合用户间每月发生业务的频次剔除无效数据，考虑到本文的重点是识别用户之间的链接关系。基于现实数据分析的结果，本文设置用户间每个月的用户发生业务的频次为20，然后把联系大于20次的用户关系看成有效链接。

4.3 基于改进资源分配的链接预测模型的建立

通过剔除无效数据后按照日期分为两部分，前45天作为训练集，后45天作为测试集。参考实验结果，设置改进前的资源分配的链接预测score的阈值为0.055；设置改进后的资源分配的链接预测score的阈值为0.000 63。然后根据用户的改进资源分配链接模型对训练集进行打分，得到一系列用户间的链接预测值，选择链接预测值大于阈值作为链接的候选集合。然后采用改进前的资源分配的链接预测模型和改进后的资源分配的链接预测模型进行对比。最后把候选集合与测试集合的结果进行对比，得到的正确率如图3所示。

4.4 实验结果及分析

由图3可知，不考虑邻域“结构洞”的方法在实现节点之间的链接预测的准确率比考虑邻域“结构洞”的方法低，因此，结合邻域“结构洞”的链接预测能够在一定程度上提升网络链接预测的准确度。

5 结束语

本文基于真实的移动用户社交网络提出了节点的链接预测模型。首先基于用户联系的频次剔除无效数据，构建移动用户社交网络；然后再结合邻域“结构洞”理论在描述两个节点具有相同共同邻居数量、相同共同邻居度数、相同的路径长度在链接预测上的区别。该方法能够从本质上描述社交网络中节点在传播资源的过程中会受到节点本身度数、拓扑结构以及共同邻居的拓扑结构、共同邻居之间的关系的影响，从而能够较好地实现节点之间的链接预测。实验证明，考虑节点本身拓扑结构以及共同邻居的拓扑结构的影响与传统的算法相比具有较高的准确率。

参考文献：

[1] D Liben-Nowell， J K leinberg. The Link Prediction Problem for Social Networks[J]. Science Technology， 2007，58（7）： 1019-1031.

[2] 郭景峰，代军丽，马鑫，等. 针对通信社会网络的时间序列链接预测算法[J]. 计算机科学与探索， 2010，4（6）： 552-559.

[3] 伍杰华. 基于划分社区和差分共邻节点贡献的链路预测[J]. 计算机应用研究， 2013，30（10）： 2954-2957.

[4] 张秋明. 基于节点相似性的手机通信网络链路预测[J]. 计算机工程， 2015，41（7）： 149-152.

[5] 李淑玲. 基于相似性的链接预测方法研究[D]. 哈尔滨： 哈尔滨工程大学， 2012.

[6] Newman M E J. The structure and function of complex networks[J]. SIAM REVIEW， 2003，45（2）： 167-256.

[7] M Fredman， R Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms[J]. Journal of the ACM， 1987，34（12）： 596-615.

[8] 沈文明，杜翠凤. 基于“邻域”结构洞的社团发现算法[J]. 移动通信， 2017，41（14）： 36-40.

[9] 苏晓萍，宋玉蓉. 利用邻域“结构洞”寻找社会网络中最具影响力节点[J]. 物理学报， 2015，64（2）： 1-11.