一种MAKLINK图多节点链路建模的路径规划研究

针对传统MAKLINK图规划路径线路改变时,其最优化路径易与环境约束条件冲突的问题,提出了在MAKLINK图中各链路上增加节点数目的方法,以提高系统建模的适应性和鲁棒性。设计的多节点链路通过dijkstra算法得到更为理想的次优化路径,由蚁群算法进行迭代计算获得最优化路径,实现了在保证路径适应度的前提下,提高优化路径对环境约束条件的适应性。实验结果表明,与基本MAKLINK图路径规划算法相比,多节点链路的建模路径规划算法可有效提高次优路径的建模精度,最优路径的适应度值较单节点链路减小了1.43%,具有一定的建模优势。

No-CapsE:一种基于节点共现的四元数胶囊网络知识图谱补全模型

知识图谱补全是通过预测知识图谱中缺失的事实进行填补,以解决知识图谱中的数据稀疏问题。CapsE、QuatE等用于知识图谱嵌入的模型在链接预测方面已经取得了较好的表现,但是,CapsE模型因其在复数空间进行链接预测与数据挖掘,会受限于其数据维度,使得数据挖掘不够深入,QuatE采用四元数构造超复数平面进行逻辑旋转,但其方法简单,无法有效地构建复杂关系。为此,提出一种改进的胶囊网络补全方法No-CapsE,在超复数平面构建胶囊网络。将数据用四元数进行表示并输入到四元数卷积网络中,输出的特征向量作为胶囊网络的输入,通过点积操作进行评分并依据评分判定三元组的正确性。此外,为了提高模型的训练速度,提出节点共现的思想,将实体和关系都视作节点。在公开数据集FB15K-237与WN18RR上进行链接预测实验,同时为了进一步探究所提模型的性能与效果,进行消融实验。实验结果均表明,相较于对比模型,No-CapsE的知识图谱补全效果更好,可以应用于大规模链接预测任务。

多路动态注意力图卷积网络

图卷积网络在处理网络数据的各种任务上有很多应用,特别是异构图卷积网络更是得到了广泛应用.但是,现有的工作中大多只设计单一关系的异构网络,这在处理那些含有多类型节点并且节点间具有多重网络关系的复杂异构网络时,很难准确捕获到跨不同关系的节点的特征,因此,这些异构网络的效果自然是不能令人满意的.为了应对这一挑战,提出了一种处理异构网络嵌入的多路动态注意力图卷积网络(MDAGCN).MDAGCN首先通过动态聚合同一节点对之间多种关系的信息,然后通过注意力机制得到不同长度元路径注意力权重,最后使用多层卷积结合注意力权重充分获取不同长度元路径上的信息来学习节点表示.在3个真实的数据集上进行实验.结果表明:MDAGCN模型可以通过动态权重以及注意力充分学习异构网络上的节点信息,以此提升节点分类和链路预测的效果.

图可视化布局方法最新研究进展综述

图可视化是图数据的直观表示,随着图数据的广泛应用,合适的图可视化能够使用户对图数据的理解更加深入和高效。但随着图数据量级的增长,图可视化布局面临着计算时间长,难以发现图的重要结构和关系,以及节点遮挡和复杂的边交叉所产生的视觉杂乱等挑战。因此,如何快速对大规模图数据进行布局,如何强化对图中重要的结构和关系的探索,以及如何生成美观的图可视化布局成为亟需解决的问题。近年来,许多基于力学模型和美学评价标准的优化方法被提出来解决上述问题。另外,图挖掘、图嵌入、图神经网络等机器学习方法从图数据特点的角度,为解决图可视化的布局问题提供了新思路,相比之下,机器学习方法在布局效率和效果上表现出一定的优越性。主要从力导向算法、基于美学约束的布局方法、图挖掘技术和机器学习方法这四方面对图可视化布局的最新研究进展进行了阐述,最后对图可视化布局方法的未来发展进行了展望。

基于局部优化的图表示学习增强

