一类本原双色有向图的指数界

对一类相对特殊的双色本原有向图给出了本原条件,结合圈矩阵给出了本原指数的上下界,并刻画了取得指数上下界时所对应的极图。

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

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

基于分层有向图与动态时空相关性的小区域光伏超短期预测方法

小区域光伏发电功率准确预测,已成为高渗透多台区系统精准调控运行的技术瓶颈。目前光伏发电功率的预测方法缺乏对台区小区域内光伏集群效应的考虑,忽略了输入变量的内在因果关系以及动态相关性。针对于上述问题,提出一种基于分层有向图以及动态图卷积循环网络(dynamic graph convolutional recurrent network,DGCRN)的小区域光伏预测方法。首先,考虑出力数据与数值天气预报(numerical weather prediction,NWP)单向关系,生成具有因果联系的分层有向图。其次,依据节点属性在每个时间步生成动态图,与预先定义的静态图有机结合,以捕捉节点之间的动态时空相关性。最后,将具有动态时空相关性的图结构用于模型训练。以某个小区域台区29个光伏节点加以预测建模,实验结果表明,DGCRN模型具备捕获多参量间的因果规律和提取光伏功率的短期动态特征的能力,其在小区域多节点的光伏发电功率预测性能优越。

欧拉–拉格朗日系统在权重不平衡有向图下的分布式优化算法

本文研究了欧拉–拉格朗日(EL)多智能体系统在权重不平衡有向图下的分布式优化问题,优化目标为通过智能体间的局部通讯最小化全局目标函数,该目标函数为智能体自身局部目标函数的和。为解决该问题,本文设计平衡补偿变量调节拓扑权重,并提出EL系统在权重不平衡有向图下的分布式优化算法,该算法使智能体状态达成一致的同时,协同最小化全局目标函数。最后,给出一个基于Simulink的数值仿真验证所提出算法的有效性。

基于图注意与有向图神经网络的人体动作识别

基于人体骨骼数据的图卷积神经网络不易受背景环境噪声影响且鲁棒性较强,已成为现阶段人体动作识别领域的研究重点,但该网络对同阶邻域中不同邻域赋予相同权值,限制了其捕捉空间信息相关性的能力。为此,引入图注意网络加权和求和相邻节点的特征,允许每个节点根据其相邻特征分配不同权重,以增强特征提取和学习能力。同时,为解决将骨架表示为无向图时只能确定相邻节点或边之间的关系,从而限制了捕获节点或边之间依赖关系能力这一问题。引入有向图卷积,利用一阶和二阶相邻节点的特征信息进行图卷积,既保留了有向图的方向性特征,又扩展了图卷积的感知域,从而能够提取更多特征。实验表明,所提方法能有效提升动作识别的精度。

有向图的谐波分析:从傅里叶到小波

数据化时代中,高效地分析和处理数据引起了研究者的广泛关注。利用图模型建立数据的结构,进而对数据进行分析处理,发展起了图信号处理。最初是在无向图中发展的,图拉普拉斯在其中发挥着重要作用。神经科学、社会网络等领域的数据网络都是定向的,从而信号处理需要扩展到有向图中。在有向图中,图拉普拉斯不再使用,将参考算子换作图上的游走算子。进而把随机游走算子的特征向量集作为有向图上函数的非正交傅里叶型基。从随机游动算子的狄利克雷能量获得的特征向量的变化与相关特征值的实部联系起来,找到了频率解释。在有向图中,又分别回顾了小波变换和抽取小波变换作为谱图小波和扩散小波框架的扩展。上述都是在算子是可以对角化的前提下提出的。但是现实生活中的数据模型不会只局限于对角化的算子,因此本文将算子扩展到了整数项的扩张矩阵中,从而提出了有向图上的紧支撑帕塞瓦尔小波框架及其多分辨率分析,并且也找到了基于这类矩阵下的频率解释。此类小波框架不仅在构造时简单高效,而且在性质上也有很大优势:有确定的消失矩的阶数,使尽量多的小波系数为零或者产生尽量少的非零小波系数,利于消除噪声。

