基于网络表示学习的链路预测算法

网络是表达对象之间复杂联系的重要形式,广泛存在。而链路预测作为网络分析的重要方法,具有很大的研究意义和应用价值。传统的链路预测算法普遍是基于邻接矩阵的稀疏表示方案而设计,计算效率低且扩展性差。首先引入网络表示学习的概念,创新性地提出基于几何布朗运动的随机游走算法GbmRw,然后进一步设计出网络表示学习算法GBMLA,实现更具区分能力与表达能力的网络表示,最后以节点表示向量的欧式距离来表征节点之间的相似性,从而预测其链路存在的可能性。不同领域的多个网络中进行反复实验的结果表明,该算法较之于基于原始网络设计的传统算法,预测效果得到了明显的提升,也进一步肯定了网络表示学习对于链路预测工作的重要意义。     

基于网络表示学习与随机游走的链路预测算法

现有的基于随机游走链路预测指标在无权网络上的转移过程存在较强随机性,没有考虑在网络结构上不同邻居节点间的相似性对转移概率的作用。针对此问题,提出一种基于网络表示学习与随机游走的链路预测算法。首先,通过基于深度学习的网络表示学习算法——DeepWalk学习网络节点的潜在结构特征,将网络中的各节点表征到低维向量空间;然后,在重启随机游走（RWR）和局部随机游走（LRW）算法的随机游走过程中融合各邻居节点在向量空间上的相似性,重新定义出邻居节点间的转移概率;最后,在5个真实数据集上进行大量实验验证。实验结果表明：相比8种具有代表性的基于网络结构的链路预测基准算法,所提算法链路预测结果的AUC值均有提升,最高达3.34%。     

基于改进随机游走的网络表示学习算法

现有的基于Word2vec的网络表示学习（NRL）算法使用随机游走（RW）来生成节点序列,针对随机游走倾向于选择具有较大度的节点,生成的节点序列不能很好地反映网络结构信息,从而影响表示学习性能的问题,提出了基于改进随机游走的网络表示学习算法。首先,使用RLP-MHRW算法生成节点序列,它在生成节点序列时不会偏向大度节点,得到的节点序列能更好地反映网络结构信息;然后,将节点序列投入到Skip-gram模型得到节点表示向量;最后,利用链路预测任务来测度表示学习性能。在4个真实网络数据集上进行了实验。在论文合作网络arXiv ASTRO-PH上与LINE和node2vec算法相比,链路预测的AUC值分别提升了8.9%和3.5%,其他数据集上也均有提升。实验结果表明,RLP-MHRW能有效提高基于Word2vec的网络表示学习算法的性能。     

保持Motif结构的网络表示学习*

随着信息技术的广泛应用,网络在人们日常的生活中变得无处不在。网络表示学习算法是最近研究网络的一个热门领域,它旨在保留网络拓扑结构信息的同时,将网络映射到一个潜在、低维度的向量空间。网络Motif,在网络分析中具有重要的意义,然而之前提出的网络表示学习算法绝大多数只考虑了节点的邻域属性或邻近性,而忽略了节点的Motif结构信息。因此,基于上述考虑,提出了算法"保持Motif结构的网络表示学习",使得在学习网络节点向量表示时能够更加侧重地考虑网络Motif的结构。算法首先计算出基于Motif的网络权重矩阵;接着求得网络中每个节点的基于Motif的个性化PageRank预估值;最后进行MotifWalk得到游走路径,从而能够运用Word2Vec模型来得到网络的向量表示。通过与三个经典的网络表示算法比较,发现在稠密以及Motif结构丰富的网络中,提出的算法表现得更好。     

基于随机游走的网络表示学习推荐算法

根据网络结构中的连接关系得到节点的向量表示,进而将节点的向量表示应用于推荐算法可有效提升其建模能力。针对推荐系统中的同质网络,提出结合随机游走的网络表示学习推荐算法。以DeepWalk算法为基础,在随机游走过程中根据节点重要性设定节点游走序列数,并设置终止概率以控制游走长度优化采样结果,在网络表示学习过程中将SkipGram模型融合节点属性信息,同时考虑上下文节点离中心节点的距离获得更准确的推荐结果。实验结果表明,该算法相比DeepWalk、Node2vec等算法具有更高的推荐准确度,并且较好地解决了冷启动问题。     

