赵宇红 张晓炜

(内蒙古科技大学信息工程学院 内蒙古 包头 014010)

0 引 言

链路预测[1]作为复杂网络的核心内容之一，可以从网络数据中挖掘有用的链路信息，即基于已存在的网络拓扑信息、节点属性和历史信息，预测未来尚未建立连接关系的节点对之间连接的可能性[2]。传统的链路预测方法主要是建立在静态网络[3]的基础上的，具有代表性的常用的方法有Common Neighbor(CN)[4]、Adamic-Adar(AA)[5]和Preferential Attachment Index(PA)[6]等，这些方法虽然能在静态网络中取到较好结果，但却忽略了网络的动态性特点。为了解决这一问题，动态网络的链路预测被提出，考虑了时间信息，可以根据网络历史时刻的拓扑结构来预测出该网络在未来的链接结构。

对未来可能产生的边进行预测的核心是对网络演化规律的把握，然而，现有的大多数动态链路预测方法都是直接在网络宏观的全局拓扑结构进行分析，并没有注意到网络中的微观结构对网络演化是如何影响的。模体(motif)是一种非常重要的网络微观结构[7]，研究发现它的演化规律可以在动态网络分析中起到关键作用。文献[8]从网络的微观演化为切入点，通过分析网络中频繁出现的模式的演变情况来进行链路预测。文献[9]首次度量模体的转换概率并定义其转换概率矩阵进行链路预测。文献[10]改进了文献[9]的方法，换用三阶张量分解的方法计算模体转换概率矩阵，同时考虑模体结构指标。

但这些方法都没有对动态网络下时间窗口的准确选取做过多的探究，并且文献[10]的方法是针对无向网络的研究，而现实中的大多网络数据是有向的，同时研究中也没有考虑网络中重复连边的问题。针对这些问题，提出基于模体演化的多因子动态链路预测方法(MFME)。该方法在动态有向网络下从合适大小的时间窗口的划分入手，利用模体演化矩阵来记录网络中的模体演化情况，引入整合移动平均自回归模型有效地预测模体的演化概率。最后，通过结合模体演化影响因子来计算节点间产生连边分数来进行链路预测。通过真实数据集下与其他方法的比较，验证了本文方法能够达到更好的链路预测效果。

1 相关介绍

1.1 动态链路预测

假设存在一个有向网络G=(V,E)，V={v1,v2,…,vN}是该网络的节点集合，E={e1,e2,…,eN}是网络中的节点间构成的带权有向边集合。对于一个动态有向网络G，给出它的时间窗口序列1,2,…,t，在t个连续的时间窗口下G=(g1,g2,…,gt),其中gt=(vt,et)，vt表示t时间窗口下网络的节点集合，et表示t时间窗口下网络中的vt个节点之间形成的带权有向边集合[11]。为了达到研究目的，本文根据已知动态网络G中g1到gt的演化情况，设计一种链路预测方法，预测时间窗口gt+1中的任意有序节点间产生连边的分数值，该分数值越大，则表示两节点之间产生链路的概率越高。

1.2 模体及其演化理论

模体最早是在生物学的蛋白质网络里表示最基本的功能模块，引入到复杂网络中便可以表示为网络的基本子结构，其中由三个节点构成的结构为最基本的模体结构。有向网络内，共有15种三元模体[12]结构，如图1所示。图中标注的模体编号与结构一一对应，该编号将在本文中应用，且下文所述模体均为三元类型。

图1 15种三元模体结构

网络中不同模体间的演化规律的作用非常重要，本文正是利用各时序状态下不同模体间的演化规律来对动态网络的链路关系分析和预测。

定义1动态有向网络中，任意由三个点组成的节点集可以称为一个模体m。m为图1中的15种模体类型之一，用mtfi来表示图1中第i类模体。动态网络的变化可以看作是大量模体间的演化过程，若在任意两个相邻的时间窗口下，某三个节点组成的模体由模体类型i转化成模体类型j，那么这个过程可表示为：

mtfi→mtfj1≤i,j≤15

(1)

网络中各模体的演化即衍生了动态网络的演化。本文用15×15的模体演化矩阵MEM(Motif Evolution Matrix)来表示动态网络相邻时间窗口上各模体间的演化规律。矩阵的行标分别对应前一时间窗口的15种不同类型的模体，而列标分别对应后一时间窗口的15种模体。