点传递二部有向图的极大连通性

有向图X的连通度κ(X)是删除一些点使得剩余的图不再强连通的最小点数.若有向图X的连通度恰好达到最小度,则有向图X是极大连通的.证明了强连通点传递二部有向图是极大连通的,并得出Bi-Cayley有向图也是极大连通的.

有向图上基于层次树索引的最大cycle truss社区搜索

社区搜索旨在从信息网络中找出包含用户查询顶点的高内聚连通子图,cycle truss是一种基于cycle三角形的社区搜索模型,而现有的基于索引的cycle truss社区搜索方法存在索引空间大、搜索效率低、社区内聚性低的缺点。为了解决这一问题,提出一种基于层次树索引的最大cycle truss社区搜索方法。首先,提出了k-cycle truss分解算法,并引入了两个重要的概念:cycle三角连通与k-层次等价。基于k-层次等价设计了层次树索引TreeCIndex与表结构索引SuperTable,在此基础上,并基于这两个新的索引,提出了两个高效的cycle truss社区搜索算法。在4个真实数据集上与已有的基于TrussIndex与EquiTruss的社区搜索算法进行了比较,实验结果表明,TreeCIndex与SuperTable比TrussIndex与EquiTruss节省至少41.5%的空间,索引构建的时间节省8.2%至98.3%,且搜索最大cycle truss社区的效率分别高出了一个和两个数量级。

基于有向图的分布式连续时间非光滑耦合约束凸优化分析

研究一类分布式优化问题,其目标是在满足耦合不等式约束和局部可行集约束的情况下使非光滑全局代价函数值最小.首先,对原有的分布式连续时间投影算法进行拓展,结合线性代数理论分析,设计一个适用于强连通加权平衡有向通信网络拓扑图的算法.其次,在局部代价函数和耦合不等式约束函数是非光滑凸函数的假设条件下,利用Moreau-Yosida函数正则化使目标函数和约束函数近似光滑可微.然后,根据强连通加权平衡有向图的分布式连续时间投影算法构造李雅普诺夫函数,证明该算法下的平衡解是分布式优化问题最优解,并对算法进行收敛性分析.最后,通过数值仿真验证算法的有效性.

基于有向图卷积循环网络的分布式光伏出力超短期预测方法

提出一种基于有向图卷积循环网络的分布式光伏超短期功率预测方法,该方法可同时提取光伏出力的时序特征和空间相关性,有效减小预测误差。首先,分析光伏出力数据兼具时序性和空间相关性,利用门控循环网络提取时序特征,构建有向图卷积网络提取传统图卷积无法捕捉的光伏出力有向空间相关性;然后,融合门控循环单元和有向图卷积网络,构建有向图卷积循环网络以提取多光伏站点出力的时空相关性,并利用注意力机制为不同时刻的时空特征分配权重;最后,通过全连接层输出最终的预测结果。采用某地区屋顶光伏实际出力数据在不同预测时间尺度下比较所提方法与其他方法的预测性能,结果表明,预测时间尺度为15、30和60 min时,相对于传统循环网络,所提方法的MAE分别减少16.3%、20.7%和28.1%。

含负权有向图最短路问题的新解法

通过简要分析现有含负权有向图最短路问题求解方法,基于Dijkstra算法图表法的基本原理,提出了一种新的较为直观的图表求解方法。该方法根据问题抽象所得的含负权有向图,通过确定权数来求解最短路问题,并给出了计算实例。结果表明,该方法具有实用性,且所提算法具有简便直观,计算量较少,不易出错,效率较高的特点。

银行间网络风险评估中的有向图采样方法

