没有合适的资源?快使用搜索试试~ 我知道了~
融合用户行为同步指标的链路预测研究.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 52 浏览量
2022-12-15
14:27:07
上传
评论
收藏 310KB DOCX 举报
温馨提示
试读
16页
融合用户行为同步指标的链路预测研究.docx
资源推荐
资源详情
资源评论
真实世界存在各种复杂系统,如果将复杂系统的主要元素抽象为节点和连边,就可将
其抽象为复杂网络,如科学家合作网络
[1]
、万维网络
[2]
、社交网络
[3]
和交通网络
[4]
等。当网
络的某些结构信息缺失时,可应用链路预测
[5]
方法来分析节点之间不确定的或潜在的链接
关系
[6]
。如在线社交服务中,链路预测可以挖掘社交用户的兴趣并挖掘用户之间的潜在关
系,为用户推荐感兴趣的朋友
[7]
。在蛋白质新陈代谢网络中,链路预测可推断蛋白质之间
的交互作用,从而有针对性地进行实验来节约成本
[8]
。在科学家合作网络中,可以预测科
学家的合作模式和强度,对理解科研合作的组织方式具有重要的作用
[9]
。
链路预测研究中,最经典的方法是节点局部结构的相似性,如共同邻居(common
neighbors, CN)、Adamic-Adar 指标
[10]
、资源分配指标(resource allocation, RA)
[11]
、局部路径
相似性指标
[12]
及局部随机游走的相似性指标
[13]
等,但通常不考虑节点之间链接的权重大
小。真实复杂系统中元素之间的交互强度往往也蕴含着关键信息,可将其抽象为加权网络
进行分析,因此链路预测研究开始重视如何充分利用网络连边的权重信息。文献[14]提出
了基于加权共同邻居指标(weighted common neighbors, WCN)、加权 Adamic-Adar 指数
(weighted Adamic-Adar, WAA)及加权资源分配指标(weighted resource allocation, WRA)等链
路预测方法,通过对多个实证网络的研究发现了加权链路预测中“弱链接的强作用”。文献
[15]提出了一种基于可靠线路的链路预测方法(rWCN, rWAA, rWRA),通过对可靠路线赋予
更高权重来达到更鲁棒的预测性能。文献[16]提出了一种局部加权路径指标,精细利用路
径的权重特征来实现准确预测。文献[17]改进了结构算法使其更适用于有向加权网络的链
路预测,如改进的共同邻居算法(modified common neighbors,MCN)、改进的 Jaccard 系数
(MJC)、改进的 Adamic Adar 算法(modified Adamic Adar, MAA)和改进的优先链接算法
(modified preferentialattach, MPA)。文献[18]设计了一种高效共同邻居指标,该指标通过分
析共同邻居节点的拓扑有效性对连边端点两侧资源分配过程的影响来刻画节点间相似性,
在 15 个实际网络数据实验中表明,该方法具有较高的预测精度。文献[19]提出了一种链路
权重预测的无监督混合方法,结合网络的权重一致性和节点的链路权重潜在特征可有效解
决链路权重预测问题。文献[20]通过对网络中真实存在的连边进行异常度排名,将链路预
测应用在大规模瘫痪状态下的电力系统的恢复,该方法不仅可以快速连通电源发电机,也
能及时恢复重要线路。文献[21]提出了基于链路线形的危险链路预测模型,对新加入交通
网络的链路进行预测,从而在碰撞发生之前进行相应的整治,该模型可有效准确地对危险
链路进行预测。
虽然上述研究相对于无权链路预测方法都取得了更好的性能,但是这些方法仅仅是使
用连边的权重信息,没有考虑挖掘该连边权重形成的时序信息。在很多加权网络尤其是社
会网络中,连边的权重是由该连边连接的两个节点多次互动形成的,这种互动行为具有一
定的时间特性,也是人类动力学研究的重要内容
[22]
。经过研究发现,两个节点行为的时间
同步性往往是由于两个节点存在链接造成的
[23]
,因此可利用两个节点的行为同步性来反推
它们之间是否存在链接关系。目前该类方法已经广泛应用于网络结构的重构研究中
[24]
。文
献[25]提出检测嘈杂实验数据中相位同步的方法,实验发现该方法可有效衡量网络群体中
个体的同步程度,并探究了同步性如何影响个体之间的关系。文献[26]利用鸽子飞行轨迹
的时序相关性,在成员之间重构了完整明确的网络层次结构。文献[27]分析了时间滞后衰
减作用对于网络重构的潜在影响,取得了较好的网络重构效果。文献[28]通过对具有同步
和异步动态特性的网络进行研究,揭示了机器学习方法可以重构交互网络并识别网络内在
的动力学特征。文献[29]根据由个人状态的时间序列组成的传播数据,重建了人与人之间
牢固关系的主干,并成功地将该方法整合到了有针对性的免疫策略中。上述研究都是将节
点行为同步信息应用在网络重构中,目前将此类信息应用于链路预测的研究还很少见。
网络重构和链路预测通常采用不同的研究范式和算法,本文尝试将节点同步性信息这
一经典网络重构的方法引入到链路预测领域,提出一种网络拓扑结构上融合节点行为同步
指数的链路预测方法。该方法将节点局域结构相似性(共同邻居指标)和节点行为在时间上
的相似性(行为同步指数)相融合,充分利用节点之间的拓扑结构域和行为时间域特征。相
对于仅使用网络域基于结构和权重的主流方法,其链路预测效果更显著。同时,为了探究
局域结构和同步指数对链路预测的共同关系,尝试使用一个可变参数调整两者的融合比
率,实验表明可变参数在较大范围内都不会影响链路预测的结果,说明了本文所提方法具
有较好的鲁棒性。
1. 问题描述与评价指标
1.1 问题描述
定义加权网络 G=(V,E,W)G=(V,E,W),其中 VV 是所有节点的集合,EE 是网络中连边
的集合,WW 是网络中连边权重的集合。定义 TT 为网络中最大与最小时间戳的差值,将
时间进行相对时间处理后基于[0,T][0,T]将整个数据划分为两段时间间隔[0,Tn][0,Tn]和
[Tn+1,T][Tn+1,T]。将[0,Tn][0,Tn]时间上数据的连边集合作为训练集 ETET,将
[Tn+1,T][Tn+1,T]时间上的连边集合作为测试集 EPEP。这两个边集之间的关系为:
ET∪EP=EET∪EP=E,ET∩EP=ϕET∩EP=ϕ,且训练集 ETET 与测试集 EPEP 的样本为 9∶
1。在科学家合作网络中,时效信息按年计。在短信网络中时效信息按秒计。在本研究中,
待分析的所有节点既在一个周期内存在,也在第二个周期内存在,即[Tn+1,T][Tn+1,T]中出
现的所有节点都是[0,Tn][0,Tn]上已经存在的节点。对于仅在[0,Tn][0,Tn]和
[Tn+1,T][Tn+1,T]中出现的节点本文做了删除处理。
1.2 评价指标
Precision 只关注前 L 条高分连边的性能,根据出现连边可能性的分数值从大到小排
序,如果有 m 条边是属于存在边集合,那么 Precision 定义为:
precision=mLprecision=mL
(1)
由该式可知,m 越大则 Precision 值越高,预测越准确。
2. 链路预测方法
2.1 基于共同邻居的相似性指标
1) CN 指标
共同邻居(CN)指标是通过计算两个节点共同邻居的数量来判断节点相似性。定义节点
xx 的邻居集合 Γ(x)Γ(x),节点 yy 的邻居集合为 Γ(y)Γ(y),共同邻居指标定义为:
SCNxy=|Γ(x)∩Γ(y)|SxyCN=|Γ(x)∩Γ(y)|
(2)
一般来说,节点 xx 和节点 yy 之间的共同邻居越多,连边的分数值越大,节点的相似
性越大。
2) AA 指标
在共同邻居的基础上,考虑两端节点度的影响,则演变为 AA 指标。AA 指标的思想
是度小的共同邻居节点贡献大于度大的共同邻居节点。该方法通过共同邻居的度,为每个
节点附上一个权重值。这个值为该节点度的对数的倒数,定义为:
SAAxy=∑z∈Γ(x)∩Γ(y)1logkzSxyAA=∑z∈Γ(x)∩Γ(y)1logkz
(3)
式中,kzkz 表示 xx 和 yy 的共同邻居节点 zz 的度。
3) RA 指标
RA 与 AA 相似,都对节点度大的共同邻居的贡献进行抑制,即节点度越小,对网络
连接产生的贡献就越大,RA 指标的抑制程度相对更大。因此,当网络的节点的度都较小
时,两者区别不大。而当网络节点中存在较大度时,因为对度大节点有更高的抑制性,所
以 RA 展现出相对较好的预测性能
[11]
。RA 指标定义如下:
SRAxy=∑z∈Γ(x)∩Γ(y)1kzSxyRA=∑z∈Γ(x)∩Γ(y)1kz
(4)
2.2 基于共同邻居的加权相似性指标
加权网络进行链路预测时,不仅要考虑网络的拓扑结构,也要考虑连边的权重,才能
取得较好的预测效果。将 CN、AA、RA 扩展到加权的形式,就可以将连边权重的信息应
用到加权网络的链路预测中。常用的 3 种加权指标 WCN、WAA 和 WRA 的定义为如下形
式:
1) WCN 指标:
SWCNxy=∑z∈Γ(x)∩Γ(y)W(x,z)+W(z,y)SxyWCN=∑z∈Γ(x)∩Γ(y)W(x,z)+W(z,y)
(5)
式中,W(x,z)W(x,z)为两节点 x 和 zz 的连边权重;W(z,y)W(z,y)为两节点 zz 和 y 的
连边权重。
2) WAA 指标:
SWAAxy=∑z∈Γ(x)∩Γ(y)W(x,z)+W(z,y)log(1+s(z))SxyWAA=∑z∈Γ(x)∩Γ(y)W(x,z)+W(z,y)log(1+s(z))
(6)
式中,s(z)s(z)表示邻居节点 zz 的强度;WAA 根据每个共同邻居的强度值进行了加
权。
3) WRA 指标:
SWRAxy=∑z∈Γ(x)∩Γ(y)W(x,z)+W(z,y)s(z)SxyWRA=∑z∈Γ(x)∩Γ(y)W(x,z)+W(z,y)s(z)
(7)
式中,WRA 是 WCN 的另一种权重赋予方式,分母不再采用强度的对数,而直接采
用节点强度进行了加权。
2.3 基于可靠路线的加权相似性指标
在加权网络链路预测中,如何利用权重信息是研究重点。在通信网络中,信息的传输
往往需要依赖最可靠的线路将数据包从源节点传输到目标节点,以保证数据传输过程中不
被损坏。受通信网络的启发,文献[15]提出了可靠路线加权指标的链路预测方法,假设所
有连边的权重都是独立的,通过连边权重的乘积计算两个节点连边的相似性得分,定义如
下:
1) 加权可靠路线 CN 指标(rWCN):
SrWCNxy=∑z∈Γ(x)∩Γ(y)W(x,z)W(z,y)SxyrWCN=∑z∈Γ(x)∩Γ(y)W(x,z)W(z,y)
(8)
2) 加权可靠路线 AA 指标(rWAA):
SrWAAxy=∑z∈Γ(x)∩Γ(y)W(x,z)W(z,y)log(1+s(z))SxyrWAA=∑z∈Γ(x)∩Γ(y)W(x,z)W(z,y)log(1+s(z))
(9)
3) 加权可靠路线 RA 指标(rWRA):
SrWRAxy=∑z∈Γ(x)∩Γ(y)W(x,z)W(z,y)s(z)SxyrWRA=∑z∈Γ(x)∩Γ(y)W(x,z)W(z,y)s(z)
(10)
上述 3 种指标利用了可靠路径的计算思路,改进了 WCN、WAA、WRA 指标,并且
在没有提高计算复杂度的前提下,对可靠路线赋予了更高的权重,从而提高了链路预测的
准确性。
2.4 基于行为同步指数的相似性指标
在很多真实社会网络中,通过两个节点多次互动形成的权重是普遍存在的,并且这种
互动行为往往具有一定的时间特性,该时间特性会通过两个节点的链接而产生
[22]
,因此可
利用这两个节点时间上的同步性来推断它们之间的潜在链接关系。
从链路预测的角度分析,网络中节点之间的互动存在时间上的延迟,这种时间特性可
以作为一种同步现象来衡量节点的行为同步性。如果节点之间存在链接,它们之间的交互
时间间隔越短,则这两个节点的行为将越趋于同步,以此可推断他们未来存在链接的概率
就越大。如节点 xx 给节点 yy 发消息,节点 yy 每次都立即回复,说明两个节点产生链接
的可能性极大。如果节点 xx 给节点 zz 发消息,节点 zz 经常不回复或是时间间隔很长才回
复,那么这两个节点产生链接的可能性就较小。因此,在不知道两个节点之间是否存在链
接的情况下,观察两个节点之间的行为同步性可以推断他们之间是否存在联系。
剩余15页未读,继续阅读
资源评论
罗伯特之技术屋
- 粉丝: 3676
- 资源: 1万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功