两相邻时间窗口对应矩阵中的每个元素都表示行标对应的模体转换到列标对应的模体的概率。将15×15种模体之间的历史转移概率看作特定的时间序列，使用MEMt,i,j表示在t时刻mtfi转换为mtfj的概率。

在时间窗口1～t之间，任意两类模体mtfi、mtfj之间均存在演化概率时间序列MEM1,i,j,MEM2,i,j,…,MEMt-1,i,j。通过上述的演化序列，如果MEMt,i,j的值能被准确预测，则会有利于动态链路预测的研究。

1.3 整合移动平均自回归模型

自回归移动平均模型(Autoregressive Moving Average Model)是一种时间序列预测方法。该模型的基本原理是：预测指标随时间形成的数据序列被视为随机序列，这些随机变量的相关性反映了原始数据在时间上的延续性。一方面，随机变量受某些因素的影响，另一方面，也有其自身的变化规律[13]。若一时间序列Yt={Y1,Y2,…,YT}满足自回归移动平均模型，可表示为：

Φ(B)▽dYt=Θ(B)εt

(2)

式中：Φ(B)=1-φ1B-…-φpBP,Bp为延迟算子，与Yt作用后得到Yt-p，φp为自回归系数；▽d=(1-B)d，d为差分次数；Θ(B)=1-θ1B-…-θqBq，θq为移动平滑系数；εt为零均值白噪声序列。式(2)可简写为：

(3)

将模型中心化后，可将公式简写为：

Yt=φ0+φ1Yt-1+…+φpYt-p+εt+θ1εt-1-…-θqεt-q

(4)

整合移动平均自回归模型是自回归移动平均模型的改进，它不仅有自回归移动平均模型的优点，而且还针对性地加入了非稳定序列的预测，并且它完成预测不需要借助其他外生变量。对于非数值型时间序列的处理，本文采用面向属性的预测思路，即预测每种不同类型属性在不同取值上的数量分布，可将非数值型预测转化为数值型预测。预测序列的稳定性对模型预测结果影响很大，数据稳定表示数据序列是没有趋势，没有周期性的；若数据是不稳定的，则无法捕捉到规律，难以预测。

1.4 模体演化影响因子

1.4.1链接权重

现实中的动态网络往往存在重复的连边，把任意两节点关系的强度用其链接重复次数表示。假如模体内的某条边重复出现，则认为这条边代表的关系也就越强。若网络中两节点出现的重复连边e1,e2,…,en，用最初出现的边e1作为这条链接的代表，把出现的次数作为e1的权重w，用w表示这两点间联系的强弱程度，链接关系的强弱将对连边的演化有着重要的影响。

1.4.2闭包三原组

三元闭包是一种非常直观和自然关系的描述。例如，如果两个人B和C存在一个共同朋友A，则这两个人在未来成为朋友的可能性就会提高。共同的朋友A直接导致他们彼此见面的几率增加，并且关系链形成的过程中，B和C都和A是朋友，这为他们提供了陌生人所缺乏的基本信任[14]。这种三节点之间的关联形成三元闭包，而闭包也呈现不同的结构，且不同结构的闭包也会影响链接的演化结果。

1.5 实验数据集

本文使用两个真实的数据集进行链路预测实验。安然(Enron)网络[15]是2000年至2002年间150位安然员工之间发送的60多万封电子邮件的公开数据库，该数据集网络的连边中带有时间戳注释；Facebook-wosn-wall[16]是某一用户发给其他用户的一小部分帖子的定向网络，网络中的节点是Facebook用户，每个有向边代表一个帖子，并且连边具有时间戳。这两个真实网络中的节点关系都是有向的，并且这些节点关系都包含时间信息，因此都是动态的有向网络。数据具体参数如表1所示。

表1 实验数据集参数表

2 算法思路与设计

本文的研究重点是对动态链路预测的多影响因子的获取，主要分为两部分，一是如何对动态网络进行合适大小的时间窗口划分；二是怎样考虑模体演化过程中链接权重和闭包三元组对连边形成的影响。首先，确定两个动态网络中以时间窗口为共同变量且呈现趋势相反的函数，利用两函数的差值最小化来找到合适的窗口大小；其次，利用预测模型得到模体演化预测矩阵MEPM(Motif Evolution Prediction Matrix)后，结合两个模体演化影响因子计算出相应的模体影响指数，综合预测矩阵得出任意两节点的产生连边的概率。

2.1 合适的时间窗口划分