基于网络表示学习的论文影响力预测算法

基于图的随机游走算法在预测论文影响力时,仅利用学术网络的全局结构信息而未考虑局部结构信息,对预测准确率造成影响。针对该问题,提出一种基于异构学术网络表示学习和多变量随机游走的论文影响力预测算法。通过构建异构学术网络表示模型,将网络中的论文、作者和期刊/会议等不同类型的节点表征到同一个低维向量空间中,同时保留网络的局部结构信息,将节点的向量相似度应用于多变量随机游走方法,实现对论文影响力的准确预测。在AMiner网站公开数据集上的实验结果表明,相比于PageRank、FutureRank等算法,该算法的预测准确性较高。     

关联文本信息的网络表示学习推荐算法

通过基于随机游走的网络表示学习算法得到节点的低维嵌入向量,进而将其应用于推荐系统是推荐领域很流行的研究方向.针对当前基于随机游走的网络表示学习算法仅着重考虑了网络结构特性而忽略文本信息的问题,提出一种关联文本信息的网络表示学习推荐算法.首先在随机游走阶段,考虑到了节点文本间的相似度,联合结构和文本信息对下一游走节点进行...     

结合属性信息的二分网络表示学习

现有的网络表示学习算法主要是针对同质网络或异质网络设计的,而忽略了在推荐系统、搜索引擎和问答系统等领域出现的二分网络的特殊特征以及这类网络所携带着的非常丰富的属性信息.为了解决上述问题,提出了一种结合属性信息的二分网络表示学习方法(ABNE).该方法首先将连边分解成邻居节点间的间接关系集,嵌入显式关系,接着通过余弦相似...     

基于网络表示学习的区块链异常交易检测

由于具有巨大的流通市值、庞大的用户量和账户匿名性的特点,区块链交易频繁受到盗窃、庞氏骗局、欺诈等异常行为的威胁。针对区块链异常交易,提出一种网络表示学习模型DeepWalk-Ba用于特征提取,以比特币为例,对区块链交易的网络结构和属性进行学习,从交易的邻域结构中挖掘隐含信息作为节点特征,再使用5种有监督和1种无监督的机器学习算法进行异常检测。实验表明,有监督模型随机森林表现最好,达到了99.3%的精确率和86.4%的召回率,比使用传统的特征提取方法的异常检测模型具有更好的检测效果。     

基于随机游走的图嵌入研究综述

近年来,图嵌入已经成为图神经网络领域研究的热点。图嵌入作为图任务分析的一种重要手段,将图的高维非欧信息编码到低维向量空间中,从而提升下游任务的性能和效率。为了及时掌握当前基于随机游走的图嵌入方法的研究现状,通过归纳与整理,对现有的经典模型进行介绍与分类,主要分为基于经典随机游走的模型和基于属性游走的模型;然后对每一种模型解决的问题、算法思想、模型策略、优缺点和应用场景进行了详细的归纳与分析,并在几种常见的数据集上评估了部分模型的性能。通过研究发现,当前的基于随机游走的图嵌入亟待解决四个方面的问题：属性选择、可扩展性、嵌入维度选择和可解释性,针对这些问题,图嵌入需要建立一致的理论框架,为后面的研究提供可参考的标准。     

图嵌入模型综述

图分析用于深入挖掘图数据的内在特征,然而图作为非欧几里德数据,传统的数据分析方法普遍存在较高的计算量和空间开销。图嵌入是一种解决图分析问题的有效方法,其将原始图数据转换到低维空间并保留关键信息,从而提升节点分类、链接预测、节点聚类等下游任务的性能。与以往的研究不同,同时对静态图和动态图嵌入文献进行全面回顾,提出一种静态图嵌入和动态图嵌入通用分类方法,即基于矩阵分解的图嵌入、基于随机游走的图嵌入、基于自编码器的图嵌入、基于图神经网络(GNN)的图嵌入和基于其他方法的图嵌入。其次,对静态图和动态图方法的理论相关性进行分析,对模型核心策略、下游任务和数据集进行全面总结。最后,提出了四个图嵌入的潜在研究方向。     

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

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

