The Path-Positive Property on the Products of Graphs

本文所讨论的积图是图的笛卡尔积，图的张量积，图的逻辑积和图的强直积四种积图．证明了：①如果Ｇ１和Ｇ２都是连通图，则积图中笛卡尔积，逻辑积和强直积都是道路正图．②图的张量积是道路正图的是图Ｇ１和Ｇ２是一个连通图，Ｇ１［或Ｇ２］有一个奇圈，且ｍａｘ｛λ１μ１，λｎμｍ｝≥２。

Improving Centralized Path Calculation Based on Graph Compression

Shortest-path calculation on weighted graphs are an essential operation in computer networks. The performance of such algorithms has become a critical challenge in emerging software-defined networks(SDN),since SDN controllers need to centralizedly perform a shortest-path query for every flow,usually on large-scale network. Unfortunately,one of the challenges is that current algorithms will become incalculable as the network size increases. Therefore, inspired by the compression graph in the field of compute visualization,we propose an efficient shortest path algorithm by compressing the original big network graph into a small one, but the important graph properties used to calculate path is reserved. We implement a centralized version of our approach in SDN-enabled network,and the evaluations validate the improvement compared with the well-known algorithms.

3D multipath planning for UAV based on network graph

According to the characteristic and the requirement of multipath planning, a new multipath planning method is proposed based on network. This method includes two steps： the construction of network and multipath searching. The construction of network proceeds in three phases： the skeleton extraction of the configuration space, the judgment of the cross points in the skeleton and how to link the cross points to form a network. Multipath searching makes use of the network and iterative penalty method （IPM） to plan multi-paths, and adjusts the planar paths to satisfy the requirement of maneuverability of unmanned aerial vehicle （UAV）. In addition, a new height planning method is proposed to deal with the height planning of 3D route. The proposed algorithm can find multiple paths automatically according to distribution of terrain and threat areas with high efficiency. The height planning can make 3D route following the terrain. The simulation experiment illustrates the feasibility of the proposed method.

Individual tree extraction from terrestrial laser scanning data via graph pathing

Background:Individual tree extraction from terrestrial laser scanning(TLS)data is a prerequisite for tree-scale estimations of forest biophysical properties.This task currently is undertaken through laborious and time-consuming manual assistance and quality control.This study presents a new fully automatic approach to extract single trees from large-area TLS data.This data-driven method operates exclusively on a point cloud graph by path finding,which makes our method computationally efficient and universally applicable to data from various forest types.Results:We demonstrated the proposed method on two openly available datasets.First,we achieved state-of-the-art performance on locating single trees on a benchmark dataset by significantly improving the mean accuracy by over 10% especially for difficult forest plots.Second,we successfully extracted 270 trees from one hectare temperate forest.Quantitative validation resulted in a mean Intersection over Union(mIoU)of 0.82 for single crown segmentation,which further led to a relative root mean square error(RMSE%)of 21.2% and 23.5% for crown area and tree volume estimations,respectively.Conclusions:Our method allows automated access to individual tree level information from TLS point clouds.The proposed method is free from restricted assumptions of forest types.It is also computationally efficient with an average processing time of several seconds for one million points.It is expected and hoped that our method would contribute to TLS-enabled wide-area forest qualifications,ranging from stand volume and carbon stocks modelling to derivation of tree functional traits as part of the global ecosystem understanding.

Optimal parallel algorithm for shortest-paths problem on interval graphs

This paper presents an efficient parallel algorithm for the shortest-path problem in interval graph for computing shortest-paths in a weighted interval graph that runs in O(n) time with n intervals in a graph. A linear processor CRCW algorithm for determining the shortest-paths in an interval graphs is given.

Longest Paths and Cycles in Connected Claw-Free Graphs

A graph is called claw-free if it does not contain a claw as its induced subgraph.In this paper, we prove the following results:1)If G is a 2-connected claw-free graph on n vertices,then for any vertex v and any two distinct vertices x and y in V(G)-{v},G has a path containing v and all neighbors of v and connecting x and y;2) Let C be the longest cycle in a 3-connected claw-free graph G and H a component of G-C,and if H is connected but not 2-connected,then there exist nonadjacent vertices u and v in H such that |V(C)|≥(3(d(u)+)d(v))-2.

System Vulnerability Analysis Using Graph Pathfinding Strategies in Partitioned Networks

In this paper, a new method has been introduced to find the most vulnerable lines in the system dynamically in an interconnected power system to help with the security and load flow analysis in these networks. Using the localization of power networks, the power grid can be divided into several divisions of sub-networks in which, the connection of the elements is stronger than the elements outside of that division. By using our proposed method, the probable important lines in the network can be identified to do the placement of the protection apparatus and planning for the extra extensions in the system. In this paper, we have studied the pathfinding strategies in most vulnerable line detection in a partitioned network. The method has been tested on IEEE39-bus system which is partitioned using hierarchical spectral clustering to show the feasibility of the proposed method.