随着图表示学习在多个领域的成功应用,针对不同图数据和问题而设计的图表示学习方法爆发式增长.然而,图噪声的存在限制了图表示学习的能力.为有效降低图网络中的噪声比例,首先分析了图节点局部邻接的分布特性,并理论证明在局部邻接拓扑构建时,探索高阶邻近信息能够优化增强图表示学习的性能.其次,提出“2步骤”局部子图优化策略(local subgraph optimization strategy,LSOS).该策略首先根据原始图拓扑结构信息构造出具有多阶信息的局部邻接相似矩阵.然后基于相似矩阵和图节点局部信息,对图节点进行局部子图的结构优化.通过局部邻接的合理重构来降低网络中的噪声比例,进而达到图表示学习能力的增强.在节点分类、链接预测和社区发现3类任务的实验中,结果表明局部子图优化策略能够提升8个基线算法的性能.其中,在3个航空网络的节点分类任务中,提升效果最高分别达到23.11%,41.58%,24.16%.

基于图滤波器的符号属性图链路关系预测算法

带节点属性的符号网络在信息学、生物学等多个领域存应用广泛,链路符号预测是该类数据分析中的一个热点问题。基于符号图神经网络的模型是该问题的最新有效解决方案,但现有方法几乎均基于社会平衡理论,且未充分利用节点属性。针对以上问题,从图信号处理角度设计了一个符号图神经网络,提出了一种端到端的符号属性图链路预测算法。首先,给出了基于低频和高频信号的带通滤波器的符号图神经网络,用于获得基于符号拓扑图的节点嵌入;其次,构造属性相似性图,利用图卷积网络得到属性相似性图节点嵌入;最后,引入注意力机制,融合符号拓扑图与属性相似性图两种节点表达,并将其输入符号判别器,通过Adam优化器训练模型。在三个药物数据集上进行了对比实验与模型设置的影响分析。与典型的符号图卷积网络与符号图谱嵌入,以及最近提出的基于图滤波的符号卷积网络的对比结果表明,该模型在AUC与F1指标上比最好的基线方法提升了8.68%与10.04%。

一种异质图的Lorentz嵌入模型

异质图嵌入的目标是用低维稠密向量表示原网络的拓扑结构和节点属性信息。为提高异质图嵌入质量、减少失真,提出了一种将异质图嵌入到基于Lorentz模型的双曲空间中的方法。该方法采用元路径约束的随机游走进行节点关系和语义的发现,模型基于负采样的极大似然为目标函数,使目标节点与邻居更相近,而远离非邻居节点,优化方法不同于欧式空间的黎曼梯度下降;在引文网上将所提算法与4种基准图嵌入算法进行比较,实验证明该方法不但获得了优于其他基准算法的预测精度,而且还保留了可解释的图的层次结构。双曲嵌入为异质图的研究提供了一种新的思路,能够为异质图的下游任务提供更高质量的嵌入结果。

基于图论的多定压节点管网水力计算方法的研究

多定压节点管网具有复杂的拓扑关系,可充分发挥图论的优势对其进行水力计算。通过引入虚节点和虚环的概念将多定压节点问题转化为单定压节点问题,对相关矩阵按照定压和非定压节点、虚管段和实际管段、树支和链支管段进行分块表示。推导出了采用链支流量矩阵进行管网水力计算的解析表达式,在此基础上得到了适于计算机求解的离散模型,同时将此方法应用于实际算例并与HardyCross法的计算结果进行了对比。

基于属性边点图的飞机结构件筋特征识别方法

针对飞机结构件中筋特征结构复杂、相交筋特征识别困难的问题,提出一种基于属性边点图的筋特征自动识别方法。属性边点图以边为节点、以边与边之间的连接关系为弧。通过构造特征种子面的属性边点图,可以有效表示和处理筋特征中的边信息,弥补了传统属性面边图的不足。用端点表示筋特征两端的边界,通过端点类型及连接关系的分析,确定筋特征两端的相交情况;用分割节点来表示筋特征顶面的融合区域,以减少实际加工时的转角减速为优化目标,在分割节点处自动添加虚链,并对筋特征种子面的属性边点图进行分解,得到优化的相交筋特征识别结果。基于以上研究开发的筋特征自动数控编程系统已在某大型航空制造企业中得到良好的应用。

完全对换网络的容错性

完全对换网络是基于Cayley图模型的一类重要互连网络。f CT(n,k)(或F CT(n,k))表示在n维完全对换网络CT n中,使每个(n-k)维子完全对换网络失灵的失灵边(或点)的最小数目。分别给出了当k=0,1,n-2,n-1和k=2,n为素数时,f CT(n,k)(或F CT(n,k))的精确值;当3≤k≤n-3时,给出了f CT(n,k)和f s(n,k)的关系,其中f S(n,k)是使星网络S n中所有子星网络S n-k失灵的失灵边的最小数目;最后提出一个猜想。

