-
摘要: 时序链路预测是动态网络分析的重要组成部分,具有极大的理论和应用价值. 传统的时序链路预测方法往往直接对边的演化规律进行分析,忽略了网络中其他微观结构的演化对链路形成的影响. 基于此分析,本文引入非负张量分解和时间序列分析对网络模体的演化规律进行研究,进而提出一种基于模体演化的链路预测方法. 在三个真实数据集上的实验结果表明,该方法能有效提高链路预测精度.Abstract: Temporal link prediction, which has great value in both research and application, is an important component of the dynamic network analysis. Traditional temporal link prediction methods trend to directly analyze the edge's evolution regularity, while ignoring the influence of other microstructure evolution on link formation. On the basis of this analysis, we adopt the nonnegative tensor decomposition and time series analysis model to extract the evolution regulars of motif, and then propose a temporal link prediction method based on motif evolution. Experimental results on three real data sets show that our method can effectively improve the link prediction accuracy.
-
实际网络的结构随时间动态变化,导致传统的静态网络分析方法不能有效挖掘网络信息[1].时序链路预测方法可以根据网络的历史信息推测网络中将会产生的边,是一种重要的动态网络分析方法,具有极大的理论和应用价值[2].如可以用于Facebook、微信等社交平台上的朋友推荐[3],帮助解决商品推荐中的数据稀疏问题[4-5],减少生物实验成本[6],推进复杂网络演化研究等.
近年来,时序链路预测问题受到了多个领域的广泛关注,许多时序链路预测方法相继被提出.其中一类是对网络结构特征直接进行分析的方法[7-9],文献[7]采用时间序列分析的方法对网络中节点对连边次数随时间变化的规律进行分析,并结合其他静态网络结构特征进行链路预测;文献[8]提出了一种进化算法对网络中的拓扑特征和属性特征进行整合,以提高链路预测精度.还有一类是基于机器学习的方法[10-11],文献[10]认为边的连接紧密性随时间不断变化,并据此提出了一种名为"时间分"的新特征,该特征可以用于有监督的学习方法中;文献[11]考虑到链路预测面临正负样本不均衡的问题,提出了一种基于半监督学习的链路预测方法.矩阵分解和张量分解理论在时序链路预测中也发挥了重要作用[12-13],文献[12]将网络动态数据合并为一个矩阵,利用截断奇异值分解对未来可能产生的连边进行预测;此外,该文献还提出了一种原始的将张量分解用于时序链路预测的方法.文献[13]利用矩阵分解和图规则化技术整合网络属性信息和结构信息来进行链路预测.
对未来可能产生的边进行预测的核心是对网络演化规律的把握.上述文献大都采用一定的数学模型,直接在边的层面上对网络的演化规律进行分析.从边的层面对链路进行预测,虽然非常直观,但是忽略了其他网络结构信息.模体是非常重要的一种网络结构,很多复杂网络的重要性质就是借助模体被发现的[14].网络模体演化作为网络微观演化的一种,是网络演化分析的重要组成部分[15].文献[16]研究表明,网络模体演化规律可以从很大程度上描述网络结构特征的变化.因此,边的形成也可能是网络模体不断变化、相互作用的结果.研究模体演化与时序链路预测间的关系,进而根据模体的演化规律对链路进行预测具有重要的意义.
但是这方面的研究仍处于起步阶段[17-20],文献[17]直接从网络的微观演化入手,通过分析网络中经常出现的模式的时序演变来对链路进行预测.三元组是社会网络中非常重要的一类模体,三元组演化在动态社会网络分析中起到了非常重要的作用[18-21].文献[18]分析了Enron网络中相邻快照间的三元组模体转换概率,将转换概率的均值用于链路预测中;文献[19]从多个方面对三元组进行衡量,并将之用于异质网络的时序链路预测中.但是,上述文献大都只对模体的变化进行了实验上的统计,缺乏对模体演化规律的进一步分析.
基于上述分析,本文对社会网络中三元组模体的演化规律进行了研究,并以此为基础,提出了一种基于模体演化的时序链路预测算法.本文的主要贡献如下: 1)在多个实际网络中对三元组的演化规律进行实证研究,发现了一些有趣的现象.2)综合考虑网络结构变化特点,从链路预测角度提出一种三元组重要性指标,实验表明,该指标可以有效提高链路预测精度.3)综合考虑不同三元组类型转换过程中的相互影响,引入非负张量分解和时间序列分析对三元组转换规律进行分析,并以此为基础,提出一种基于三元组演化的时序链路预测方法.4)在真实数据集上与其他方法进行比较,证明本方法更加有效.
本文第1节对一些基本概念进行了介绍,第2节是实验数据说明,第3节介绍提出的基于模体演化的链路预测方法,第4节将本文提出的算法和其他链路预测算法在三个实际网络中进行对比分析,最后第5节给出结论.
1. 相关概念
1.1 时序链路预测问题描述
随时间变化的无向无权无环网络 $G=(g_1,g_2,\cdots,g_t,\cdots,g_T)$ 由T个快照组成,其中,gt表示T时刻网络G的快照, $V(g_t)$ 表示快照gt的节点集,E(gt)表示快照gt的边集.动态链路预测问题可以转化为:已知网络G中g1到gt的拓扑信息,给定一种链路预测方法,为 $g_{t+1}$ 中的任意节点对 $(v_x,v_y)$ 赋予一个分数值,该分数值可以理解为与两节点的连边概率正相关的一个数值.
1.2 三元组
本文对无向网络中三元组模体的变化规律进行深入分析,并将这种变化运用于链路预测中,以得到更高的预测精度.本文对三元组中的节点进行区分,对不同的节点进行编号,得到无向网络中的8种三元组,如图 1所示.图中标识的三元组ID具有唯一性,将在本文其他章节得到应用.
张量(Tensor)是矩阵在高维空间上的扩展,与矩阵相比,它能描述更多的因素,可以很自然地表达高维数据而不丢失信息,因而能在最大程度上保持数据的内在结构特性[22].一个三阶张量可以表示为 $Z \in {{\bf{R}}^{{I_1} \times {I_2} \times {I_3}}}$ ,其元素为 ${z_{ijk}},i \in {I_1},j \in {I_2},k \in {I_3}$ .
张量分解可以挖掘张量的潜在结构及其不同维间的关联[23],一般可以分为CP(CanDecomp/ParaFac)分解和Tucker分解两类,其中,CP分解可以看作是矩阵奇异值分解的高阶扩展,在可解释性、解的唯一性方面具有优势[22].一个三阶张量的CP分解可以表示为
$ \hat Z=\sum\limits_{r=1}^R {{\lambda _r}} {a_r} \circ {b_r} \circ {c_r}=[\lambda;A,B,C] $
(1) 其中,符号 $\circ $ 表示外积,被加数 $\lambda_{r}a_r\circ b_r\circ c_r$ 表示一个组件,设 $\| a_r\|=\| b_r\|=\| c_r\|=1$ , $\lambda_r$ 表示第r个组件的权重,R表示组件的个数. $[\lambda;{\pmb A},{\pmb B},{\pmb C}]$ 是CP分解的缩写形式,其中, ${\pmb A}\in {\bf R}^{I_1\times R},{\pmb B}\in{\bf R}^{I_2\times R},{\pmb C}\in{\bf R}^{I_3\times R}$ 都称作因子矩阵,表示张量在各个维度上的主成分.CP分解过程如图 2所示.
更特别地,非负CP分解的目标是将非负张量 $Z \in {\bf{R}}_+^{{I_1} \times {I_2} \times {I_3}}$ 分解为非负因子之和:
$ Z \approx \sum\limits_{r=1}^R {{\lambda _r}} {a_r}^\circ {b_r}^\circ {c_r} $
(2) 此分解可以通过求解最优化问题得到:
$ \begin{array}{l} \min \left\| {Z - \sum\limits_{r=1}^R {{\lambda _r}} {a_r}^\circ {b_r}^\circ {c_r}} \right\|\\ {\rm{s}}.{\rm{t}}.\quad {\lambda _r} \ge 0,\;{a_r} \ge 0,\;{b_r} \ge 0,\;{c_r} \ge 0,\\ \qquad \qquad \qquad \qquad \quad \;r=1,2,\cdots,R \end{array} $
(3) 2. 实验数据
本文采用三种社会网络数据集对算法进行评估分析.Condmat网络[10]包含了1995年~2000年间,凝聚物理问题中共19464次多机构合作记录,以年为单位划分网络快照.Enron数据集[24]包含了2001年1月1日~2002年3月31日间,Enron机构内部员工的邮件通信记录,以月为时间间隔建立快照.Facebook数据集[25]包含了2006年11月~ 2009年1月,60290位用户以"墙评论"形式的交流记录,以月为时间间隔建立快照.这些网络的参数信息如表 1所示.
表 1 实验数据集参数表Table 1 Parameters of experimental data setsCondmat Enron Facebook 节点数 17636 22 477 60 290 总边数 88 036 164 081 838 090 快招数 6 16 52 3. 算法设计
3.1 算法总体描
本文根据三元组的演化规律对网络中节点对的连边可能进行预测.首先对前两个相邻快照之间的三元组进行统计,得到这两个快照中不同三元组类型之间的转换概率,并构成这两个快照间的三元组转换概率矩阵;以此类推,得到所有相邻快照间的三元组转换概率矩阵,并将其合并为三阶张量.然后对此三元组转换概率张量进行CP分解,对其中的时间因子C进行时间序列分析后合并各因子矩阵,得到T时刻到T+1时刻的三元组转换概率矩阵.根据该三元组转换概率矩阵和T时刻的网络快照可以得到T+1时刻各个三元组的生成概率;最后根据T+1时刻中各个三元组的生成概率和不同三元组的重要性来预测T+1时刻网络中节点对的连边可能.下面对各个步骤进行详细分析.
3.2 三元组转换概率矩阵分析
对网络中的历史信息进行统计,可以得到相邻快照之间,不同三元组类型的转换概率.常用的统计方法是对网络中的节点进行遍历,但是时间复杂度很高.在对数据进行分析时发现,第1类型三元组转换到第1类型三元组的情况占三元组转换总数的很大一部分,传统的对节点遍历的方法将大部分时间花费在了统计此类情况上.复杂网络具有稀疏性,以Facebook数据集为例,网络节点总数为60290,因此网络中可能产生的节点连边总数为60290×(60290-1)/2,但是每个时刻产生的连边的均值为16117,仅占可能产生的总边数的百万分之八.考虑到这种网络的稀疏性,本文提出了一种快速统计方法.方法的核心思想是先对含有连边的节点进行研究,即先统计第2类型三元组转换到第8类型三元组的情况,此类转换情况包含第2~8类型三元组转换到第1类型的情况和第1类型三元组转换到第2 ~8类型三元组的情况.然后用转换总数减去上述情况的转换数,得到第1类型到第1类型三元组的转换数.最后进行归一化,得到三元组各个类型之间的转换概率.快速统计方法只需要对相邻快照间存在连边的节点进行统计即可得到第2~8类型三元组的转换情况.由网络稀疏性可知,网络中实际存在的边只占网络中可能存在的边的很小一部分,因此,此快速统计方法适用于大规模网络.
三元组的类型数为8,因此,本文定义一个大小为8×8的矩阵来描述相邻时刻间不同三元组类型的转换概率,称为三元组转换概率矩阵(Triad changement matrix,TCM).矩阵中各元素的值为
$ \begin{align} {TCM}_t{(i,j)}=P({tr}_i[t]\rightarrow {tr}_j[t+1]) \end{align} $
(4) 其中, ${tr}_i[t]$ 表示T时刻第i类三元组(第1.2节中编号为i的三元组), ${TCM}_t(i,j)$ 表示从t时刻到t+1时刻第i类三元组转换到第j类三元组的概率,即对应时刻TCM矩阵第i行第j列元素.
图 3~5是各数据集的TCM矩阵色谱图,虽然不同数据集中,不同时刻间的TCM矩阵不同,但是这些TCM矩阵仍然表现出一些相同的规律:
1) 所有TCM矩阵左上角元素值都最大,表明整个网络比较稀疏,许多三元组保持着第1类型,即三元组中不存在连边.
2) TCM矩阵最左边一列的元素值较大,表明已经存在连边的三元组在下一时刻中不再存在连边的可能性很大.
3) TCM矩阵对角线上的值普遍较高,表明三元组类型转换时存在"惯性",有较大可能维持原有状态.
4) TCM矩阵左下角的值普遍高于右上角,除最左边的元素较大外,左下角其他元素的值都较为均衡,意味着三元组中各边都较易消失,且消失概率大致相同.
通过对所有TCM矩阵的进一步分析,发现除上述共同规律外,不同三元组类型间的转换概率随着时间的变化也表现出了一些特定的趋势.本文以Facebook数据集为例,描述这些规律.图 6为Facebook数据集中不同三元组类型间转换概率随时间变化的色谱图.
图 6 Facebook数据集不同三元组类型间转换概率随时间变化色谱图Fig. 6 Chromatogram of triad transition probabilities that change with time in Facebook network从图 6中可以发现以下规律:
1)从图 6(a)中可以看出,第1类型三元组较为稳定,基本维持不变,这是因为第1类型三元组中各节点间没有发生联系,随着时间的变化,该三元组内各节点发生联系的可能性仍然较小.
2)从图 6(b)~6(d)中可以看出,第2类型到第4类型三元组随着时间变化表现出了稳定的趋势,或者维持原有状态,或者转换为第1状态;这是因为三元组中只有两个节点间发生了联系,三元组内各个节点还没有都发生联系,三元组内部连接还不够紧密、稳固,可以将这种三元组称为"弱三元组".
3)从图 6(e)~6(h)中可以看出,第5类型到第8类型的三元组有一定概率转换为其他各个类型的三元组,这是因为三元组中至少两个节点间发生了联系,各个节点间的联系较强,可以将这种三元组称为"强三元组".弱三元组转换为强三元组的概率较小,但是强三元组有较大概率转换为弱三元组.
4)有些转换概率还表现出了周期性的趋势,如图 7所示,第6类型三元组到第2类型三元组的转换概率、第7类型三元组到第3类型三元组的转换概率和第8类型三元组到第5类型三元组的转换概率的变化具有周期性;而另外一些三元组转换概率则较为稳定,在一定周期内没有发生较大变化,如第5类型三元组到第8类型三元组的转换概率.
图 7 Facebook数据集中部分随时间变化的三元组转换概率示意图Fig. 7 Diagram of some triad transition probabilities that change with time in Facebook network3.3 三元组转换概率预测
上述规律表明,三元组的演化是非线性的,不同三元组类型间也存在影响,因此,不能采用简单的如求均值的方式对三元组的转换概率进行预测.非负张量可以很自然地描述三元组的转换概率而不丢失信息,张量分解可以挖掘不同三元组转换概率之间的潜在关系.大部分三元组转换概率表现出了周期性趋势或平稳趋势,时间序列分析可以很好地对这些趋势进行预测.因此,本文采用非负张量分解和时间序列分析的方法对三元组转换概率进行进一步分析和预测.本文构建三元组转换概率张量(Triad changement tensor,TCT)来描述所有相邻时刻间三元组的转换概率,张量中的元素为
$ \begin{array}{l} TCT(i,j,t)=TC{M_t}(i,j)=\\ \qquad P(t{r_i}[t] \to t{r_j}[t+1]) \end{array} $
(5) 该张量与TCM矩阵的关系可以表示为
$ \begin{align} TCT=(TCM_1,TCM_2,\cdots,TCM_t,\cdots,TCM_T) \end{align} $
(6) 不同的三元组转换概率间存在关联,同一三元组转换概率本身随时间变化时也存在关联,因此,采用非负CP分解对TCT张量进行分解,挖掘张量各维之间的潜在关系及各维数据自身的潜在结构. $AB^{\rm T}$ 衡量了不同类型三元组间的转换关系,而C中包含了这种关系随时间变化的信息;对时间因子矩阵C进行时序分析,得到 $c_{T+1,r}$ 后,可以得到T时刻到T+1时刻的三元组转换似然矩阵(Triad changement likelihood matrix,TCLM):
$ \begin{align} TCLM_T(i,j)=\sum_{r=1}^R\lambda_r(a_{i,r}\cdot b_{j,r}\cdot c_{T+1,r}) \end{align} $
(7) $TCLM_T$ 矩阵包含了T时刻到 $T+1$ 时刻的三元组转换信息,但是不满足概率条件,因此,对 $TCLM_T$ 矩阵按行进行归一化,得到T时刻到T+1时刻的三元组转换概率矩阵 $TCM_T$ .本文采用Matlab工具箱tensor toolbox 2.5中[26]的cp-nmu函数对TCT张量进行CP非负分解,算法源码由此工具箱提供,采用的时序分析模型是较为简单的指数衰减模型:
$ \begin{array}{*{20}{l}} {{c_{T+1,r}}=}&{\;\alpha {c_{T,r}}+\alpha(1 - \alpha){c_{T - 1,r}}+}\\ {}&{\;\alpha {{(1 - \alpha)}^2}{c_{T - 2,r}}+\cdots+{{(1 - \alpha)}^{T - 1}}{c_{1,r}},}\\ {}&{\qquad \qquad \quad \;r=1,\cdots,R且0 <\alpha <1} \end{array} $
(8) 其中,α是平滑参数,设α=0.5,ct,r是对TCT张量进行CP分解后得到的时间因子矩阵C中的元素,表示第r个组件中t时刻的时间因子值.除指数衰减模型外,也可以采用Holter-Winter等其他时序分析方法来分析三元组转换概率随时间变化的潜在趋势[27],对未来的时间因子值进行推测.
3.4 三元组重要性分析
一个节点对包含在不同的三元组中,如图 8所示,节点对AB包含在ABC、ABD、ABE三个三元组中.每个包含该节点对的三元组的状态都为预测其连边可能提供了参考,但不同的三元组对预测的重要性不同,"活跃"的三元组往往能起到更加积极的作用.三元组的活跃度可以表现为两个方面,一方面是三元组内部各节点间连边的频率,频率越高,三元组越活跃;另一方面是三元组形成闭合的频率,网络演化中,三元组形成闭合的次数越多,说明该三元组内部节点间关系越紧密,对预测节点对的连边也越重要.此外,历史连边的产生时间距预测时刻点越远,则对预测时刻点的节点对产生的影响越小[28],本文用指数衰减模型描述这种影响.
基于上述分析,本文定义三元组重要性指标来描述三元组对于链路预测的重要性程度:
$ \begin{align} W_i=\beta\sum_{t=1}^{ T}\theta_1^{T-t}l_{i,t}+\gamma\sum_{t=1}^{ T}\theta_2^{T-t}trc_{i,t}+1 \end{align} $
(9) 其中,Wi表示三元组i的重要程度,li,t表示t时刻三元组i中各节点的连边个数,trci,t表示t时刻三元组i是否闭合,闭合为1,不闭合为0,β 、γ为调控参数,θ1、θ2取值为(0,1),用来衡量历史连边的产生时间对链路预测的影响.
3.5 根据TCM矩阵和三元组重要性指标进行链路预测
根据 $TCM_T$ 矩阵和计算得到的三元组重要性指标,可以得到T+1时刻网络中每个节点对的连边可能值:
$ \begin{align} score_{i,j}=\sum_{m=1}^{M_{tr}}W_m\times TCM(m) \end{align} $
(10) 其中, $M_{tr}$ 表示T+1时刻所有包含节点对ij的三元组总数,Wm表示第m个三元组的重要程度,TCM(m)表示T+1时刻包含节点对ij的第m个三元组从时刻T到时刻T+1的转换概率.
将本文提出的算法称为TCM链路预测算法,算法伪码如下所示.
算法1.基于模体演化的链路预测方法
输入. 1到T时刻网络快照.
输出. T+1时刻节点对的连边概率.
1 initialize: calculate TCM matrix of T snapshot to T+1 snapshot
2 for each node pair
3 for each triad including the node pair
4 calculate the importance of the triad by(9)
5 end
6 calculate link probability of the node pair by(10)
7 end
4. 实验结果和分析
4.1 实验设计
为测试算法可行性,本文在上述三个数据集上进行实验.实验程序采用Matlab编写,在装有32位Win7系统的单机上运行,该单机内存为4GB,Matlab版本为R2013a.
本文与TTM[18]、HPLP[29]、PA[30]和TS[7]四种时序链路预测方法进行对比.TTM方法首先对三元组转换概率进行了统计研究,并将其用于链路预测中.PA方法是链路预测中常用的基准比较算法.HPLP方法是目前公认较好的一种基于特征的链路预测有监督学习框架,TS方法是一种经典的时序链路预测方法.
文献[31]对链路预测中各个评价指标进行了比较,研究表明,当正负样本非常不均衡时,采用精确度--召回率曲线下面积(Area under precision-recall curve,AUPR)值作为评价指标更加合理,但是之前的链路预测方法大多采用接收者操作特征曲线下面积(Area under receiver operating characteristic curve,AUC)值作为评价指标,严谨起见,本文采用AUC值和AUPR值作为评价指标.
在计算AUC值和AUPR值时,采用如图 9所示的方法确定训练集和测试集.首先选取网络中前▽ T时刻的快照作为训练集,以第▽ T+1时刻的网络快照为测试集,计算一次AUC值和AUPR值.然后将时间窗口顺次移动一个步长,重新计算AUC值和AUPR值,循环十次后,对所有AUC值和AUPR值求平均作为对应时间窗口▽ T的AUC值和AUPR值.
4.2 实验结果分析
4.2.1 有效性验证
选取时间窗口为5,三元组重要性指标中各参数都设定为0.5,其他算法中各参数按原文默认值设定,得到实验结果如表 2~4所示.从表中可以看出,采用AUC值进行衡量时,TCM算法在Condmat数据集中取得了很好的预测精度,但在Enron数据集中略低于TS算法,在Facebook数据集中也只略优于TS算法.但是当采用AUPR值作为评价指标时,TCM算法都取得了很好的预测效果,并且同其他算法相比,优势明显.例如,在Enron数据集中,TCM算法比TS算法提高了23\%.因此,本文提出的算法具有较高的预测精度.从表中还可以看出,许多情况下,时序链路预测算法优于静态链路预测方法,TS算法和TCM算法都取得了较好的效果,虽然TTM算法只是对三元组的转换概率进行了简单的统计,但是也取得了和HPLP算法相比拟的预测效果,说明了根据网络模体演化规律进行链路预测具有可行性.
表 2 Facebook数据集中各算法预测精度表Table 2 Accuracy of different methods in Facebook networkPA HPLP TTM TS TCM AUC 0.52 0.76 0.79 0.83 0.84 AUPR 0.03 0.06 0.08 0.1 0.13 表 3 Enron数据集中各算法预测精度表Table 3 Accuracy of different methods in Enron networkPA HPLP TTM TS TCM AUC 0.8 0.91 0.81 0.92 0.89 AUPR 0.04 0.17 0.21 0.23 0.30 表 4 Condmat数据集中各算法预测精度表Table 4 Accuracy of different methods in Condmat networkPA HPLP TTM TS TCM AUC 0.59 0.68 0.76 0.81 0.92 AUPR 0.24 0.25 0.22 0.25 0.35 TTM算法与TCM算法都对三元组的转换概率进行了分析,但TTM算法缺乏对不同三元组转换概率随时间变化的规律的进一步挖掘和对三元组重要性程度的区分.为更详细直观地比较这两种算法的性能,绘制出三个数据集中TCM算法与TTM算法的ROC曲线和PR曲线如图 10~12所示.从图中可以更直观地看出,只有在Facebook数据集中,采用ROC曲线衡量时,二者预测效果相差不大,其他情况下TCM算法都优于TTM算法.这是因为,TTM算法对三元组演化规律的挖掘还不够深入,TCM算法不仅研究了相邻时刻间的三元组转换规律,还从整体上研究了三元组转换概率随时间变化的规律,并合理衡量了不同三元组在预测中的作用.
图 10 Facebook数据集TCM算法和TTM算法性能对比图Fig. 10 Performance contrastgures of TCM algorithm and TTM algorithm in Facebook network
图 11 Enron数据集TCM算法和TTM算法性能对比图Fig. 11 Performance contrastgures of TCM algorithm and TTM algorithm in Enron network
图 12 Condmat数据集TCM算法和TTM算法性能对比图Fig. 12 Performance contrastgures of TCM algorithm and TTM algorithm in Condmat network4.2.2 算法时间复杂度分析
本文提出的算法可以分为三个主要部分,一是三元组重要性指标的计算,二是三元组转换概率矩阵的计算,三是计算节点间可能产生的连边.三元组重要性指标计算的时间复杂度为O(tn).其中,t为时间窗口,n表示网络节点总数.如果采用传统的对网络进行遍历的方式计算三元组转换概率矩阵,则时间复杂度为O(tn3),但是本文提出了一种快速的统计方法,该方法的时间复杂度为O(tL2),其中,L为相邻两时刻网络快照的连边总数.通过比较可知,这种快速方法有效地降低了此步骤的时间复杂度.在计算单个节点对的连边可能时,本文采用与计算三元组转换概率矩阵相类似的思想,其时间复杂度为O(l),其中,l为t时刻网络快照中的连边总数.计算全网络所有节点对的连边可能的时间复杂度则为O(ln2).
4.2.3 时间窗口及三元组重要性指标对TCM算法的影响
Condmat数据集的快照数只有6,因此,本文使用Facebook数据集和Enron数据集来分析时间窗口和三元组重要性指标对TCM算法的影响,评价指标采用AUPR,实验结果如图 13所示.
图 13 时间窗口及三元组重要性指标对TCM算法的影响Fig. 13 Influence of time window and the triad importance index to TCM method1) 时间窗口对TCM算法的影响.从图中可以看出,多数情况下,随着时间窗口的增加,TCM算法的预测精度有逐渐提升的趋势,这是由于算法可以利用更多的网络时序信息.但是当时间窗口的大小增加到一定程度时,算法精度反而下降,这应该是由于初始时刻距要预测时刻较远,该时刻快照的拓扑信息反而会对链路预测产生负面影响.此外,当β=0,γ=1时,算法预测精度随时间窗口缓慢增加,但增加幅度较小,这可能是由于网络比较稀疏,三元组闭合次数较少,此种情况下的三元组重要性指标不能很好地衡量三元组在链路预测中的重要程度,即使时间窗口增加时,算法也无法很好地利用网络时序信息.
2) 三元组重要性指标对TCM算法的影响.本文比较了β=0.5/γ=0.5,β=0/γ=1,β=1、γ=0三种情况下,TCM算法的预测精度.从图中可以看出,当β=1、γ=0时,TCM算法预测精度最高,β=0.5、γ=0.5时,算法预测精度次之,β=0、 γ=1时,算法预测精度最差.这可能是由于网络数据比较稀疏,三元组闭合次数较少,不能准确反映三元组的重要程度.实验结果还不能完全说明在链路预测中,三元组内部节点连接次数比三元组闭合次数重要.
5. 结论
时序链路预测与网络演化分析密不可分,将网络微观演化规律用于链路预测可以取得较好的预测效果,反之根据链路预测效果也可以从一定程度上评估网络演化机理.本文从这一角度出发,对社会网络中具有重要结构和功能意义的一种模体-三元组的演化规律进行了分析,进而提出了一种基于模体演化的链路预测方法.在三个真实数据集上的实验结果表明,利用网络微观演化规律进行链路预测具有可行性,该方法有较好的预测效果.此外,本文还通过实验分析了时间窗口、三元组重要性指标对实验结果的影响.
本文从网络模体入手,对网络中三元组的演化规律进行了初步探索,并提出了一种新的时序链路预测方法.但在以后的工作中,仍需对三元组演化规律、网络微观演化规律、网络中连边的形成规律以及它们之间的关系进行更深入的理论分析.此外,进一步降低算法时间复杂度并在更多的数据集上测试算法的有效性也是我们下一步的研究方向.
-
图 6 Facebook数据集不同三元组类型间转换概率随时间变化色谱图
Fig. 6 Chromatogram of triad transition probabilities that change with time in Facebook network
图 7 Facebook数据集中部分随时间变化的三元组转换概率示意图
Fig. 7 Diagram of some triad transition probabilities that change with time in Facebook network
图 10 Facebook数据集TCM算法和TTM算法性能对比图
Fig. 10 Performance contrastgures of TCM algorithm and TTM algorithm in Facebook network
图 11 Enron数据集TCM算法和TTM算法性能对比图
Fig. 11 Performance contrastgures of TCM algorithm and TTM algorithm in Enron network
图 12 Condmat数据集TCM算法和TTM算法性能对比图
Fig. 12 Performance contrastgures of TCM algorithm and TTM algorithm in Condmat network
图 13 时间窗口及三元组重要性指标对TCM算法的影响
Fig. 13 Influence of time window and the triad importance index to TCM method
表 1 实验数据集参数表
Table 1 Parameters of experimental data sets
Condmat Enron Facebook 节点数 17636 22 477 60 290 总边数 88 036 164 081 838 090 快招数 6 16 52 
下载: 导出CSV
表 2 Facebook数据集中各算法预测精度表
Table 2 Accuracy of different methods in Facebook network
PA HPLP TTM TS TCM AUC 0.52 0.76 0.79 0.83 0.84 AUPR 0.03 0.06 0.08 0.1 0.13
下载: 导出CSV
表 3 Enron数据集中各算法预测精度表
Table 3 Accuracy of different methods in Enron network
PA HPLP TTM TS TCM AUC 0.8 0.91 0.81 0.92 0.89 AUPR 0.04 0.17 0.21 0.23 0.30
下载: 导出CSV
表 4 Condmat数据集中各算法预测精度表
Table 4 Accuracy of different methods in Condmat network
PA HPLP TTM TS TCM AUC 0.59 0.68 0.76 0.81 0.92 AUPR 0.24 0.25 0.22 0.25 0.35
下载: 导出CSV
-
[1] 席裕庚. 大系统控制论与复杂网络——探索与思考. 自动化学报, 2013, 39(11): 1758-1768Xi Yu-Geng. Large-scale systems control and complex networks——exploration and thinking. Acta Automatica Sinica, 2013, 39(11): 1758-1768 [2] 陆浩, 王飞跃, 刘德荣, 张楠, 赵学亮. 基于科研知识图谱的近年国内外自动化学科发展综述. 自动化学报, 2014, 40(5): 994-1015Lu Hao, Wang Fei-Yue, Liu De-Rong, Zhang Nan, Zhao Xue-Liang. Analytics of lastest research progress in automation discipline based on academic knowledge mapping. Acta Automatica Sinica, 2014, 40(5): 994-1015 [3] Lv L, Medo M, Yeung C H, Zhang Y C, Zhang Z K, Zhou T. Recommender systems. Physics Reports, 2012, 519(1): 1-49 [4] Scellato S, Noulas A, Mascolo C. Exploiting place features in link prediction on location-based social networks. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2011. 1046-1054 [5] Wang D S, Pedreschi D, Song C M, Giannotti F, Barabasi A L. Human mobility, social ties, and link prediction. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2011. 1100-1108 [6] Mamitsuka H. Mining from protein-protein interactions. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2012, 2(5): 400-410 [7] Huang Z, Lin D K J. The time-series link prediction problem with applications in communication surveillance. INFORMS Journal on Computing, 2009, 21(2): 286-303 [8] Bliss C A, Frank M R, Danforth C M, Dodds P S. An evolutionary algorithm approach to link prediction in dynamic social networks. Journal of Computational Science, 2014, 5(5): 750-764 [9] 邓志宏, 老松杨, 白亮. 基于预测误差修正的时序链路预测方法. 电子与信息学报, 2014, 36(2): 325-331Deng Zhi-Hong, Lao Song-Yang, Bai Liang. A temporal link prediction method based on link prediction error correction. Journal of Electronics and Information Technology, 2014, 36(2): 325-331 [10] Munasinghe L, Ichise R. Time score: a new feature for link prediction in social networks. IEICE Transactions on Information and Systems, 2012, E95-D(3): 821-828 [11] Zeng Z Z, Chen K J, Zhang S B, Zhang H J. A link prediction approach using semi-supervised learning in dynamic networks. In: Proceedings of the 6th International Conference on Advanced Computational Intelligence. Hangzhou, China: IEEE, 2013. 276-280 [12] Dunlavy D M, Kolda T G, Acar E. Temporal link prediction using matrix and tensor factorizations. ACM Transactions on Knowledge Discovery from Data, 2011, 5(2): Article No. 10 [13] Gao S, Denoyer L, Gallinari P. Temporal link prediction by integrating content and structure information. In: Proceedings of the 20th ACM International Conference on Information and Knowledge Management. Glasgow, UK: ACM, 2011. 1169-1174 [14] Milo R, Itzkovitz S, Kashtan N, Levitt R, Shen-Orr S, Ayzenshtat I, Sheffer M, Alon U. Superfamilies of evolved and designed networks. Science, 2004, 303(5663): 1538- 1542 [15] 陈关荣. 复杂动态网络环境下控制理论遇到的问题与挑战. 自动化学报, 2013, 39(4): 312-321Chen Guan-Rong. Problems and challenges in control theory under complex dynamical network environments Acta Automatica Sinica, 2013, 39(4): 312-321 [16] Juszczyszyn K, Musial K, Kazienko P, Gabrys B. Temporal changes in local topology of an email-based social network. Computing and Informatics, 2009, 28(6): 763-779 [17] Bringmann B, Berlingerio M, Bonchi F, Gionis A. Learning and predicting the evolution of social networks. IEEE Intelligent Systems, 2010, 25(4): 26-35 [18] Juszczyszyn K, Musial K, Budka M. Link prediction based on subgraph evolution in dynamic social networks. In: Proceedings of the 3rd IEEE International Conference on Social Computing, the 3rd IEEE International Conference on Privacy, Security, Risk and Trust. Boston, USA: IEEE, 2011. 27-34 [19] Rümmele N, Ichise R, Werthner H. Exploring supervised methods for temporal link prediction in heterogeneous social networks. In: Proceedings of the 24th International Conference on World Wide Web. Florence, Italy: International World Wide Web Conferences Steering Committee, 2015. 1363-1368 [20] Davis D, Lichtenwalter R, Chawla N V. Supervised methods for multi-relational link prediction. Social Network Analysis and Mining, 2013, 3(2): 127-141 [21] Microscopic evolution of social networks. In: Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Las Vegas, USA: ACM, 2008. 462-470 [22] Kolda T G, Bader B W. Tensor decompositions and applications. SIAM Review, 2009, 51(3): 455-500 [23] Signoretto M, Van de Plas R, De Moor B, Suykens J A K. Tensor versus matrix completion: a comparison with application to spectral data. IEEE Signal Processing Letters, 2011, 18(7): 403-406 [24] Leskovec J, Lang K J, Dasgupta A, Mahoney M W. Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics, 2009, 6(1): 29-123 [25] Viswanath B, Mislove A, Cha M, Gummadi K P. On the evolution of user interaction in Facebook. In: Proceedings of the 2nd ACM Workshop on Online Social Networks. Barcelona, Spain: ACM, 2009. 37-42 [26] Bader B W, Kolda T G. Efficient Matlab computations with sparse and factored tensors. SIAM Journal on Scientific Computing, 2007, 30(1): 205-231 [27] Chatfield C. The Analysis of Time Series: an Introduction (6th edition). Boca Raton: Chapman and Hall/CRC Press, 2013. 7-8 [28] Sharan U, Neville J. Temporal-relational classifiers for prediction in evolving domains. In: Proceedings of the 8th IEEE International Conference on Data Mining. Pisa, Italy: IEEE, 2008. 540-549 [29] Lichtenwalter R N, Lussier J T, Chawla N V. New perspectives and methods in link prediction. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington DC, USA: ACM, 2010. 243-252 [30] Liben-Nowell D, Kleinberg J. The link-prediction problem for social networks. Journal of the American Society for Information Science and Technology, 2007, 58(7): 1019-1031 [31] Lichtnwalter R, Chawla N V. Link prediction: fair and effective evaluation. In: Proceedings of the 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. Istanbul, Turkey: IEEE, 2012. 376-383 期刊类型引用(9)
1. 赵宇红，张晓炜. 基于模体演化的多因子动态链路预测方法. 计算机应用与软件. 2022(03): 234-240 . 
百度学术2. 吴翼腾，于洪涛，顾泽宇. 基于统一描述网络结构模型的链路预测方法. 计算机工程. 2022(07): 51-58 . 百度学术3. 吴铮，陈鸿昶，张建朋. 基于时序模体注意力图卷积的动态网络链路预测算法. 计算机应用研究. 2021(10): 3143-3147 . 百度学术4. 顾传青，唐鹏飞，陈之兵. 计算张量指数函数的广义逆张量ε-算法. 自动化学报. 2020(04): 744-751 . 本站查看5. 顾秋阳，琚春华，吴功兴. 基于子图演化与改进蚁群优化算法的社交网络链路预测方法. 通信学报. 2020(12): 21-35 . 百度学术6. 杜凡，刘群. 有向动态网络中基于模体演化的链路预测方法. 计算机应用研究. 2019(05): 1441-1445+1453 . 百度学术7. 刘书新，刘群，杜凡. 基于模体演化与社区一致性的时序链路预测方法. 计算机应用研究. 2019(12): 3674-3678+3684 . 百度学术8. 蔡海尼，牛冰慧，文俊浩，王喜宾. 基于时序模型和矩阵分解的推荐算法. 计算机应用研究. 2018(06): 1624-1627+1659 . 百度学术9. 潘永昊，于洪涛，刘树新. 基于神经网络的链路预测算法. 网络与信息安全学报. 2018(07): 30-38 . 百度学术其他类型引用(10)
-
下载:
计量
- 文章访问数: 1886
- HTML全文浏览量: 422
- PDF下载量: 1710
- 被引次数: 19