RMFKAN:基于改进图Mamba的网络水军检测方法

网络水军检测任务对构建和谐网络空间至关重要。针对现有基于图Transformer的网络水军检测方法无差别传递来自社区的节点之间的信息;从而导致节点表示过于同质;在处理长距离依赖关系时存在过度压缩和过度平滑;最终降低网络水军检测效果的问题;提出了一种基于关系双向图Mamba的傅里叶Kolmogorov-Arnold网络（RMFKAN）模型用于检测社交平台中的网络水军。通过异质感知的长距离关系特征提取方法解决了大规模社交网络跨社区长距离关系特征丢失的问题。通过引入双向选择状态空间模型（Bi-Mamba）解决了处理长距离依赖关系时的过度压缩和过度平滑问题。具体而言;通过随机游走策略令牌化子图;输入消息传递神经网络独立处理不同类型的边;利用傅里叶系数改进的KAN增强特征;将特征矩阵输入Bi-Mamba;提高对长距离依赖关系的捕捉能力;同时有效降低训练复杂度。在两个公开的网络水军检测数据集Twibot-20和Twibot-22上与10个基线模型进行对比实验;实验结果表明;RMFKAN在多个评价指标上均优于现有的基线方法;与现有研究的最佳效果相比RMFKAN的F1分数分别提高了2.10和4.06个百分点;准确率分别提高了1.01和4.45个百分点;验证了其在网络水军检测任务中的优越性能。     

基于非递减时序随机游走的动态异质网络嵌入

网络嵌入是将高维网络映射到低维向量空间的一种表示学习方法.目前,人们对动态同质网络嵌入和静态异质信息网络嵌入已经开展了一些研究,但动态异质网络上的嵌入研究仍然较少.如果直接应用静态网络嵌入或动态同质网络嵌入方法来解决动态异质网络嵌入问题,会由于忽略网络的动态或异质特性而导致严重的信息丢失.因此,提出一种基于时间和类别约束随机游走的动态异质网络嵌入方法TNDE.该方法引入类别约束,能够解决动态异质网络中由于异质特性带来的语义信息保留问题.不同于其他动态网络中的时序随机游走,该方法采用非递减的时间约束来增量式地进行随机游走,能够解决网络同时具备动态和异质特性而引入的强语义局部结构上的边时间戳一致的挑战,避免游走时出现时间戳陷入的问题.通过对实时变化的增量游走和嵌入学习,TNDE提供了一种高效的在线表示学习算法.在3个真实数据集上的实验结果表明：该方法在不同特性的网络中具有良好的通用性.与目前最先进方法相比,能够得到下游链路预测和节点分类任务中2.4%~92.7%的准确度提升,显著提高了嵌入质量,并在保证良好嵌入质量的前提下,缩短算法运行时间12.5%~99.91%.     

基于随机游走的大规模图中节点对采样算法

社会网络中的节点对采样可用于大规模社会网络的好友预测和用户兴趣识别.当整个网络的拓扑结构不完全或者随机选择用户的代价很高时,传统的均匀顶点采样方法的性能迅速下降.为此,提出了一种基于随机游走的大规模图中节点对采样算法.首先对社会网络的节点对采样进行了系统分析,对不同跳数下的节点对进行了定义;然后将社会网络转换成等价的网络图.新图中的顶点是原图中的边,新图中边的两个顶点是原图中含有相同顶点的两条边.最后,在新图上应用随机游走模型对节点对进行采样.实验结果表明,提出的方法统计误差小、执行效率高,性能明显优于均匀节点采样的相关算法.     

基于k核分解的网络嵌入