基于权重图增量的无线网络Relay节点选择算法

为提高增量式无线网络Relay节点优化选择能力,提出基于权重图增量的无线网络Relay节点选择算法。构建无线网络Relay节点的优化拓扑结构模型,结合增量式无线网络的信道均衡控制方法,进行Relay节点的输出链路转换控制,建立无线网络的优化拓扑结构模型;结合信道自适应均衡调制方法进行无线网络Relay节点的链路转换设计;结合自适应拓扑调制方法进行增量式无线网络的权重图谱特征提取。根据权重图谱的聚类性进行无线网络Relay节点的自适应选择和融合聚类,提取无线网络Relay节点输出信息的关联维特征量;根据特征聚类结果,实现无线网络Relay节点的优化部署和选择,完成无线网络的信道输出均衡控制。仿真结果表明,采用该方法进行无线网络Relay节点选择的自适应性较好,网络输出的信噪比较高,误比特率较低。

异质网络中基于节点影响力的相似度度量方法

异质网络相似度学习,即分析两个不同类型对象间的相关程度.不同类型对象在异质网络中的重要程度不同,它们在相似度学习过程中的发挥的作用也不同.针对异质网络,提出了一种基于节点影响力的相似度度量方法NISim,该模型既考虑了网络中的链接结构,也保留了网络中的语义信息,同时区分不同类型节点对异质网络的作用.在异质信息网络环境下,通过启发式规则区分并量化不同类型节点的影响力权值,并结合网络链接结构和节点间语义关系,解决了提高相似度学习准确性的问题.实验结果表明,该方法能够有效地对异质信息网络不同类型节点进行相似度度量,可以应用在网络搜索、推荐系统以及知识图谱构建等不同领域.

图的表示与可视化方法综述

图是由节点和边组成的图形,通常用于表示两个或多个实体之间的关系。基于图的分析可以帮助人们理解实体关系的结构和本质,探索图中的隐含关联。图的表示与可视化方法在图分析中起着的重要作用,在图可视化研究中首先要考虑知识传达是否准确、人们的思维地图等方面,同时还要考虑图形是否美观、构建图所需的时间、以及计算机的性能等问题。综述了基于节点-链接、邻接矩阵以及图嵌入的图表示方法、图布局算法以及可视化方法,并对这些方法进行归纳与对比。最后对图表示与可视化技术的未来发展趋势进行了展望。

基于多粒度结构的网络表示学习

图卷积网络(GCN)能够适应不同结构的图,但多数基于GCN的方法难以有效地捕获网络的高阶相似性。简单添加卷积层将导致输出特征过度平滑并使它们难以区分,而且深层神经网络更难训练。本文选择将网络的多粒度结构和图卷积网络结合起来用于学习网络的节点特征表示,提出基于多粒度结构的网络表示学习方法Multi-GS。首先,基于模块度聚类和粒计算思想,用分层递阶的多粒度空间替代原始的单层网络拓扑空间;然后,利用GCN模型学习不同粗细粒度空间中粒的表示;最后,由粗到细将不同粒的表示组合为原始空间中节点的表示。实验结果表明:Multi-GS能够捕获多种结构信息,包括一阶和二阶相似性、社团内相似性(高阶结构)和社团间相似性(全局结构)。在绝大多数情况下,使用多粒度的结构可改善节点分类任务的分类效果。

基于同源控制点的边缘绑定方法

对含有大量复杂连接关系的节点连接图进行可视化会造成视觉上的严重混乱,边缘绑定是一种有效降低视觉混乱的方法。以往基于空间邻近性进行边缘绑定的方法会导致独立边缘产生模糊性歧义,给予用户错误的认知,而只专注于图的拓扑结构无法有效解决密集连接造成的视觉干扰问题。基于边缘路径的方法能够较好地利用图中原始节点信息对边缘进行控制绑定,从而避免独立边缘产生模糊性歧义,同时展现数据的高级模式。因此,在边缘路径方法的基础上进行了改进,提出了一种基于同源控制点的边缘绑定方法。该方法结合图的拓扑结构信息计算同源控制点,并以此为基础利用最短路径算法选取边缘控制点,然后结合分级思想对边缘聚合程度进行优化,最后通过Bézier曲线对边缘进行平滑处理。将基于同源控制点的边缘绑定方法用于美国迁移数据集和中国铁路线路数据集中,实验结果表明,该方法在改善过度绑定的问题上起到了较好的效果,相比原方法,此方法保留了更多局部数据细节,平衡了整体与局部边缘的绑定程度,可以有效地用于复杂连接图的可视化。