在本文中,我们研究了银行间负债网络的采样方法,即给定强度序列下的加权有向图采样算法。具体地,我们可以将给定强度序列下的采样问题看作带约束的随机采样问题,并通过消除等式约束的方案将采样空间转换为一个特殊的多胞形,同时将原问题转换为多胞形上的采样问题。由于真实的银行间网络数据在采样空间中并不是均匀分布的,我们引入了先验知识,用混合高斯分布对采样分布进行建模。基于给定强度序列下的有向图采样技术,本文还结合拓扑结构推断、重要性采样以及DebtRank模型等工具,首先提出了一套基于随机模拟的银行间网络风险评估框架,并在部分银行数据上做了信贷冲击实验和流动性冲击试验,提供了一个基于风险分布模拟的风险分析视角。

大型卫星地面站故障诊断的增强分层有向图方法

为了解决传统分层有向图模型在卫星地面站故障诊断面临的问题,提出了基于增强分层有向图模型的故障诊断方法。在建模过程中,考虑到卫星地面站故障征兆多、建模复杂,依据各设备工作状态的故障传播方式合并同类节点,以减小模型规模;同时,在模型中加入节点有效性使能函数,克服传统分层有向图模型中设备主备切换导致系统结构发生改变时需要重新建模的问题。在故障诊断推理过程中,采用反向回溯和正向推理相结合的方法减小故障源搜索空间,并基于各节点被搜索次数给出故障概率,提高诊断效率。以北斗卫星无线电测定业务地面站为例对单故障和多故障报警场景下的故障诊断方法进行了验证。结果表明,基于增强分层有向图模型的故障诊断方法可以提高故障诊断的准确率和全面性。

基于有向图的强化学习自动驾驶轨迹预测

轨迹预测作为自动驾驶中的重要组成部分,旨在对车辆进行行驶估计,以便车辆根据行驶估计进行路径规划,从而做出安全准确的决策。首先,为提升车辆轨迹预测精度,采用有向图方法构建高清驾驶场景地图,有向图方法将地图信息矢量化,以便有效提取地图拓扑结构;其次,采用生成对抗模仿学习(GAIL)通过生成器与判别器的对抗博弈学习数据集驾驶策略,从而根据当前状态采取对应驾驶行为;最后,通过采样遍历得到多模态预测轨迹方案。在nuScenes运动预测数据集上进行仿真,量化结果显示相比于其他方法,K=5时,最小最终位移误差MinFDE_(5)提高了10.8%;K=10时,最小最终位移误差MinFDE_(10)提高了17.53%,最小平均位移误差MinADE_(10)提高了9.52%,失误率MissRate_(10)减少了28.26%。评估结果表明:生成的轨迹多模态符合场景基本结构,且准确度得到提高。

有向图的外独立双罗马控制

设D=(V(D),A(D))是一个有向图,若函数h:V(D)→{0,1,2,3}满足以下条件:(1)每个赋值为0的顶点至少有一个赋值为3的内邻或两个赋值为2的内邻;(2)每个赋值为1的顶点至少有一个赋值为2或3的内邻;(3)所有赋值为0的顶点都是不相邻的,则称函数h为有向图D的一个外独立双罗马控制函数.一个有向图的外独立双罗马控制函数的权为所有顶点的赋值之和.外独立双罗马控制函数的最小权称为外独立双罗马控制数.2020年,Abdollahzadeh Ahangar等人给出了无向图的外独立双罗马控制函数的定义,并给出了无向图外独立双罗马控制数的一些界.文中将此概念推广到了有向图上,研究了有向图的外独立双罗马控制数的界,并进一步刻画了外树的外独立双罗马控制数的下界,以及外独立双罗马控制数的Nordhaus-Gaddum不等式.

有向图对策下的Banzhaf值及其应用

Banzhaf值是经典可转移效用合作对策中重要的分配规则之一,它假设任何有限参与者间均能进行合作形成可行联盟。2006年,Alonso-Meijide和Fiestras-Janeiro考虑无向网络,定义了图对策下的Banzhaf值,以此反映合作网络对参与者间合作以及分配结果的影响。本文则在此基础上,考虑合作网络的方向性,将Banzhaf值进一步推广到有向图对策中,提出了新的分配规则——有向Banzhaf值。首先,本文证明了有向Banzhaf值满足准隔离性、收缩性、公平性、强分支可分解性以及强分支总贡献性。其次,证明了有向Banzhaf值可由公平性、准隔离性以及收缩性唯一刻画,也可由公平性结合强分支总贡献性唯一刻画。最后,以湿地水循环系统为例,对有向Banzhaf值和其他值进行了比较分析,讨论了有向Banzhaf值的应用价值。