Length of the Longest Path and Diameter in Orientations of Graphs

We say that a parameter p of directed graphs has the interval property if for every graph G?and orientations of G, p can take every value between its minimum and maximum values. Let λbe the length of the longest directed path. A question asked by C. Lin in [1] is equivalent to the question of whether λhas the interval property. In this note, we answer this question in the affirmative. We also show that the diameter of directed graphs does not have the interval property.

基于知识图谱的可解释学习路径推荐

学习路径推荐是解决信息超载、学习迷航等问题的关键,但当前的学习路径推荐相关研究存在推荐方法脱离学习场景、推荐结果缺乏解释等问题。为此,文章构建了基于知识图谱的可解释学习路径推荐模型:首先利用邻域标定的图注意力网络表征知识图谱语义信息并生成候选学习路径集,然后计算不同学习场景下学习者与候选学习路径之间的契合度和匹配度,最终实现可解释的学习路径推荐。之后,文章通过对基于知识图谱的可解释学习路径推荐模型与学习路径推荐基线模型进行对照实验和可解释案例分析,发现基于知识图谱的可解释学习路径推荐模型不仅提高了推荐结果的准确度,而且提升了推荐结果的可解释性。文章的研究有助于学习者获得准确、可解释的学习路径,从而提升个性化学习效果。

基于CiteSpace的国内旅游形象研究进展与展望

旅游形象历来受到旅游目的地重视,也是目的地研究的重要领域。厘清旅游形象的研究热点与演化路径,有助于进一步推动目的地形象管理领域的理论创新。文章基于中国知网数据库收录的1994-2022年旅游形象研究文献作为数据,运用CiteSpace可视化软件对文献作者、研究机构和关键词进行计量分析。研究表明:旅游形象领域学者及机构共现较少,学术交流与合作亟待加强;研究热点主题有城市旅游、形象感知、品牌形象、品牌塑造、认知形象、内容分析和网络文本等;数字足迹、网络游记、地理标记图片、网络文本分析、文本挖掘等是今后一段时期旅游形象研究相关的热点主题。

基于全局图注意力元路径异构网络的药物-疾病关联预测

提出了一个基于全局图注意力元路径异构网络模型(MHNGA)来进行药物-疾病关联预测。首先,收集整理药物和疾病数据,将已知的药物-疾病关联、药物相似性、疾病相似性构建为一个异构网络;其次,引入多个基于元路径的子图,使用图注意力神经网络提取这些子图的邻居节点的特征,并且通过通道注意力和空间注意力机制来增强特征;最后,通过十折交叉验证的评估,MHNGA取得了93.5%的精确召回曲线下的面积和99.4%的准确率。

正确性可验证的密文图数据最短路径外包计算方案

地理位置、社交网络等海量图数据应用广泛且包含大量隐私,通常需要安全的外包计算来提供多样化的查询服务。然而,如何设计正确性可验证的图数据外包计算协议仍是公开的难题。为此,提出了加密图数据上正确性可验证的精确最短路径外包计算方案。该方案利用加法同态加密构造密态图数据上的广度优先最短路径计算算法,支持加密图数据的精确最短距离查询外包计算;其次,基于双线性映射累加器构造最短路径外包计算结果的概率正确性验证机制。分析和证明表明,该方案能以概率可靠性实现正确性可验证的精确最短路径的外包计算,具备随机预言模型下的IND-CCA2安全。对比实验结果表明,所提方案相比其他相关方案在安全性、功能性方面有显著优势,性能上较已有可验证图数据外包计算方案在初始化及加密环节、查询环节、验证及解密环节的时间开销分别降低了0.15%~23.19%,12.91%~30.89%和1.13%~18.62%。

一种基于简化可视图的建图和规划方法

当前车辆路径规划大部分是基于栅格地图的规划方法,这种方法在搜索面积较大时计算量也会大幅增加。相比之下,基于可视图的方法能够在路径搜索时减小计算量,但是受到障碍物复杂程度的影响较大。针对这一问题,本文结合SLAM和可视图的方法,提出了一种简化可视图的建图和规划方法。首先使用改进的SLAM算法生成点云地图,并进行动态障碍物的剔除。接着生成可视图,并基于障碍物的大小和顶点处内凹角的大小对可视图中多边形的复杂边缘进行简化,剔除冗余的顶点。最后通过仿真和实车实验证明,该方法相对原有的算法,在保证建图精度的情况下,可视图中多边形的顶点数量减少20%~30%,地图更新时间和整体算法的运行时间减少30%以上。这表明本文方法能够有效减小建图和规划过程的计算量和算法的运行时间。

