基于集成学习的动态链接预测方法

安琛，陈阳

南京邮电大学计算机学院，南京210046

基于集成学习的动态链接预测方法

安琛，陈阳

南京邮电大学计算机学院，南京210046

CNKI网络出版：2017-03-04,http://kns.cnki.net/kcms/detail/11.2127.TP.20170304.1727.002.html

1 引言

随着Web2.0的发展以及用户生成内容（User Generated Content）模式的推广，网络数据正以空前的速度不断累积。为了从海量的动态数据中发现有价值的信息，社会网络分析（Social Network Analysis）这一新兴的研究领域应运而生。作为社会网络分析的关键问题，链接预测近些年来得到越来越多研究者的关注。链接预测根据社会网络现有的结构，预测隐含的链接或是将来可能产生的链接。已有的链接预测方法主要分成三类：（1）基于节点相似度的方法；（2）基于网络拓扑结构特征的方法；（3）基于概率模型的方法[1]。其中，基于网络拓扑结构特征方法的使用较为广泛，而其他两种方法在网络节点数目较多时会产生很大的时间开销[2]。链接预测的应用领域非常广泛。例如，利用链接预测方法，在线社交网站可以帮助用户发现自己的朋友；电子商务网站可以给用户推荐感兴趣的商品；医学研究者能够更好地认识蛋白质等复杂网络的结构[3]；而在安全领域，链接预测亦可实现对复杂超网络结构演化的建模和预测分析，在实际的舆情监控系统中有着重要作用[4]。

传统的链接预测方法主要分析网络当前的静态特征，忽略了网络在演变过程中可能隐含的额外的时间信息[5]。目前，已有一些研究者尝试引入网络结构随时间变化的信息，研究动态网络中的链接预测问题。在此背景下，本文提出了一种基于网络特征动态变化的链接预测方法。该方法挖掘网络结构特征的变化数据，为每一个结构的特征变化建立一个学习器，最后通过优化算法为各个学习器分配权值，得到最终集成的预测模型。

2 动态网络中的链接预测问题

链接预测问题通常被形式化为：给定一个社会网络G=(V,E)（其中，V是网络节点的集合，E是网络目前能观察到的边的集合），对于一个尚未形成链接的节点对＜u,v＞，预测其形成链接的概率。

传统的链接预测方法主要分析某一时刻的静态网络。例如，陈可佳等人[6]利用网络中的未标记数据帮助学习，提出并使用两种半监督范式进行链接预测；伍杰华[7]尝试引入“树状”结构来描述合著者网络中的链接关系，结合朴素贝叶斯分类器和节点相似度特征进行链接预测；张健沛和姜延良[8]提出了一种基于节点相似性的邻居关系权值预测算法。在国外的研究者中，Liben-Nowell和Kleinberg[9]通过研究arXiv合著者网络，发现了采用Jaccard、Adamic-Adar和Katz这些结构特征的链接预测方法性能远优于随机预测。然而，传统的链接预测方法忽视了社会网络在演化过程中产生的潜在信息，这些信息对于预测未来时刻的链接是有帮助的。

因此，动态链接预测问题得到了越来越多研究者的关注。张昱等人[10]基于节点在相近时间发布的内容相似性更大的假设，在博客数据集上提出了一个比传统方法更为有效的链接预测方法；Kumar等人[11]研究了Flickr和Yahoo!360的演化过程，根据社会网络中的三种结构（单独节点、孤立社区和巨大连通分支），提出了一个简单有效的社会网络演化模型。Huang和Lin[12]综合了静态结构特征和时间特征，提出了一个线性自回归模型。Tylenda等人[13]在动态网络中使用了时间特征和其他静态特征实现节点对的排序。Sharan和Neville[14]使用静态带权图来表示动态网络，再用关系贝叶斯分类器进行预测。Potgieter等人[15]研究了用于链接预测的时间度量方法。Da Silva Soares等人[16]计算网络结构特征的时间序列，并训练该数据得到分类器进行预测。

3 本文提出的方法

3.1 方法描述

本文在监督学习框架中对网络中节点对结构特征的动态变化进行建模，根据学得的模型预测网络下一时刻可能出现的链接。该方法命名为EnDLiP（Ensemble based Dynamic Link Prediction）。首先，根据时间轴得到网络的演化序列，选取若干描述节点对样本的结构特征；然后记录样本的每个结构特征在网络演化过程中的变化情况，并训练得到一个学习器；最后采用集成的方法，将每个学习器的预测结果加权得到最终的模型。

