基于高阶近似的链路预测算法

目前大部分链路预测算法只研究了节点与邻居节点之间的一阶相似性，没有考虑节点与邻居的邻居节点之间的高阶相似性关系。针对此问题，提出一种基于高阶近似的链路预测算法（LP-HOPA）。首先，求出网络的归一化邻接矩阵和相似度矩阵；其次，利用矩阵分解的方法将相似度矩阵进行分解，得到网络节点的表示向量以及其上下文的表示向量；然后，通过高阶网络表示学习的网络嵌入更新（NEU）算法对原始相似度矩阵进行高阶优化，并利用归一化的邻接矩阵计算出更高阶的相似度矩阵表示；最后，在四个真实的数据集上进行大量的实验。实验结果表明，与原始链路预测算法相比，大部分利用LP-HOPA优化后的链路预测算法准确率提升了4%到50%。此外，LP-HOPA算法能够将基于低阶网络局部结构信息的链路预测算法转换为基于节点高阶特征的链路预测算法，在一定程度上肯定了基于高阶近似链路预测算法的有效性和可行性。     

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

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

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

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

融合模体图神经网络和自编码器的链路预测

链路预测是网络数据挖掘的一项基本任务,已有很多相关的研究成果。由于图神经网络研究的深入发展,使得相关的模型可以更加有效学习网络的重要特征,在链路预测等任务中取得了很好的预测效果。然而,不同于深度学习中CNN模型,已有的图神经网络模型中仅聚合了节点的一阶邻居信息,未充分考虑邻居节点之间的拓扑结构特性。在此基础上,提出了基于模体的图神经网络链路预测模型。该模型采用自编码器结构,在编码过程中,通过模体构建节点的邻接矩阵,进而得到节点的模体邻域,依照每一类模体的邻域聚合邻居信息,通过非线性变换得到节点的表示,最后拼接每一类模体下节点的表示。然而由于不同的模体结构在网络中重要度有所不同,利用注意力网络给出表达不同模体的注意力权重,连接注意力网络给出节点的向量表示。在解码过程中,通过计算节点间的相似性重构网络。在几个引文合作者网络上的实验结果表明,该方法在两个指标上优于大多数基准算法,有效地提高了网络链路预测的准确度。     

基于社团多特征融合嵌入表示的时序链路预测方法

时序动态网络在静态网络基础上综合了时间属性的概念,包含了网络结构的复杂性、动态性等内涵,是研究复杂网络链路预测问题的较优思维对象,因在现实世界中具有较高应用价值而备受关注。目前大部分传统方法研究对象仍局限于静态网络,存在对网络时域演化信息利用不充分、时间复杂度较高等问题。结合社会学理论,提出一种基于社团多特征融合嵌入表示的时序链路预测方法,该方法的核心思想是通过分析网络动态演化特性,在社团范围内学习节点的嵌入表示向量,融合多特征以衡量节点间连边的生成概率。利用网络集体影响力的方法对节点和连边的权值进行计算,基于集体影响的连边权值进行社团划分,将网络划分为若干个社团子图,得到基于集体影响的相似性指标。在社团范围内,利用有偏的随机游走,结合梯度优化的Skip-gram方法获取所有节点的嵌入表示向量,得到基于社团范围游走的相似性指标。融合节点的集体影响、社团范围节点的多个中心性特征和学习到的节点表示向量,得到多特征融合的相似性指标,3 种新指标都可以用于衡量节点之间形成连边的概率。对比基于移动平均、嵌入表示、图神经网络等经典时序链路预测方法,在 6 个真实数据集上的实验结果表明,所提基于社团多特征融合的方法在 AUC评价标准下取得更优的预测性能。     

基于节点匹配度的动态网络链路预测方法

现实世界存在众多真实网络,研究真实网络中的动态演化趋势和时序性特征是热点问题。链路预测技术作为网络科学领域重要研究工具可通过挖掘历史连边信息推测网络演化规律,进而对未来连边进行预测。通过分析动态真实网络中的拓扑结构演化,发现通过分析网络拓扑中节点间的交互性和匹配度问题能够更充分捕捉网络的动态特征,提出一种基于节点匹配度的动态网络链路预测方法。该方法对网络节点的属性特征进行分析,定义基于原生影响力和次生影响力的节点重要性量化方法;引入时间衰减因子,刻画不同时刻网络拓扑对连边形成的影响程度;结合节点重要性和时间衰减因子定义动态节点匹配度（TMDN,temporal matching degree of nodes）方法,用于衡量节点对之间未来形成连边的可能性。在5个真实动态网络数据集中的实验结果表明,相比现有 3 类主流动态网络链路预测方法,所提方法在 AUC 和Ranking Score 两种评价标准下均取得更优的预测性能,预测结果最高提升 42%,证明了节点间存在着交互匹配优先级,同时证实了节点原生影响力和次生影响力的有效性。     

融合快速注意力机制的节点无特征网络链路预测算法

