基于时序模体注意力图卷积的动态网络链路预测算法

时序网络中的动态链路预测旨在基于历史连边信息预测未来会产生的连边,是网络分析的重要组成部分,具有极大的理论研究价值和广阔的应用场景.针对现有的动态链路预测算法大多基于一阶连边关系预测未来连边,忽略了对高阶的拓扑信息和时序通联信息的挖掘和利用问题,提出一种基于时序模体注意力图卷积的动态链路预测算法.首先,提出一种时序模体邻接矩阵构建算法,利用时序模体抽取节点间的高阶拓扑和时序关系信息;然后利用隐式调节过程对网络演化过程进行建模,并使用时序模体邻接矩阵作为传输矩阵的图卷积神经网络学习节点的低维向量表示并进行迭代更新;最后以节点间表示向量作为输入,通过计算连边发生的条件密度函数值作为依据完成动态链路预测.在多个真实时序网络数据集上的实验结果表明,所提算法可有效挖掘节点间的高阶拓扑和时序信息,提高动态链路预测效果.     

基于模体演化与社区一致性的时序链路预测方法

针对动态有向网络中的时序链路预测问题,充分分析动态有向网络中微观结构三元组模体的演化规律,使用指数平滑法季节加法（Holter-Winter-Additive）时序分析方法预测三元组模体的转换概率,引入牛顿法寻求时序分析方法中的最优参数;同时考虑到节点的社区属性对链路预测产生的影响,定义模体内节点的社区结构一致性重要指标,对三元组模体的影响力进行评估。基于此,首先使用时间序列分析方法对模体的转换概率进行预测,进而结合模体社区结构一致性的指标提出一种新的链路预测方法。使用不同的方法在三个真实的有向网络中进行验证,实验结果显示该方法能够达到更好的链路预测效果。     

融合拓扑和属性的动态网络链路预测方法

网络数据中出现的大量节点属性和随时间变化的特征,给链路预测提出了新挑战。基于注意力机制和循环神经网络对随时间演化网络进行建模,提出了DTA-LP模型。与传统的静态链路预测算法相比,DTA-LP使用LSTM捕获时序信息,动态预测可以更好应用于现实网络;与基于网络拓扑的动态链路预测算法相比,DTA-LP可以聚集高阶拓扑特征,有效挖掘网络邻域信息;与基于属性网络的动态链路预测算法相比,DTA-LP可以加权融合网络拓扑属性,提高预测精度。在4种真实数据上的实验结果表明,该方法能结合网络已有先验知识,以较高的MAP值来预测未来网络中的边,验证了模型的有效性。     

基于模体演化的时序链路预测方法

时序链路预测是动态网络分析的重要组成部分,具有极大的理论和应用价值. 传统的时序链路预测方法往往直接对边的演化规律进行分析,忽略了网络中其他微观结构的演化对链路形成的影响. 基于此分析,本文引入非负张量分解和时间序列分析对网络模体的演化规律进行研究,进而提出一种基于模体演化的链路预测方法. 在三个真实数据集上的实验结果表明,该方法能有效提高链路预测精度.     

基于三元组结构的有向网链路预测方法

当前链路预测的研究主要集中在无向网络,然而现实世界中存在大量的有向网络,忽略链路的方向会缺失一些重要信息甚至使预测失去意义,而直接将无向网络的预测方法应用于有向网络又存在预测精度降低的问题。为此,提出了一个基于三元组的有向网络链路预测算法,该算法针对有向网络和无向网络三元组结构的不同,应用势理论对三元组进行筛选,通过统计分析不同三元组闭合的可能性,以网络整体三元组闭合指数作为权重计算节点间的相似性。在9个真实数据集上的实验表明,所提方法比基准方法的预测精度提高了4.3%。     

TLP:一个动态网络中的时序链路预测算法

链路预测是网络分析的一个重要应用,网络结构在真实场景中随时间发生演变,节点间会产生新的联系或者终止连接,从而导致网络结构变化以及节点中内在的偏向发生偏移。为提升链路预测能力,提出一种基于时序特征的动态网络节点表示的链路预测算法,即每一时刻的节点表示向量由历史的表示向量计算得到,以反映节点在向量空间中的变化规律,同时结合节点间的高阶邻近特性,生成具有鲁棒性的节点向量来维护网络结构。在真实数据集上的实验结果表明,与TNE、DHPE等算法相比,该算法在链路预测任务上的预测性能具有明显提升,适用于大规模的动态网络。     