本文的集成学习框架采用Schapire提出的boosting方法，该算法采用加入输入扰动，在训练集样本上抽取不同特征，训练出多个弱分类器，之后通过集成得到预测性能更好的强分类器。在分类的过程中，每个样本都设置不同的权值，权值随着每次样本的分类结果及整体分类结果改变，若该样本分类正确，就降低其权值，否则，提高权值。将调整过后的样本作为下一轮的新样本继续迭代训练，最后进行融合。该模型的框架流程图如图1。

图1 EnDlip算法流程图

为了完整描述EnDLiP，需要引入下列符号。令一个社会网络G在时刻t的状态为Gt，该社会网络的演化序列为{G1,G2,…,Gt,…,GT}。＜αi＞表示训练集中的第i个节点对样本。label＜αi＞表示＜αi＞的标签信息（已连接的节点对标记为1，未连接的节点对标记为0）。{Fea1,Fea2,…,Feaj,…,FeaN}表示为样本选取的所有结构特征的集合，Feaj表示其中的第j个特征。Feaj＜αi＞t表示＜αi＞在t时刻的Feaj值。ΔFeaj＜αi＞t=Feaj＜αi＞t+1-Feaj＜αi＞t表示在相邻时间片段中Feaj的变化情况。{ΔFeaj＜αi＞1,…,ΔFeaj＜αi＞t}表示由ΔFeaj＜αi＞x组成的长度为t的序列，其中x的取值范围为[1,t]。为每个Feaj分别生成训练集TrainSet(Fj,label＜αi＞)。其中，Fj表示第i个样本的第j个特征变化值的演变序列，即对训练集中所有＜αi＞的训练得到分类器ClfFeaj。ClfFeaj＜αj＞表示ClfFeaj预测＜αi＞会形成链接的强度。令ϖ为权值向量，ϖ=(w1,w2,…,wj,…,wN)，其中的wj表示为分类器ClfFeaj分配的权值。

EnDLiP的伪代码描述如下：

3.2 补充说明

为了描述网络特征的动态变化ΔFeaj＜αi＞t，除了差分（Feaj＜αi＞t+1-Feaj＜αi＞t）外，还可以使用变化率((Feaj＜αi＞t+1-Feaj＜αi＞t)/Feaj＜αi＞t)。不过此时需要处理Feaj＜αi＞t值为0的情况（见实验部分）。下文中，代表用差分得到的序列，代表采用变化率得到的序列。

Feaj＜αi＞t的计算可不必从t=1开始。实际数据中，结构特征值往往从中间某个时刻才发生变化。因此，取一个长度为h（数值在实验中确定）的时间段[T-1-h,T-1]，在此区间上计算Feaj＜αi＞t的值。这在一定程度上反映了，网络在某一时刻的状态和之前h个时刻的状态更相关。

EnDLiP中h值和动态度量的确定方法为先令h=1，分别使用差分和变化率得到两个不同的训练集，训练得到分类器ClfFeaj|diff和分类器ClfFeaj|rate。根据测试集中的预测结果分别得到和，代表利用差分和变化率得到的ROC曲线下的面积，值越高，所对应的预测模型性能也就越好；随后对h依次加1得到h′，当时，令h′代替h，并根据和的大小决定选择差分还是变化率作为衡量h′时间段中网络动态变化的方法。计算变化率时，为了防止除数为0，先为每个特征值加1再进行计算。

为每个结构特征找到合适的h和动态度量方法后，可以得到一个分类器（本文实验中有4个特征，共得到4个分类器）。随后，使用最小二乘法优化从而得到权值向量̂。运用最小二乘法，可以让期望输出和真实输出间的均方误差最小，即：

要使得J(w)最小，需要满足正交条件：

4 实验结果与分析

4.1 数据集与特征选取

实验使用了arXiv网站上三个现实的合著者网络数据（nucl-th、hap-lat和hep-ex）。在合著者网络中，每个节点代表一个作者，如果两个作者有合作关系，则在两个节点间会形成一条边。nucl-th网络的起止时间为1993—2010年；hep-lat网络的起止时间为1993—2010年；hep-ex网络的起止时间为2002—2012年。

实验首先设定每个网络的演化序列。对nucl-th网络和hep-lat网络，按两年划分时间片段，得到网络演化序列{G1994,G1996,…,G2008,G2010}。对hep-ex网络，按一年划分时间片段，得到的网络演化序列{G2002,G2003,…,G2011,G2012}。