对于动态网络预测研究，时间窗口的划分对其预测结果有较大的影响，因此选取适当的时间窗口划分方法非常必要。本文采用SOTS(Segment of Time Series)方法对动态网络划分时间窗口。

在给定窗口大小为ω和相应的网络g(ω)的情况下，f代表动态网络时间快照的不同统计信息，Sω表示其对应的时间序列信息：

Sω(g)=[f(G1),f(G2),…,f(Gt),…,f(GT)]

(5)

为了保障时间窗口中保留较完善的网络快照信息，采用如下方法：

(1) 方差：V(Sω)表示Sω的方差，可以看作是一种时间序列Sω的噪声度量方法，公式如下：

(6)

(7)

式中：ε(Sω)为Sω的均值。随着时间窗口ω的变化，方差的值也会发生改变。如果方差值较大的话，说明Sω随着时间发生了剧烈的变化，这样会产生信息冗余，产生很多噪声；反之，会使得Sω过于平滑，丢失很多有用信息。

(2) 时序压缩比：d表示Sω(g)的序列长度，cd表示利用数据压缩算法压缩后的Sω(g)的序列长度，则Sω(g)的时序压缩比R(Sω)表示如下：

(8)

R(Sω)是一种对Sω的信息编码方式，一个较小的时序压缩比值表示Sω的信息中存在大量的噪声；反之，则表示混乱度低，信息含量多。

由上边的描述可以看出，方差和压缩比随着窗口大小ω的变化呈现着相反的趋势，方差和时序压缩比的最小差值也就是最优的时间窗口划分值。SOTS时间窗口划分方法步骤如算法1所示。

算法1SOTS时间窗口划分方法

输入:1.带有时间标签的有向网络

2.该网络下窗口划分的最大可能值ωmax≥1

输出:合适的窗口大小ω

1 forω=1 toωmaxdo

2 根据图序列计算时间序列Sω:[f(G1),f(G2),…,f(Gt),…,f(GT)]；

3 计算对应窗口下的方差V(Sω)和时序压缩比R(Sω)；

4 ifV(Sω)-R(Sω)=0 then

5 输出ω；

6 end if

7 end for

2.2 构建模体演化概率预测矩阵

以优化的时间窗口对动态网络进行等值窗口切分，对历史演化信息统计，则可以得到相邻时间窗口下不同模体类型的转换概率。在两个数据集下对所获取的模体演化信息进行分析，图2和图3分别是Enron数据集和Facebook数据集所截取的前15个时间窗口的不同模体下的演化情况，可以看出模体在演化过程中会出现一定的趋势性和周期性，即演化过程中的不稳定性。例如，图2中008号模体到011号模体的演化过程，图3中005号模体到006号模体的演化过程等，这样的不稳定性对预测模型的训练和预测结果都会有不好的影响。

图2 Enron数据集下不同模体间演化概率

图3 Facebook数据集下不同模体间演化概率

本文基于TTM prediction[9]算法将每两个相邻时间窗口下的模体演化概率分别记录到对应的模体演化矩阵MEM当中，最后利用整合移动平均自回归的时序预测模型计算两个相邻时间窗口下的模体间演化概率并得到预测矩阵。

在划分好的相邻时间窗口下，若某两个类型模特间的演化概率的时间序列为MEM1,i,j,MEM2,i,j,…,MEMt,i,j，表示为Yt=(y1,y2，…,yt)，使用整合移动平均自回归模型可表示为式(2)的形式。

(1) 用单位根检验法来判断数据的平稳性。当数据不平稳时，对其进行差分处理，差分阶数的选取从1逐渐增加，直至满足校验。检验方法如下：

假设序列经过d阶差分后平稳，可以设：

(9)

(10)

由式(10)知，模型可以得出p+q个根。当d≠0时，可判断序列在模型下不平稳。

(2) 确定模型最佳的p、q值。根据所选数据的自相关函数ACF和偏自相关函数PACF的拖尾性和截尾性来确定p和q。本文采用AIC标准，即利用使AIC达到最小值的自回归移动平均模型进行拟合。AIC的标准函数如下：

AIC=nlnL+2(p+q+1)

(11)

式中：L为似然函数。选择使AIC达到最小的p、q值为最佳p、q值。

(3) 估计预测模型中参数的值。本文选用最小二乘法来估计参数值。方法如下：

(12)

θ2εt-2-…-θqεt-q

(13)