链路预测是网络科学的一个重要研究分支,旨在推断网络中节点对间存在连边的可能性.现实生活中很多事物关系都能够通过网络科学进行描述,很多实际问题都可以转化为链路预测问题.节点无特征网络链路预测算法可向有向网络、加权网络、时序网络等更复杂的网络推广.但现有的链路预测算法面临着网络结构信息挖掘不够深入、特征提取过程受人为主观意...     

基于密集连接卷积神经网络的链路预测模型

现有的基于网络表示学习的链路预测算法主要通过捕获网络节点的邻域拓扑信息构造特征向量来进行链路预测，该类算法通常只注重从网络节点的单一邻域拓扑结构中学习信息，而对多个网络节点在链路结构上的相似性方面研究不足。针对此问题，提出一种基于密集连接卷积神经网络（DenseNet）的链路预测模型（DenseNet-LP）。首先，利用基于网络表示学习算法node2vec生成节点表示向量，并利用该表示向量将网络节点的结构信息映射为三维特征数据；然后，利用密集连接卷积神经网络来捕捉链路结构的特征，并建立二分类模型实现链路预测。在四个公开的数据集上的实验结果表明，相较于网络表示学习算法，所提模型链路预测结果的ROC曲线下方面积（AUC）值最大提高了18个百分点。     

基于二阶图卷积自编码器的图表示学习

图卷积自编码器是一类高效的图表示学习模型,在链路预测等任务中具有出色性能。然而现有模型大多依赖图卷积网络对邻接矩阵和属性矩阵进行编码,未充分利用二阶信息等高阶结构特征。针对上述问题,提出了基于二阶信息的图卷积自编码器模型SeVGAE。首先使用图卷积和二阶图卷积生成变分自编码器的均值和方差,然后学习嵌入向量表示原始图的混合概率分布,最后使用内积解码器恢复拓扑结构。在链接预测任务中,SeGVAE表现优于基线模型,Citeseer数据集上的AUC和AP相较原始的VGAE分别提升了3.26%和2.56%。实验结果表明,二阶信息的引入能够在低维嵌入中保留更丰富的图信息,提升模型性能。模型在处理属性信息不足、拓扑信息不准确的图数据时具有较为明显的优势,在边缘和属性均缺失40%的极端情况下,SeVGAE的AUC和AP相较VGAE提升4.79%和3.47%。     

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

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

基于对抗图卷积网络的链接预测模型

大部分的链接预测模型在挖掘节点相似性时过于依赖已知的链接信息,但在真实世界中,已知的观测链接数量通常较少.因此,为了提高模型的鲁棒性,需要提高解耦模型对链接信息的依赖并挖掘节点的潜在特征.文中考虑节点特征和链接之间的潜在关系,提出基于对抗图卷积网络的链接预测模型.首先利用节点间的相似性度量填充邻接矩阵中部分未知链接,缓解链接稀疏对图卷积模型的影响.再利用对抗网络深度挖掘节点特征和链接之间的潜在联系,降低模型对链接的依赖.在真实数据集上的实验表明,文中模型在链接预测问题上具有较好的表现力,在链接稀疏的情况下性能依旧较稳定,同时适用于大规模数据集.     

Cold-Start Link Prediction via Weighted Symmetric Nonnegative Matrix Factorization with Graph Regularization

Link prediction has attracted wide attention among interdisciplinary researchers as an important issue in complex network. It aims to predict the missing links in current networks and new links that will appear in future networks. Despite the presence of missing links in the target network of link prediction studies, the network it processes remains macroscopically as a large connected graph. However, the complexity of the real world makes the complex networks abstracted from real systems often contain many isolated nodes. This phenomenon leads to existing link prediction methods not to efficiently implement the prediction of missing edges on isolated nodes. Therefore, the cold-start link prediction is favored as one of the most valuable subproblems of traditional link prediction. However, due to the loss of many links in the observation network, the topological information available for completing the link prediction task is extremely scarce. This presents a severe challenge for the study of cold-start link prediction. Therefore, how to mine and fuse more available non-topological information from observed network becomes the key point to solve the problem of cold-start link prediction. In this paper, we propose a framework for solving the cold-start link prediction problem, a joint-weighted symmetric nonnegative matrix factorization model fusing graph regularization information, based on low-rank approximation algorithms in the field of machine learning. First, the nonlinear features in high-dimensional space of node attributes are captured by the designed graph regularization term. Second, using a weighted matrix, we associate the attribute similarity and first order structure information of nodes and constrain each other. Finally, a unified framework for implementing cold-start link prediction is constructed by using a symmetric nonnegative matrix factorization model to integrate the multiple information extracted together. Extensive experimental validation on five real networks with attributes shows that the proposed model has very good predictive performance when predicting missing edges of isolated nodes.     

融合链接预测相似度矩阵的属性网络嵌入算法

在属性网络中,与节点相关联的属性信息有助于提升网络嵌入各种任务的性能,但网络是一种图状结构,节点不仅包含属性信息还隐含着丰富的结构信息。为了充分融合结构信息,首先通过定义节点的影响力特性、空间关系特征;然后根据链接预测领域基于相似度的定义构建相似度矩阵,将节点二元组中的关联向量映射到相似度矩阵这一关系空间中,从而保留与节点相关的结构向量信息;再基于图的拉普拉斯矩阵融合属性信息和标签特征,将上述三类信息集成到一个最优化框架中;最后,通过二阶导数求局部最大值计算投影矩阵获取节点的特征表示进行网络嵌入。实验结果表明,提出的算法能够充分利用节点二元组的邻接结构信息,相比于其他基准网络嵌入算法,本模型在节点分类任务上取得了更好的结果。     