基于时序图卷积的动态网络链路预测

动态网络链路预测广泛的应用前景,使得其逐渐成为网络科学研究的热点.动态网络链路演化过程中具有复杂的空间相关性和时间依赖性,导致其链路预测任务极具挑战.提出一个基于时序图卷积的动态网络链路预测模型(dynamic network link prediction based on sequential graph convolution, DNLP-SGC).针对网络快照序列不能有效反映动态网络连续性的问题,采用边缘触发机制对原始网络权重矩阵进行修正,弥补了离散快照表示动态网络存在时序信息丢失的不足.从网络演化过程出发,综合考虑节点间的特征相似性以及历史交互信息,采用时序图卷积提取动态网络中节点的特征,该方法融合了节点时空依赖关系.进一步,采用因果卷积网络捕获网络演化过程中潜在的全局时序特征,实现动态网络链路预测.在2个真实的网络数据集上的实验结果表明,DNLP-SGC在precision, recall, AUC指标上均优于对比的基线模型.     

基于Word2vec和粒子群的链路预测算法

链路预测中普遍存在两大问题:特征提取困难和类别数据不平衡.本文借鉴文本处理中的深度学习特征提取算法和优化问题中的粒子群算法, 提出一种基于词向量的粒子群优化算法(Word2vec-PSO).该方法首先通过随机游走产生网络序列后, 利用Word2vec算法对节点序列特征提取.然后在有监督的条件下, 利用粒子群算法对提取好的特征进行筛选, 并确定重采样的参数来解决类别数据不平衡问题, 并分析了不同链路预测算法的计算复杂性.最后将本文的算法与基于相似性、基于深度学习、基于不平衡数据的3类链路预测算法, 在4个不同的时序网络中进行实证对比研究.结果表明, 本文提出的链路预测算法预测精度较高, 算法更加稳定且具有普适性.     

基于空间尺度粗粒化的异常检测方法

目前,大部分基于链路预测对社会网络进行异常检测的研究中,缺乏对异常节点演化影响的分析,且受社会网络规模以及复杂度的限制,检测效率普遍不高。针对上述问题,提出了一种基于空间尺度粗粒化和异常节点加权机制的异常检测方法。首先利用凝聚型社区发现算法Louvain对社会网络进行粗粒化得到简化网络,然后在简化网络的演化过程中识别有异常演化行为的节点,并将其异常演化过程量化,引入异常节点加权机制到链路预测方法中进行异常检测。在真实社会网络数据集VAST、Email-EU（dept1和dept2）以及Enron上,与基于LinkEvent的不同调整策略算法和NESO_ED方法进行对比。结果表明,该方法可以兼顾异常检测的稳定性和敏感性,能够更合理地描述网络演化过程,得到更好的异常检测效果。     

基于学习连续时间事件序列的动态网络链路预测

动态网络链路预测是目前复杂网络的热点研究方向,网络表示学习可以有效学习到节点的相似性,从而为链路预测提供基础.现有的动态网络表示学习方法大多先将动态网络进行离散窗口化,然后在静态网络快照图上建模,这样很难有效处理具有细粒度时间特性的动态网络.本文提出了一种可以学习动态网络中复杂的时间特性的链路预测模型,该模型使用连续时间事件序列表示动态网络,对网络中的连续时间信息和结构演化特征进行学习,并提出了基于时间注意力的信息传递机制来模拟网络中信息的扩散与聚合,最后将链路预测转化为分类问题.实验在4个真实动态网络数据集以及模拟网络上进行,并以ap和auc作为评价指标.真实网络实验结果证明该模型能够较好地学习网络演化的连续性,得到更有效的节点表示,从而提升了链路预测效果.模拟网络的实验结果表明链路预测的效果和网络模型相关,但本文模型仍可以获得较好的预测效果.     

基于矩阵分解的DeepWalk链路预测算法