式中：φi为自回归系数；θi为移动平均系数；εi为零均值白噪声序列。则残差项为：

(14)

至此，确立适合本文的模型及其参数。利用得到的模型预测出T-1到T时间窗口下任意两类模体间的演化概率，从而得到预测矩阵MEPM。整个过程可用图4表示。

图4 模体演化矩阵及预测矩阵构建过程

每相邻的两个时间窗口下的模体演化信息用一个MEM记录，并把前T-1个MEM作为历史序列，用整合移动平均自回归模型学习并预测出最后的MEPM。

2.3 基于模体演化的多因子链路预测方法

网络中的一个节点对往往可能属于多个模体之中。如图5所示，一个简单的有向网络中存在节点对(vm,vn),该节点对可以属于模体(vm,vn,v2)、(vm,vn,v5),也可以属于(vm,vn,v4)等。因此，当得到模体预测矩阵时，并不能完全直接由其得出某节点对之间的连边概率。但是，每个包含该节点对的模体的状态都为连边可能性的预测提供了参考，并且对该节点对影响更大的模体对预测结果往往也起到积极的作用。

图5 简单动态有向网络结构示例图

2.3.1模体演化影响因子

影响模体的演化主要集中表现为两个方面，一方面是单个模体中各节点间的连边次数，连接频率越高，则说明该模体的影响度越大；另一方面是模体的闭合次数，在模体演化的过程中，如果某一模体形成的闭合次数越多，说明该模体内节点间关系越紧密，对节点对连边的预测也越重要。此外，针对有向网络而言模体的闭合类型也不一样，比如模体(vm,vn,v2)是单层闭合，而模体(vm,vn,v5)则存在一条双层闭合。

基于上述分析，对于任一个模体(vm,vn,vj)，本文定义模体影响指数来综合描述模体演化影响因子即连边次数和闭包闭合次数对链路预测的影响程度：

ei∈link(vm,vn,vj)

(15)

式中：I(vm,vn,vj)表示该模体的模体影响指数；Wvi表示模体内任两节点间的连边次数；link(vm,vn,vj)表示当前模体内所有存在的连边；synt表示t时刻模体是否闭合，闭合为1，不闭合为0；δ表示连边次数和闭合次数的影响占比。对于一个有向网的模体闭合状态，考虑θ为模体闭合程度，取值如式(16)所示。

(16)

根据得到的MEPM和模体影响指数，可以计算出预测的T时刻中任意节点对(vm,vn)间的连边概率：

vj∈neig(vm,vn)

(17)

式中：mtfT-1为T-1时刻(vm,vn,vj)的模体名；mtfT为T时刻(vm,vn,vj)的模体名；neig(vm,vn)为节点vm、vn的邻居节点集。

2.3.2算法描述

在上述分析基础上，本文提出基于模体演化的多因子链路预测方法MFME，算法如下：

算法2基于模体演化的多因子链路预测方法

输入:1到T时刻的时间窗口

输出:T时刻各节点对的连边概率

1 初始化: 计算1～T-1相邻时间窗口的模体演化矩阵；

2 计算T-1到T时间窗口的模体演化预测矩阵MEPM；

3 for each(vm,vn) do

4 for each(vm,vn)∈(vm,vn,vj) ；

//vj∈neig(vm,vn)

5 用式(15)计算模体影响指数；

6 end

7 用式(17)计算节点对的连边概率；

8 end

3 实验与结果分析

3.1 实验设计

本文研究采用的实验环境是AMD Ryzen 5 2600X，16 GB内存，系统采用Windows 10，实验程序采用MATLAB编写，版本为R2019a。

本文所提的MFME方法将与TTM[9]、TCM[10]、TS[18]进行对比实验。其中，TTM是最先利用模体的转换概率信息进行链路预测的方法，并得到了较好结果；TCM是在TTM的基础上用三阶张量分解的方法计算模体转换概率矩阵，效果优于TTM方法；而TS方法是一种经典的动态链路预测方法。AUC[19]可以从整体上衡量结果的精确度，对比实验采用AUC指标对预测结果的准确性进行验证。

3.2 实验结果及分析

下面先利用SOTS算法对选定的两个真实数据集进行时间窗口的划分。图6为Enron数据集在SOTS算法下的方差和时序压缩比的计算结果，可以看到随着时间窗口ω的增大，方差是总体呈下降趋势的；反之时序压缩比呈持续增长的趋势，并且很明显可以看到在ω=6附近时两者的值出现交点，因此我们将选取ω=6为Enron数据集的时间窗口划分大小。