利用加权有向图的船舶水尺重建与水位识别

针对目前船舶水位识别精度低、检测场景迁移性差等问题,提出一种基于加权有向图的高精度、鲁棒性好的船舶水尺重建和水位识别方法.首先通过目标检测和图像分割算法识别船体上的水尺字符和水位线;然后根据船舶水尺的结构特点将识别出来的水尺字符构建加权有向图,通过寻找加权有向图中的最长路径完成船舶的水尺重建;最后根据重建水尺和水位线的位置关系识别船舶的水位高度.在黄骅港实地采集的视频数据上进行实验的结果表明,所提方法可以较好地修正前期基于水尺字符检测网络带来的字符误检问题,大大减少因船舶图像背景复杂产生的不利影响,在10mm的误差范围内,水位识别准确率可达91.3%,显著优于业内主流方法.

GC-MCR:有向图约束指导的并发缺陷检测方法

约束求解应用到程序分析的多个领域,在并发程序分析方面也得到了深入的应用.并发程序随着多核处理器的快速发展而得到广泛使用,然而并发缺陷对并发程序的安全性和可靠性造成了严重的影响,因此,针对并发缺陷的检测尤为重要.并发程序线程运行的不确定性导致的线程交织爆炸问题,给并发缺陷的检测带来了一定挑战.已有并发缺陷检测算法通过约减无效线程交织,以降低在并发程序状态空间内的探索开销.比如,最大因果模型算法把并发程序状态空间的探索问题转换成约束求解问题.然而,其在约束构建过程中会产生大量冗余和冲突的约束,大幅度增加了约束求解的时间以及约束求解器的调用次数,降低了并发程序状态空间的探索效率.针对上述问题,提出了一种有向图约束指导的并发缺陷检测方法GC-MCR(directed graph constraint-guided maximal causality reduction).该方法旨在通过使用有向图对约束进行过滤和约减,从而提高约束求解速度,并进一步提高并发程序状态空间的探索效率.实验结果表明:GC-MCR方法构建的有向图可以有效优化约束的表达式,从而提高约束求解器的求解速度并减少求解器的调用次数.与现有的J-MCR方法相比,GC-MCR的并发程序缺陷检测效率可以取得显著提升,且不会降低并发缺陷的检测能力,在现有研究方法广泛使用的38组并发测试程序上的测试时间可以平均减少34.01%.

具有小度数的1-正则Cayley有向图

令Γ是一个图,如果Γ的自同构群Aut(Γ)作用在其弧集上是正则的,则称图Γ为1弧正则图,简称1正则图。本文利用局部分析法和全局分析法,结合图论、群论,尤其是置换群的一些理论以及方法,给出了度数分别为3、4、5、6的1正则Cayley有向图的完全分类,这样的图如果不是正规或双正规的,那么它一定是某个商图的正规(多重)覆盖。

Riordan有向图

为了拓展Riordan阵与Riordan群理论,提出Riordan有向图的概念并研究其性质,由此建立整数序列、Riordan阵与图之间的联系。首先,基于Riordan阵,定义Riordan有向图,并利用Riordan阵的基本性质得到Riordan有向图的边集满足的条件。然后,给出Riordan有向图含有Hamilton路的一个充分条件以及Riordan有向图是本原有向图的一个充分条件。最后,通过Riordan群上的对角平移算子提出构造同构Riordan有向图的方法。结果表明:一些特殊的整数序列与有向图之间有良好的对应,且利用Riordan阵理论可以将一些整数序列的性质反映到有向图的性质上。