现有的链路预测方法的数据来源主要是基于邻居、路径和随机游走的方法,使用的是节点相似性假设或者最大似然估计,尚缺少基于神经网络的链路预测研究。基于神经网络的一些研究表明,基于神经网络的DeepWalk网络表示学习算法可以更加有效地挖掘到网络中的结构特征,已有研究证明DeepWalk等同于分解目标矩阵。因此,提出了一种基于矩阵分解的DeepWalk链路预测算法（LPMF）。该算法首先基于矩阵分解的DeepWalk算法分解得到网络的表示向量;然后通过余弦相似度计算每对节点之间的相似度,构建目标网络的相似度矩阵;最后利用相似度矩阵,在三个真实的引文网络中进行链路预测实验。实验结果表明,提出的链路预测算法性能优于现存的20余种链路预测算法。这充分表明了LPMF能够有效地挖掘网络中节点之间的结构关联性,而且在实际网络的链路预测中能够发挥出较为优异的性能。     

相似性特征对链路预测的影响与增强

链路预测的主要任务是设计一个能够更加准确地描述给定网络机制的预测算法,从而得到更准确的预测结果。在分析现有研究成果基础上发现,网络的相似性特征对采用的链路预测方法有较大的影响：在节点间标签相似性较低的网络中,提高标签的相似性可以提高预测的准确性;而在节点间标签相似性较高的网络中,则应更加关注结构信息对于链路预测的贡献来提高预测的准确性。随后,通过对标签进行加权处理,提出带权值的标签相似性算法,在低相似性网络中能够提高链路预测的准确性。同时,在较高相似性网络中,将网络的结构信息引入到节点的相似性计算中,并通过偏好链接机制来提升链路预测的准确性。在四个真实网络上的实验结果表明,所提算法相对于标签系统间的余弦相似性（CSTS）算法、偏好链接（PA）等算法取得了最高的准确率。根据网络相似性特征,采用所提出的对应算法进行链路预测能够得到更准确的预测结果。     

基于随机投影和主成分分析的网络嵌入后处理算法

网络嵌入作为网络表示学习,近年来受到了研究人员的广泛关注。目前,已有许多基于网络结构学习网络中结点的低维向量表示的模型,如DeepWalk等,并且这些模型在结点分类和链接预测等任务中取得了良好的效果。然而,随着网络规模的增大,多个网络嵌入算法存在计算瓶颈问题。为缓解该问题,可采用诸如随机投影这类无需学习的方法,但这样可能会丢失网络结构的关键信息,致使算法性能下降。为此,文中提出了一种网络嵌入的后处理算法PPNE(Post-Processing Network Embedding),该算法结合了随机投影以及主成分分析,有效地保留了网络结构的关键信息,保持了网络结构的高阶近似性。将所提算法与其他网络嵌入算法在3个公共数据集上针对结点分类和链接预测任务进行实验对比,以验证其有效性。实验结果表明,PPNE算法在运行速度和预测性能方面相比其他算法有较大的提升,尤其是该算法在保证良好任务效果的同时,运行速度比其他基于学习的算法提升了至少两个数量级。     

基于共同邻居惩罚的复杂网络链路预测方法

链接预测是确定用户间关系的基本工具。通过相似性度量进行链路预测是一种常见的方法,提出一种基于相似度的链路预测算法,根据网络结构及拓扑特性来确定相似度,引入优化链路预测度量方法,将聚类系数作为网络结构性质。此外,并考虑共享邻域,得到较其他同类链路预测方法更好的性能。实验结果表明,提出的算法性能优于经典算法。结合在Facebook、Twitter与新浪微博等社交网络环境中的实验结果可知,SLP-CNP法较其他算法具有更优精度与效率。在未来的工作中,还可尝试在所提方法的基础上,提升在加权网络、有向网络和二部网络中的适用性。     

基于节点亲密度的链路预测算法