图6 SOTS算法在Enron下的划分情况

由于Facebook-wosn-wall数据集的网络规模和时间跨度都更大，因此在利用SOTS算法进行划分的时候，所呈现的曲线也有很大的不同。如图7所示，该数据集下的方差曲线呈快速下降的趋势，而时序压缩比曲线在ω=20附近才开始有明显的增长趋势，并且两条曲线在ω=30附近出现交点，因此，本文将选取ω=30为Facebook-wosn-wall数据集的时间窗口划分大小。

图7 SOTS算法在Facebook-wosn-wall下的划分情况

为了验证算法的有效性并能从中体现出时间窗口对实验结果产生的影响，分别对所用的两个数据集进行了多组实验。图8是Enron数据集在不同时间窗口下各算法的AUC值曲线，可以看出各算法在不同时间窗口下的AUC值有着较为明显的变化趋势，并且时间窗口在5～8的范围里各方法的AUC值都达到了最大值；图9是Facebook-wosn-wall数据集在不同时间窗口下各算法的AUC值变化曲线，可以看到曲线随着窗口大小的增长同样有明显的变化趋势，而且在窗口大小为28～35的区间里四种方法的AUC值也是达到一个最高的水平。

图8 Enron数据集不同时间窗口下各算法AUC对比

图9 Facebook-wosn-wall数据集不同时间窗口下各算法AUC对比

实验表明在SOTS的时间窗口划分结果下进行实验，各预测算法都能在选取的窗口大小中得到更为精准的预测结果，说明SOTS算法对动态网络时间窗口划分的有效性；同时利用两个时序相关函数的计算，也能更为快速地确定划分结果，这也体现了SOTS算法的高效性。

基于优化的时间窗口的划分，分别在两个数据集上进行了上述4种链路预测方法的对比实验。实验中，考虑到稀疏网络中模体的闭合次数较少，因此将连边次数的影响占比δ设为0.7，则模体的闭合次数影响占比为0.3。实验结果如图10所示，TS算法作为一种经典的时序链路预测方法还是有着较高的准确性的，它在Enron数据集上的表现明显比TTM和TCM算法更好，但在Facebook-wosn-wall数据集上的表现较差，由于Facebook-wosn-wall数据集规模相对较大，模体演化的规律性更容易体现出来并被模型所学习，三种基于模体转换分析的算法都有着相似的表现。

图10 不同数据集下各算法的AUC值对比

虽然TTM和TCM都对模特转换进行了分析，但TTM缺乏对不同模体转换概率随时间变化的规律的进一步挖掘，而TCM缺乏对动态网络时间窗口划分准确合理的处理和对真实网络有向性的考虑。与其他三种算法相比，MFME方法利用SOTS算法快速得到了更为准确合理的时间窗口的划分，对模体演化规律分析后选用合理的时序预测方法，同时充分考虑了模体的两个影响因子对模体演化的影响，使得MFME算法在两个数据集下的预测效果都有较好表现。

3.3 算法复杂度分析

本文所提的算法可分为三个主要部分，一是时间窗口大小的确定，二是模体演化概率矩阵的构建，三是模体影响指数的计算。其中，SOTS算法的时间复杂度为O(n),模体演化概率矩阵计算时间复杂度为：如果采用传统的对网络进行遍历的方式计算则时间复杂度为O(tn3)，模体影响指数计算时间复杂度为O(nt)。其中，n为网络节点数，b为网络最大度，t为时间窗口。

4 结 语

链路预测是动态网络演化研究的重要内容，合适的时间窗口划分是对动态网络演化研究的必要且关键的一步。将模体这种微观结构的演化规律应用到动态网络的链路预测之中，可以更加深入、准确地挖掘节点间的关联变化从而取得较好的链路预测效果。现实中的大多数动态网络都是有向网络，本文基于动态有向网络首先研究时间窗口的划分，基于优化的时间窗口利用模体演化矩阵来记录网络中不同时间序列模体演化情况，引入整合移动平均自回归模型来预测模体的演化概率。最后，综合考虑模体演化影响因子获得连边影响指数并结合模体演化概率来计算节点间产生连边的分数。仿真实验表明，本文所提方法在时序链路预测中可获得更精确的预测值。在以后的研究中，欲更加深刻挖掘模体演化的周期性和趋势性等规律对动态有向网络链路预测的影响。