基于图搜索的陆空两栖平台3D路径规划算法

为了解决陆空两栖平台路径规划能效与寻径效率问题,提出了一种基于图搜索算法的全局路径规划算法。考虑了空中飞行能耗与地面行驶能耗模型的不同,结合起飞阈值、地面移动成本系数、空中移动成本系数等参数决定模态切换机制,在遇到难以越过的障碍时使用逃脱算法脱困,当允许地面通过时优先采用地面行驶的方式到达目标点以提升寻径效率与能效。为验证该算法,分别建立了针对陆空2种模式下的能耗模型,在现有交通规则约束下完成城市场景和虚拟迷宫测试。结果表明:本算法的搜索效率相较于对照组算法提升了30%以上,有效提升搜寻效率的同时降低了能量消耗。

基于证据图推理的文档级实体关系抽取

[研究目的]为缓解文档级实体关系抽取任务中存在的句子噪声问题,提高文档级实体关系抽取性能,提出一种基于证据图推理的文档级实体关系抽取方法,为文档级实体关系抽取和知识发现研究提供参考。[研究方法]通过启发式规则捕获实体对间关系推理所需证据句路径信息;引入图结构学习思想将证据句路径信息融入异构文档图;基于关系图卷积网络进行关系推理以提升文档图对证据句信息的聚合能力;采用前馈神经网络对实体关系进行预测,实现文档级实体关系高效抽取。[研究结论]所提出的模型在国际公开文档级评测数据集CDR和GDA上F1值分别达到71.3%和85.4%,较基准模型EIDER提高1.2%与1.1%。实验结果表明该方法能够有效选择实体关系推理所需证据路径,提升文档级实体关系抽取性能。

基于有向图规划的城乡物流配送路径优化研究

为了解决当前的城乡物流配送路径优化方法存在的路径利用率和需求点满意度低、配送成本高的问题,提出基于有向图规划的城乡物流配送路径优化方法。将城乡物流配送路径优化转化为配送路线合理安排问题,设计城乡物流配送路径问题表达式和约束条件,以此提出配送路径优化假设,建立城乡物流配送路径优化模型,并制定模型约束。采用有向图规划计算最短路径和最早配送时间,并获取该范围内的需求点,得到优化后的城乡物流配送需求点和路径。实验结果表明,研究方法的配送成本较低,路径利用率和需求点满意度较高。

路与星图的强乘积图的容错直径

设路P_(m)与星图S_(1,n-1)的强乘积图为G=P_(m)S_(1,n-1).首先,通过归纳假设和构造内点或边不交路的方法,结合星图的中心性,给出图G的点容错直径D_(w)(G)和边容错直径D′t(G).结果表明,对图G中发生的任意点或边故障,都有D_(w)(G)≤d(G)+2,D′t(G)≤d(G)+1.其次,通过顶点数和边数构造的不等关系,给出两个极大连通图的强乘积图的点容错直径的上界,以及两个非平凡连通图的强乘积图的边容错直径的上界.

融合模式决策的4WIS车辆路径规划方法

针对四轮独立转向(four-wheel independent steering,4WIS)车辆的路径规划问题,提出了一种融合模式决策的图搜索算法.首先,对4WIS车辆三种运动模式进行建模,并分析其运动模式的运动特性,据此设计多模式节点拓展策略,实现了4WIS车辆多运动模式与路径规划的融合.然后,针对最优节点选取和运动模式决策问题,设计了多目标代价函数,引导4WIS车辆合理切换运动模式,并生成平滑路径.最后,在MATLAB软件上进行仿真实验,在多种场景中测试所提出算法,验证其可行性与有效性.结果表明:提出的算法在路径规划中考虑了三种运动模式的优化组合与模式切换问题,能实现最优运动模式序列和最短路径规划.且该算法求解效率高,所规划路径优异,能充分发挥4WIS车辆的高灵活性与高通过性,有效解决其路径规划问题.

结合注意力机制的属性异质网络嵌入方法

图(网络)是一种常用于抽象现实世界实体之间关系的数据结构,网络嵌入广泛应用于图数据的表征.目前大部分异质网络嵌入方法未考虑网络节点之间的多种边类型和边属性,无法完整刻画网络的结构和语义信息,导致原始网络特征信息丢失和下游任务效果差的问题.为解决该问题,基于注意力机制设计了一种多边属性异质网络嵌入方法,其将注意力机制应用于学习不同边类型下嵌入向量的重要系数,通过有偏序列采样、邻居向量聚合和模型参数更新3个阶段的嵌入学习,将网络节点表示成固定长度的稠密向量.实验表明,提出的嵌入方法能够更好地嵌入网络的特征信息,使之在下游的机器学习任务上有一定的效果提升.