基于图勾勒的图链路预测方法

针对已有链路预测算法复杂度高,不适于在大规模图上进行链接预测的问题,本文基于图勾勒近似技术对已有链路预测方法进行优化,提出了基于图勾勒的链路预测方法。该方法将链路预测算法的计算复杂度由O(n^3)降低至O(n^2k^2log^2n)。为进一步提高链接预测效率,给出了基于Spark的并行化链路预测实现方法。在真实图数据集上进行测试,实验结果表明本文方法在保证链接预测精度的前提下,可有效提升算法效率。

融合图注意力的多特征链接预测算法

链接预测是复杂网络中重要的研究方向之一。利用神经网络学习预定义的启发式特征近年来受到广泛关注。但是目前此类方法主要利用目标链接的局部子图预测链接,具有较强的局部性。针对这一问题,在SEAL算法的基础上,提出了利用多特征融合图注意力进行链接预测的算法ADNSL。该模型支持多类型的节点嵌入特征作为输入,包括局部特征生成和全局特征提取两部分。对于局部特征生成模块,利用图卷积层,将局部子图中的节点特征交互融合。为了弥补SEAL中的特征无效性和节点无偏性,提出了双向无参注意力。在全局特征提取模块中,利用迭代公式生成聚合图以降低struc2vec节点嵌入算法的复杂度,进而从全局角度挖掘可解释的结构特征,可以有效提升链接预测算法性能。实验表明,ADNSL算法可以合理地利用多类型节点嵌入特征,在八个不同领域的真实数据集上的表现明显优于多个基准算法。

代码依赖可视化系统

分析了代码依赖可视化在智能化软件开发中的作用,在总结代码依赖特点和信息可视化系统一般流程的基础上,提出了代码依赖可视化系统的设计.该系统使用力导向节点连接图和层次边聚合图作为可视化形式,基于对两种可视化形式布局特点的深入分析,分别针对力导向节点连接图和层次边聚合图创造了过滤子节点和聚合叶节点的交互设计.在使用多种软件技术实现了代码依赖可视化原型系统dpViz之后,将系统试用于企业软件开发中,实验结果表明该可视化原型系统可有效增进代码分析效率.

基于链路预测的未来新增航线发现

针对新增航线发现研究中存在的航线选择主观化、网络信息挖掘不充分等问题,考虑航空运输网络的拓扑结构特征和节点(通航城市)层次属性,提出了一种基于链路预测的未来新增航线发现(NARP)模型。NARP模型提取局部封闭子图构建子图邻接矩阵,基于距离标记子图节点结构重要性,采用因子分析和层次聚类提取节点层次属性。在此基础上,融合子图结构和节点属性2类特征,采用深度图卷积神经网络(DGCNN)进行链路预测,实现新增航线发现。在中国航空运输网络实际运行数据上的实验结果表明:较之基准方法,NARP模型的预测准确率最高提升9.28%;在网络极度不完整时,预测准确率可以保持在80%左右;预测结果符合航空运输网络的实际演变情况。

结合图卷积神经网络的文献作者姓名消歧

在科学文献管理中,存在大量的科学技术文献需要被高效的识别、分类和保存.对于研究者来说,在研究该领域的相关知识时,通常会检索该领域的相关专家的文章,然而,姓名作为检索的常见搜索经常会出现歧义问题,这导致文献检索、统计和分析的质量下降.现有的方法在数据集上仍不能表现出良好的聚类效果,如何实现有效的消歧方法仍是一项挑战.本文提出基于图卷积神经网络的作者姓名消歧技术.首先使用BERT模型将文献作者、出版机构、摘要等多种属性信息嵌入到低维向量空间中,得到与作者相关的多种属性的嵌入向量,克服嵌入向量不够准确的缺陷;接下来以节点嵌入为基础,为每篇文献都构建文献局部图,使用图卷积神经网络对生成的文献局部图进行链路预测,有助于提高链路预测的准确性;最后,在图上使用简单的连通域搜索并动态剪枝进行聚类.基于实验表明,本文提出的方法有比较好的性能提升,能够提高作者姓名消歧的准确性.