没有合适的资源?快使用搜索试试~ 我知道了~
一种融合局部拓扑影响力的时序链路预测算法.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 98 浏览量
2023-02-23
20:06:58
上传
评论
收藏 1.32MB DOCX 举报
温馨提示
试读
19页
一种融合局部拓扑影响力的时序链路预测算法.docx
资源推荐
资源详情
资源评论
1. 引言
自然界中一切事物都是运动的,现实世界中的各种复杂网络也都是随着时间变化而不
停演化的动态网络,如航空交通运输网络、生物网络、文献引用网络、电力网络、社交推
荐网络、蛋白质网络等等,这些真实网络都可以抽象成为一个个由节点和连边组成的动态
时序复杂网络。挖掘节点与节点之间、连边与连边之间的相互作用,分析动态网络的演化
规律,预测网络的变化情况,对研究网络科学和复杂系统具有重要意义。链路预测作为研
究复杂科学的重要技术之一,已成为近年来的研究热点问题
[1,2]
。
链路预测是挖掘网络数据之间潜在关系的一种重要方法,原理就是利用已知的网络节
点属性、连边属性和拓扑结构等信息,预测网络中未连接节点之间产生连边的可能性
[3]
。
基于“朋友的朋友很可能也是朋友”等规律,最常用的链路预测指标包括 CN(Common
Neighbors),AA(Adamic-Adar),RA(Resource Allocation),PA(Preferential Attachment),
LP(Local Path),Katz 等
[4]
。近年来,许多学者对预测指标的优化开展了大量的研究工作,
李治成等人
[5]
利用节点的拓扑稳定性对相似性指标进行了优化;王凯等人
[6]
对信息在传输路
径上的有效性进行了刻画,优化了 RA 指标;刘树新等人
[7]
从资源传输匹配的角度对资源
双向传输进行了准确量化。在静态网络链路预测的基础上,时序链路预测利用每一个时刻
的静态预测指标,结合时间序列分析的方法,实现对动态时序网络的分析。最朴素的思路
就是对所有时刻图的特征建立总体平均模型
[8]
,即利用每一时刻相似度特征的平均值去预
测下一时刻的情况。Huang 等人
[9]
将时间序列应用到链路预测中,计算网络中所有节点对
在每一个时刻相似性分数的时间序列矩阵,结果表明,引入时间序列的动态算法性能优于
传统的静态算法。Güneş 等人
[10]
将静态网络的拓扑结构相似性指标与
ARIMA(Autoregressive Integrated Moving Average model)模型进行融合,提出的时序链路预
测算法取得了良好的实验结果。刘继嘉等人
[11]
利用 LR(Liner Regression)线性回归模型对改
进相似性特征的时间序列进行建模,实现了对动态网络不错的预测效果。
上述方法从时间序列分析的角度进行分析,未考虑网络演化过程对网络本身的影响,
许多学者在计算历史时刻图信息特征的基础上,增加不同的网络演化规律方面的特征,提
出了精度更高的时序链路预测算法。如 Munasinghe 等人
[12]
认为节点对之间的相互作用会随
时间发生变化,如果近期两个节点与它们的共同邻居之间的连边越多,那么未来这两个节
点间发生连边的概率也会变大。Zhang 等人
[13]
利用基于隐藏空间模型的方法,把共同邻居
的关系映射到隐藏空间,在隐藏空间中的距离越近的节点对,产生连接的可能性更大。邓
志宏等人
[14]
以传统的结构相似性算法为基础,提出了基于误差修正的时序网络链路预测算
法,取得了较好的预测结果。Bliss 等人
[15]
通过协方差矩阵自适应演化策略对相似性指标进
行了优化,在 Twitter 数据集中取得较好的精确度。这些时序链路预测算法虽然有效地利用
了时间信息,但它们只考虑了局部连边的网络演化规律,对网络拓扑结构的特性挖掘有
限。因此,可以进一步挖掘网络微观结构在演化过程中节点变化和连边变化的影响力演化
模型。
此外,还有很多学者从网络动力学的角度,对网络的离散性、动态性、自适应和高阶
特征等方面开展了相关研究,提出了基于线性方程
[16]
、基于压缩感知
[17]
、基于相位同步
[18]
、基于霍克斯过程
[19]
等模型,这些模型都把网络演化过程抽象成不同的非线性迭代训练
过程,但这些模型要么仅对稀疏连边的演化进行建模,要么仅对连边变化映射相位的演化
进行建模,要么仅对节点事件的演化进行建模。这些模型的应用场景比较单一,如线性方
程和压缩感知的方法大多把时序网络转换成线性系统,相位同步模型的方法更适应马尔可
夫网络,对记忆网络的效果不好,基于霍克斯过程的模型大多针对节点的演化信息进行拟
合,而忽略了网络结构的其他信息对网络演化的影响,也没有对各类特征的融合进行建模
研究。
基于以上分析,本文首先从研究这些模型的迭代规律入手,认为网络自身的本质特征
是网络全局长期的影响效果,把网络拓扑演化过程中节点、连边的自相关和协相关定义为
局部影响,再加上噪声的因素,提出一种基于拓扑结构影响力的时序链路预测算法的通用
模型 (Common Temporal Link Prediction Model, CTLPM);其次,在仅考虑拓扑局部影响的
情况下,利用节点和连边在时序动态网络上的演化规律,给出了融合局部拓扑影响力的时
序链路预测算法 (Temporal Link Prediction base on Fusion Local Structure Influence, TLP-
FLSI);最后,在 7 个真实数据集上分步骤进行实验,考察节点和连边作用的权重比例,直
接影响力和间接影响力的作用优先顺序,并且与经典时序算法进行预测性能对比,实验结
果表明了 TLP-FLSI 算法的可行性和有效性。
2. 问题描述及评价指标
常见的动态网络建模方式是根据时序对数据进行等间隔切分,把动态网络分解为一系
列的时间快照图集合,这样的建模方式相当于对动态网络在时间维度上进行采样,将动态
网络拆分成多个静态网络序列,使得静态网络的预测算法能够适用于动态网络的处理。
复杂网络通常以图的形式进行描述,静态网络通常用$ G = (V,E) $表示,其中$ V =
\{ {v_1},{v_2}, \cdots,{v_N}\} $表示节点集合;$N{\text{ = }}\left| V \right|$表示网络中节点
数量;$ E \subseteq V \times V $表示节点集合中任意两个节点连接构成的集合(有向或无
向),$E = \left\{ {\left. {{e_{ij}}} \right|i,j = 1,2, \cdots ,N} \right\}$,${e_{ij}}$表示节点间连
接关系紧密度,即边的权重,如果边不存在,${e_{ij}} = 0$,如果是无权图,则
${e_{ij}}$始终为 1,如果节点对之间是多种关系,则${e_{ij}}$可以用向量进行表示。
动态时序网络在 t ($0 < t < T$)时刻的时间快照可以定义为$ {G^t} = ({V_t},{E_t}) $,
$ {V_t} $表示 t 时刻网络中的节点集合,${E_t}$表示 t 时刻网络中的连边集合。时间范围
T 内的动态网络 G 可表示为包含一系列时间快照的集合$G = \{ {G^1},{G^2},
\cdots,{G^T}\}$。
时序链路预测是指利用动态网络的历史快照数据$G = \{ {G^1},{G^2},
\cdots ,{G^T}\}$,预测$ {G^{T + 1}} $的网络拓扑分布。如图 1(b)所示,通过时刻 1 到时
刻 T 的数据作为训练集合进行建模分析,进而实现对 t=T+1 时刻的链路预测。
图 1 复杂网络示意图
下载: 全尺寸图片 幻灯片
时序链路预测的评价指标与静态链路预测相同,也可以采用 AUC(Area Under Curve)
指标和 RS(Ranking Score)指标
[20]
对预测结果进行评价。两种指标考虑的着重点不一样,其
中,AUC 是最常用的一种评价指标,它能从整体衡量算法的精确度,而 RS 则更多地考虑
了所预测的边的排序。
AUC 指标可以认为是在 T 时刻之前的测试集中随机选择一条边的得分比 T 时刻未连
接边的分值大的概率。T 时刻之前的快照图用于训练集,得到一个预测得分,并将 T 时刻
的数据作为测试集,独立比较 n 次,其中测试集中连边的分数大于未连接边的分数则加 1
分,测试集中连边的分数等于未连接边的分数则加 0.5 分。分别用$n'$和$n''$记录上述两种
情况的个数,AUC 的值越高,说明预测的精度越大。
$$ {\text{AUC = }}\frac{{n' + 0.5n''}}{n} $$
(1)
RS 指标对所有未连接边按照相似分值大小排序,得到测试集$ {E^{\rm{P}}} $的边在
最终排序中的位置,测试集连边排名越高,排序分值越小时,说明该算法具有较好预测性
能。测试边$ e \in {E^{\rm{P}}} $的排名表示为${r_e}$,则测试边$e$的 RS 为
$$ {\text{R}}{{\text{S}}_e} = \frac{{{r_e}}}{{\left| H \right|}} $$
(2)
对于测试集中的所有边而言,对预测时刻的平均 RS 可通过遍历求和的方法得到,具
体计算为
$$ {\text{RS}} = \frac{1}{{\left| {{E^{\rm{P}}}} \right|}}\sum\limits_{e \in {E^{\rm{P}}}}
{{\text{R}}{{\text{S}}_e}} $$
(3)
3. 算法设计
首先给出时序链路预测通用模型的定义,在此模型基础上提出基于融合局部拓扑影响
力的时序链路预测算法,并对节点和连边的历史信息与演化信息进行分析。
3.1 基于网络拓扑影响力的通用时序链路预测模型
网络拓扑的影响力包括全局影响和局部影响,局部影响又可以分为直接影响和间接影
响。全局影响力可以衡量拓扑对网络整体的重要性,如中心性指标可用于表示节点和连边
的全局重要性,特征向量指标可用于刻画网络产生的长期影响;在网络动态变化时,对于
网络中的一个个实体来说,只有与它有关系的节点和连边才会在相邻的一个时刻产生短期
影响,节点度指标便可以衡量节点的直接影响力,紧密度指标则可以衡量节点的间接影响
力;另外,对时序序列数据进行建模时,还需要考虑噪声和时间衰减变化等因素。因此,
发生于 T 时刻的新事件不仅受网络的全局和局部拓扑结构的影响,还受之前时刻的历史事
件影响。由此,对于时序动态网络的预测,给出预测未来时刻得分矩阵函数的通用模型
(CTLPM)为
$$ {\text{Score}}(T) = \sum\limits_{t = 1}^{T - 1} {[\gamma (t) + (F(G(t)) + } \varepsilon (t)) \cdot
{\boldsymbol{d}}(t)] $$
(4)
其中,$ \gamma (t) $表示 t 时刻网络拓扑的全局影响力,$ F({\text{ }}) $表示 t 时刻对
网络拓扑局部影响力的计算,G(t)表示 t 时刻网络的静态图拓扑情况,$ \varepsilon (t) $表
示 t 时刻的噪声影响,$ {\boldsymbol{d}}(t) $表示时序衰减矩阵。
全局影响力可以使用网络中节点或边的各类中心性指标进行度量。节点的度中心性指
标可以更准确地表示它对邻居的影响力,不同网络的节点即使度相同,由于网络整体的最
大度不同,它们对邻居节点的影响力也不同;介数中心性利用通过连边的最短路径数量表
示该连边和在该连边上节点的重要性,如网络中 2 个社团之间的连边要比社团之间的连边
的重要性更大;特征向量中心性可以表征为节点中心性的函数,与节点连接的邻居越重
要,该节点就越重要。不同类型的网络往往具有不同的特色演化规律,可以挑选合适的中
心性指标进行度量。
局部影响力可以考虑网络拓扑中节点和连边在局部范围内的结构特征进行融合表示,
可以用节点和连边的相似性,以及演化过程中的相关性进行度量。对于 t 时刻的节点 i 和 j
的局部影响力计算为
$$ F(e{}_t(i,j)) = {\text{Si}}{{\text{m}}_t}(i,j) + {\text{Si}}{{\text{m}}_t}({e_{ij}}) + {\text{Cov}}(i,j) $$
(5)
其中,$ {\text{Si}}{{\text{m}}_t}(i,j) $表示节点 i 和节点 j 的局部相似性,可以利用
节点的影响力,如度数、集聚系数等评价指标进行度量;节点的度越大,它对邻居的影响
力越大;节点的集聚系数越大,它把邻居节点进行汇聚的能力越大,可以间接证明节点的
影响力。$ {\text{Si}}{{\text{m}}_t}({e_{ij}}) $表示连边的局部相似性,可以利用静态网络
的局部相似性计算方法,从连边上经过的路径数量越多,该连边的影响力越大。
$ {\text{Cov}}(i,j) $表示节点 i 和节点 j,以及它们之间连边的相关性,节点的自相关系数
可以考虑相邻两个时刻节点共同邻居数的比值,连边的自相关系数可以考虑相邻两个时刻
连边局部介数的比值。
为了对不同的度量指标进行特征融合,所以重新定义时序网络局部影响力计算模型为
剩余18页未读,继续阅读
资源评论
罗伯特之技术屋
- 粉丝: 3701
- 资源: 1万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功