本文选择了在链接预测领域较为常用的网络结构特征：优先连接（PA）、共同邻居（CN）、Adamic Adar分数（AA）和Jaccard系数（JC）。计算方法如表1（其中，Γ(u)代表节点u的邻居集合，|Γ(u)|代表u的度）。

表1 结构特征描述

4.2 实验设置

为了便于比较，本文按Da Silva Soares等人的方法设置训练集和测试集。对于一个网络的演化序列{G1,G2,…,Gt,…,GT}：首先，找出所有从Gt-1到Gt时新形成链接的节点对，记为集合A。然后，找出Gt-1中所有满足如下条件的节点对＜u,v＞，记为集合B。要求：节点u和节点v距离为2跳，且u和v在之前的任意时刻都未形成链接。最后，得到集合C(C=A⋂B)和集合D(D=B-A)。将C作为测试集中的正例集合，从D中选取和正例数目相同的节点对作为测试集的反例集合，得到一个正、反例数目均等的测试集。选取训练集的方法和选取测试集的方法相同，只是训练集中的A表示从Gt-2时刻到Gt-1时刻新形成链接的节点对集合，而B表示是Gt-2中的距离为2跳的节点对集合。

为三个合著者网络选取训练集和测试集的样本数目如表2。

表2 各合著者网络训练集和测试集的数目

4.3 比较方法

为了验证EnDLiP的有效性，本文还实现了两种相关的比较方法。第一种为传统的静态预测方法，另一种是Da Silva Soares等人提出的方法。在静态预测方法中，只利用Gt-1中的信息为每一个结构特征进行训练并集成，其他配置与EnDLiP相同。第二个比较方法先对每一种结构特征计算其在网络演化过程中各个时刻的值，得到一个结构特征时间序列，然后采用简单指数平滑法（SES）和移动平均值（MA）来预测下一时刻的特征值。将所有结构特征的预测值作为一个混合特征向量，通过学习模型（如SVM）进行训练，得到链接预测结果。

4.4 实验结果与分析

表3～表5展示了在三个网络中每个结构特征所宜采用的度量方法、最佳训练时间段（h值），以及对应分类器的权重。图2是在三个网络中各方法的ROC曲线比较图。其中，EnDLiP是本文提出的方法，用实线表示。其余三条虚线分别代表Da Silva Soares等人方法中预测效果最好的两种模型（不同网络中的最优模型未必相同），以及静态的监督链接预测方法。

图2 网络中各方法的ROC曲线比较

表3 nucl-th网络中各结构特征的实验配置

表4 hep-lat网络中各结构特征的实验配置

表5 hep-ex网络各结构特征的实验配置

实验结果表明，考虑网络结构演变信息后，链接预测的性能确实有了很大的提高。例如，在hep-lat网络中，EnDLiP的AUC值比静态预测方法要高出8.4%，并且比Da Silva Soares等方法的最好结果还要高出13.7%。在三个网络中，h的取值都较小（2～4），这说明在预测时刻，只需考察之前一小段时间内网络结构的演变信息即可。

Da Silva Soares等的方法虽然考虑了网络的动态变化，但采用的预测模型较简单，且只对预测值进行训练，因此预测性能跟理想情况有一定的差距。相比之下，EnDLiP并没有引入新的预测值，而是利用了更多的网络演变信息进行训练，所以性能上能有所提高。

此外，从各分类器在集成时分配的权重也可以发现，虽然在每个网络中的权值略有差别，但总体上，结构特征CN和AA所占的权重要高于结构特征PA和JC所占的权重。这说明，结构特征CN和AA比PA和JC更适合描述网络结构的动态演变。

5 结束语

针对传统静态链接预测方法的局限，本文提出了一种动态的链接预测方法EnDLiP。该方法描述了网络特征的动态变化情况，通过集成学习的方法对动态信息建模，实现了链接预测的目的。实验表明，引入网络动态变化的信息，确实提高了链接预测的性能。此外，对于不同的网络结构特征，其适合的动态变化度量方法（差分或变化率）与之前关联时间片段数目（h值）均有所不同。此外，实验也表明了不同结构特征对网络动态变化的刻画能力也有所不同。

本文使用的集成方法还较为简单，未来将讨论其他先进集成方法的有效性。此外，也将尝试其他刻画网络动态变化的方法，并考察其刻画能力。

[1] Xie X，Li Y，Zhang Z.A joint link prediction method for social network[J].IFIP Advances in Information&Communication Technology，2015，503：56-64.

[2] Peng W，Baowen X U，Yurong W U.Link prediction in social networks：The state-of-the-art[J].Science China Information Sciences，2014，58（1）：1-38.