基于深度神经网络和门控循环单元的动态图表示学习方法

学习图中节点的潜在向量表示是一项重要且普遍存在的任务,旨在捕捉图中节点的各种属性。大量工作证明静态图表示已经能够学习到节点的部分信息,然而,真实世界的图是随着时间的推移而演变的。为了解决多数动态网络算法不能有效保留节点邻域结构和时态信息的问题,提出了基于深度神经网络（DNN）和门控循环单元（GRU）的动态网络表示学习方法DynAEGRU。该方法以自编码器作为框架,其中的编码器首先用DNN聚集邻域信息以得到低维特征向量,然后使用GRU网络提取节点时态信息,最后用解码器重构邻接矩阵并将其与真实图对比来构建损失。通过与几种静态图和动态图表示学习算法在3个数据集上进行实验分析,结果表明DynAEGRU具有较好的性能增益。     

基于节点相似性的链接预测

链接预测是图数据挖掘中的一个重要问题。它是通过已知的网络结构等信息预测和估计尚未链接的两个节点存在链接的可能性。目前大部分基于节点相似性的链接预测算法只考虑共同部居节点的个体特征,针对目前预测。算法对共同部居节点间相互关系的考虑不足,提出了一种新算法:节点引力指数算法。该算法在保持低时间复杂度的同时,提高了预测的准确率。通过多个现实网络实验证实了算法的预测效果。     

单时序特征图卷积网络融合预测方法

近年来,图神经网络逐渐成为深度学习领域广泛讨论的话题和研究的重点,但大多数研究都是基于图节点,在存在多维属性的前提下进行分类和回归预测,对单时序特征的图节点预测并不能产生理想的效果。本文提出一种时序图卷积网络算法,可以在复杂图网络中,只根据节点单一特征的时序序列,实现对该特征的预测。算法通过在传统图卷积网络中对邻接矩阵参数化,解决单一特征条件下的参数退化问题,并结合长短时记忆网络的序列学习方法,将时序信息融入到训练过程中,提高训练精度。在交通流量数据集PeMS和Los上的实验表明,其预测精度要优于GCN、T-GCN、GRU、LSTM等主流算法。     

基于重启随机游走的图自编码器

针对现有的图自编码器无法捕捉图中节点之间的上下文信息的问题,提出基于重启随机游走的图自编码器.首先,构造两层图卷积网络编码图的拓扑结构和特征,同时进行重启随机游走捕捉节点之间的上下文信息;其次,为了聚合重启随机游走和图卷积网络获得的表示,设计自适应学习策略,根据两种表示的重要性自适应地分配权重.为了证明该方法的有效性,将图最终的表示应用于节点聚类和链路预测任务.实验结果表明,与基线方法相比,提出的方法实现了更先进的性能.     

考虑时空相似性的动态图卷积神经网络交通流预测

高精度的交通流预测对于大型城市的交通管理和智慧出行具有重要作用,而交通流动态时空相关性的挖掘则是提高预测精度的关键.针对现有研究中存在的对交通流在不同时间尺度下呈现出的高度相似性,以及处于相似功能区的非邻近节点间交通流变化的相似性考虑不足的问题,构建考虑时空相似性的动态图卷积神经网络(dynamic graph convolution neural network considering spatio-temporal similarity,STS-DGCN).以相邻时段、日和周等多时间尺度下的数据输入张量表达交通流数据的时间相似性,以路网节点间距离度量、相似性度量、自适应嵌入、动态相关性等多属性特征的邻接矩阵表达交通流数据的时空相似性,进而基于这些邻接矩阵构建反映路网节点时空动态变化的动态图,并设计相应的时空特征挖掘算法.在公开数据集上的实验结果表明,所提出模型的预测结果优于目前较为先进的对比基线模型,具有更高的预测精度.     

Temporal link prediction in multi-relational network

Link prediction problem in complex networks has received substantial amount of attention in the field of social network analysis. Though initial studies consider only static snapshot of a network, importance of temporal dimension has been observed and cultivated subsequently. In recent times, multi-domain relationships between node-pairs embedded in real networks have been exploited to boost link prediction performance. In this paper, we combine multi-domain topological features as well as temporal dimension, and propose a robust and efficient feature set called TMLP (Time-aware Multi-relational Link Prediction) for link prediction in dynamic heterogeneous networks. It combines dynamics of graph topology and history of interactions at dyadic level, and exploits time-series model in the feature extraction process. Several experiments on two networks prepared from DBLP bibliographic dataset show that the proposed framework outperforms the existing methods significantly, in predicting future links. It also demonstrates the necessity of combining heterogeneous information with temporal dynamics of graph topology and dyadic history in order to predict future links. Empirical results find that the proposed feature set is robust against longitudinal bias.