近年来,网络嵌入技术受到了广大研究者的关注。不过大多数网络嵌入算法并未考虑到处于相同层级结构的节点间的结构相似性,这些节点在网络中通常具有相同的重要性。因此,提出一种基于网络层级结构的网络嵌入算法,称为KCNE。KCNE算法使用网络节点间的层级结构信息来保持节点之间的结构相似性。该算法首先基于k核(k-core)分解方法将网络中的节点划分为不同的层级,并且使用定制的随机游走方法为每个节点生成游走序列,该序列可以有效捕获节点的一阶邻域及处于同层级中的高阶相似节点,随后将游走序列输入到Skip-gram模型中,使学习到的节点表示具有更好的区分性。基于多个真实数据集的实验结果表明,在链路预测和节点分类任务上,KCNE算法相比于8个基准算法中的次优算法性能提升最高分别约4%和5%。参数敏感性分析实验也表明了KCNE算法具有较好的鲁棒性。此外,该算法在运行效率方面均优于Role2Vec、RARE和GEMSEC算法。     

基于k核分解的网络嵌入

近年来, 网络嵌入技术受到了广大研究者的关注。不过大多数网络嵌入算法并未考虑到处于相同层级结构的节点间的结构相似性, 这些节点在网络中通常具有相同的重要性。因此, 提出一种基于网络层级结构的网络嵌入算法, 称为KCNE。KCNE算法使用网络节点间的层级结构信息来保持节点之间的结构相似性。该算法首先基于k核(k-core)分解方法将网络中的节点划分为不同的层级, 并且使用定制的随机游走方法为每个节点生成游走序列, 该序列可以有效捕获节点的一阶邻域及处于同层级中的高阶相似节点, 随后将游走序列输入到Skip-gram模型中, 使学习到的节点表示具有更好的区分性。基于多个真实数据集的实验结果表明, 在链路预测和节点分类任务上, KCNE算法相比于8个基准算法中的次优算法性能提升最高分别约4%和5%。参数敏感性分析实验也表明了KCNE算法具有较好的鲁棒性。此外, 该算法在运行效率方面均优于Role2Vec、RARE和GEMSEC算法。     

基于节点-属性二部图的网络表示学习模型

在图结构数据上开展推理计算是一项重大的任务,该任务的主要挑战是如何表示图结构知识使机器可以快速理解并利用图数据。对比现有表示学习模型发现,基于随机游走方法的表示学习模型容易忽略属性对节点关联关系的特殊作用,因此提出一种基于节点邻接关系与属性关联关系的混合随机游走方法。首先通过邻接节点间的共同属性分布计算属性权重,并获取节点到每个属性的采样概率;然后分别从邻接节点与含有共有属性的非邻接节点中提取网络信息;最后构建基于节点-属性二部图的网络表示学习模型,并通过上述采样序列学习得到节点向量表达。在Flickr、BlogCatalog、Cora公开数据集上,用所提模型得到的节点向量表达进行节点分类的Micro-F1平均准确率为89.38%,比GraphRNA（Graph Recurrent Networks with Attributed random walks）高出了2.02个百分点,比经典工作DeepWalk高出了21.12个百分点;同时,对比不同随机游走方法发现,提高对节点关联有促进作用的属性的采样概率可以增加采样序列所含信息。     

信任社交网络中基于图熵的个性化推荐算法

随着社交网络的飞速发展引起了人们对推荐系统(RS)的广泛关注。针对社交网络中现有推荐方法仍存在冷启动问题以及未考虑用户所处的社交网络信息的情况,提出了在信任社交网络中基于图熵的个性化推荐算法(PRAGE)。首先,根据用户物品和它们之间的反馈信息建立用户物品图(UIG),同时引入信任机制建立用户信任图(UTG);其次,通过对两个图使用随机游走算法得到用户与物品的初始相似度和基于信任机制的新的用户物品相似度;重复随机游走过程直至相似度稳定到收敛值;然后,使用UIG和UTG的图熵对两组相似度进行加权并最终相应地得出目标用户的最终推荐列表。在真实的数据集Epinions和Film Trust上的实验结果表明,相比经典的基于随机游走算法,PRAGE的精确率分别提高了34. 7%和19. 4%,召回率分别提高了28. 9%和21. 1%,能够有效地缓解推荐的冷启动问题且在精确率和覆盖率指标上均优于对比算法。