链路预测作为复杂网络分析的一个重要分支,在不同领域中有着广泛的应用。现有的链路预测算法通常根据共同邻居节点的结构信息来度量节点对之间的相似性,忽略了节点对与其共同邻居节点之间的连接紧密程度。针对此问题,提出了一种基于节点亲密度的链路预测算法。该算法利用边聚集系数来测量节点对与其共同邻居节点之间的紧密程度,以AUC值作为链路预测的精确度评价指标。在4个真实网络上的实验结果表明,相比于其他相似性算法,所提出的算法提高了链路预测的预测精度。     

多维社会网络中链路预测方法研究

多维社会网络中链路预测是指通过已知的网络节点以及多维社会网络结构等信息预测多维社会网络中尚未产生连边的两个节点之间产生链接的可能性.在研究有关链路预测的相关技术后,基于节点之间的相似性,提出了一种多维社会网络中的链路预测算法.算法中考虑时间因素和权重因素对于链路预测的影响,同时将多维网络中的相关技术应用到链路预测的过程...     

混合指标量子群智能社会网络事件检测方法

社会网络错综复杂,如果能够及时发现和预测当前网络可能发生的重大事件并采取有效的处置策略,将具有重大意义.链路预测的理论框架和评价方法为社会网络事件检测提供了一条有效途径.目前,链路预测的研究工作大多针对特定网络提出相似性指标,试图取得更高的链路预测精度.这些研究存在如下问题：（1）不同的相似性指标适用于不同的网络,不具有普适性;（2）独立的相似性指标无法全面反映网络演化的多样性和复杂性;（3）链路预测时未考虑网络演化过程中可能出现波动,无法进行事件检测.基于上述问题,提出一种社会网络事件检测的混合指标群智能方法IndexEvent,由最佳权重算法OWA（optimal weight algorithm）和波动检测算法FDA（fluctuationdetection algorithm）组成,可以评价不同网络的演化波动,发现网络波动异常,进行事件检测.主要工作如下：（1）提出了混合指标,并证明了基于混合指标的链路预测算法可以取得更高的预测精度;（2）基于量子粒子群算法提出了最佳权重算法OWA,以高效地确定不同网络的最佳混合指标;（3）提出了一种网络波动检测算法FDA,定量评价不同时段网络演化的波动程度,并在考虑微观因素的基础上进行改进.对不同特征的网络进行实验,结果表明,IndexEvent方法能够准确地反映事件造成的网络演化波动,有效地检测事件.     

融合节点重要性的无监督链路预测算法

提高加权网络链路预测算法精确度是研究复杂网络的基础问题之一。常用的基于局部网络结构的无监督预测方法没有考虑到重要性越高的节点越容易产生新连接,且在真实网络上中心性小的节点同样具有高度重要性。针对上述问题,提出一种融合节点重要性的无监督链路预测算法,从结构相似性和节点重要性两个角度计算新连接产生的可能性,并利用自定义系数调节影响程度。在5个真实加权网络数据集上进行实验,结果表明在解决小规模加权网络的快速预测问题上,该算法相比同类方法的预测精确度更高,有监督式链路预测方法并不适用。     

Spectral evolution in dynamic networks

We introduce and study the spectral evolution model, which characterizes the growth of large networks in terms of the eigenvalue decomposition of their adjacency matrices: In large networks, changes over time result in a change of a graph’s spectrum, leaving the eigenvectors unchanged. We validate this hypothesis for several large social, collaboration, rating, citation, and communication networks. Following these observations, we introduce two link prediction algorithms based on the learning of the changes to a network’s spectrum. These new link prediction methods generalize several common graph kernels that can be expressed as spectral transformations. The first method is based on reducing the link prediction problem to a one-dimensional curve-fitting problem which can be solved efficiently. The second algorithm extrapolates a network’s spectrum to predict links. Both algorithms are evaluated on fifteen network datasets for which edge creation times are known.     

基于相似度传播的二分网络链接预测

链接预测是复杂网络分析中的重要研究问题。提出了一个基于链接相似度传播的二部图链路预测算法。该算法将链接相似度得分通过随机游走在网络中进行传播和更新。在该算法中,网络里的每一条边都被分配一个基于相似度的传播概率。不同部分的节点之间的链接相似性得分根据它们的边的传播概率来传播。在不同大小的真实社交网络上的实验结果证明,该算法可以取得比其他算法更精确的预测结果。