[3] Kaya B，Poyraz M.Age-series based link prediction in evolvingdiseasenetworks[J].ComputersinBiology&Medicine，2015，63（C）：1-10.

[4] 田儒雅，刘怡君，牛文元.舆论超网络的领袖引导模型[J].中国管理科学，2014，22（10）：136-141.

[5] Bliss C A，Frank M R.An evolutionary algorithm approach to link prediction in dynamic social networks[J].Journal of Computational Science，2013，5（5）：750-764.

[6] 陈可佳，韩京宇，郑正中.半监督学习在链接预测问题中的应用[J].计算机工程与应用，2012，48（33）：136-141.

[7] 伍杰华.基于树状朴素贝叶斯模型的社会网络关系预测[J].计算机应用，2013，33（11）：3134-3137.

[8] 张健沛，姜延良.一种基于节点相似性的链接预测算法[J].中国科技论文，2013，8（7）：659-662.

[9] Liben-Nowell D，Kleinberg J.The link-prediction problem for social networks[J].Journal of the American Society for Information Science and Technology，2007，58（7）：1019-1031.

[10] 张昱，张恩德，李封.基于时间信息的社会网络链接预测研究[J].计算机与数字工程，2012，40（11）：50-51.

[11] Kumar R，Novak J，Raghavan P.Structure and evolution of blogspace[J].Communications of the ACM，2004，47（12）：35-39.

[12] Huang Z，Lin D K J.The time-series link prediction problem with applications in communication surveillance[J].Informs Journal on Computing，2009，21（2）：286-303.

[13] Tylenda T，Angelova R，Bedathur S.Towards time-aware link prediction in evolving social networks[C]//Proceedings of Workshop on Social Network Mining&Analysis Snakdd，2009：1-10.

[14] Sharan U，Neville J.Exploiting time-varying relationships in statistical relational models[C]//Webkdd and，Sna-Kdd 2007 Workshop on Web Mining and Social Network Analysis，2007：9-15.

[15] Potgieter A，April K A，Cooke R J E，et al.Temporality in link prediction：Understanding social complexity[J].Emergence Complexity&Organization，2007（11）：2007.

[16] Da Silva Soares P R，Bastos C P R.Time series based link prediction[C]//International Joint Conference on Neural Networks，2012：1-7.

AN Chen,CHEN Yang.Dynamic link prediction method based on ensemble learning.Computer Engineering and Applications,2018,54（6）：110-114.

AN Chen,CHEN Yang

College of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210046,China

Link prediction is a crucial problem in social network analysis.Most of the traditional link prediction methods find the missing links or predict the future links merely based on astatic structure of a network,ignoring its dynamics.In order to utilize the dynamic information of the network better and achieve a more preferable result,in this paper,a method with consideration of the network evolution is proposed.A machine learning technique is used to model the change of the structural characteristics in networks.A classifier is trained for each structural feature and a final ensemble result is obtained by weighting all the classifiers.The experimental results in three real collaboration networks show that the proposed method outperforms the traditional static link prediction method and a related dynamic link prediction method,which demonstrates that the results of link prediction are much facilitated with the dynamic information of the network.Moreover,the experimental result also shows that different structural characteristics have different abilities to describe the network dynamics.

link prediction;machine learning;dynamic network;social network analysis;ensemble learning;supervised learning

链接预测是社会网络分析领域的关键问题。传统的链接预测方法大多针对社会网络的静态结构预测隐含的链接或者将来可能产生的链接，而忽视了网络在动态演变过程中的潜在信息。为了能更好地利用网络演变的动态信息，从而取得更好的链接预测效果，提出了一种基于网络结构演变规律的链接预测方法。该方法使用机器学习技术对网络结构特征的动态变化信息进行训练，学习每种结构特征的变化并得到一个分类器，为每个分类器加权得到最终集成的结果。在三个现实的合著者网络数据集上的实验结果表明，该方法的性能要高于静态链接预测方法和一个相关的动态链接预测方法。这说明，网络结构演变信息有助于提高链接预测效果。此外，实验还表明，不同的结构特征对网络动态变化的刻画能力也有所差别。

链接预测；机器学习；动态网络；社会网络分析；集成学习；监督学习

2016-10-17

2016-12-04

1002-8331（2018）06-0110-05

A

TP391

10.3778/j.issn.1002-8331.1610-0187

国家自然科学基金青年基金（No.61100135，No.61302158）。

安琛（1991—），男，硕士研究生，主要研究方向：机器学习、数据挖掘，E-mail：chenan0120@163.com。