A Fast Method for Shortest-Path Cover Identification in Large Complex Networks

Fast identifying the amount of information that can be gained by measuring a network via shortest-paths is one of the fundamental problem for networks exploration and monitoring.However,the existing methods are time-consuming for even moderate-scale networks.In this paper,we present a method for fast shortest-path cover identification in both exact and approximate scenarios based on the relationship between the identification and the shortest distance queries.The effectiveness of the proposed method is validated through synthetic and real-world networks.The experimental results show that our method is 105 times faster than the existing methods and can solve the shortest-path cover identification in a few seconds for large-scale networks with millions of nodes and edges.

Using Link Analysis Technique with a Modified Shortest-Path Algorithm to Fight Money Laundering

Effective link analysis techniques are needed to help law enforcement and intelligence agencies fight money laundering. This paper presents a link analysis technique that uses a modified shortest-path algorithms to identify the strongest association paths between entities in a money laundering network. Based on two-tree Dijkstra and Priority＇First-Search （PFS） algorithm, a modified algorithm is presented. To apply the algorithm, a network representation transformation is made first.

A~*算法在Shortest-Path方面的优化研究

在游戏和地理信息系统开发等领域中,专门针对最短路径搜索方面的优化研究较多,尤其是最短路径中启发式搜索算法中的A*算法的效率优化研究.本文将针对在人工智能或算法研究中的使用的地图大多数是基于任意图而不是网格图的状况,通过任意图与网格图及方向的相结合,提出了三种优化A*算法的启发式函数搜索策略,较好地减小了算法搜索的范围和规模,有效地提高了A*算法的运行效率.最后的实验结果显示,与传统的A*算法相比较,优化启发搜索策略后的A*算法寻径更快速,更准确,计算效率更高.

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.

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

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

考虑鲁棒成本与绝对后悔的最短路径问题研究

为克服鲁棒偏差方法在处理区间路网时所求鲁棒最短路径的保守性问题,通过分析鲁棒成本的定义以及鲁棒最短路径过于保守的原因,结合算例分析提出了绝对后悔值的概念,并以鲁棒成本和绝对后悔值为目标函数建立了区间路网的多目标最短路径模型;根据最短路径模型的特点设计了分离路径决策变量与连续变量的Benders分解算法,同时基于传统有效路径的判断依据重新定义了符合该最短路径模型的有效路径,并在分解后的主问题模型中引入了有效路径约束以加快算法收敛速度;利用MATLAB生成了一个包含29个节点、70条双向通行路段的区间路网对模型与算法进行仿真测试。结果表明:考虑鲁棒成本和绝对后悔值的最短路径模型能在区间路网中找到不保守,且同时兼具鲁棒性的最短路径,能够有效克服鲁棒偏差方法的缺陷。

基于标识密码的内生安全最短路径优先协议

路由协议如开放的最短路径优先协议OSPFV2的安全运行对网络的连通及信息安全传输至关重要。传统OSPFV2协议在设计上缺少抵御源路由伪造或路由信息篡改的能力,致使组网易遭遇攻击,而现有的安全策略多为外挂式,易引发新的安全问题或安全效能低,为此,提出基于标识密码的内生安全OSPFV2协议,将标识密码内嵌于路由交换流程内,使网络具备高效的、内生式的抵御路由在传输过程中的篡改和伪造攻击能力。另一方面,考虑大范围部署安全OSPFV2协议存在多种限制因素,利用不透明链路状态通告,设计支持增量部署的运行机制。仿真实验表明,设计的内生安全OSPFV2协议在不损耗过多收敛时延的同时,具备抵御源路由伪造、数据篡改的安全能力。

基于SRv6的域内路由保护方案研究

网络故障导致大量的数据包丢失,并且严重影响网络性能,如何高效快速地应对网络中的故障是设计路由协议的基本要求和主要任务。目前,比较有效的方法是互联网部署的开放式最短路径优先(open shortest path first,OSPF)和中间系统到中间系统(intermediate system-to-intermediate system,IS-IS),通过动态路由协议解决网络故障,但是在协议动态收敛的过程中仍会有大量的报文被丢弃。因此,路由器厂商广泛采用了性能更好的路由保护方法来克服网络故障,然而,已有的路由保护方案普遍存在实现复杂度较高或者故障保护率偏低情况。针对上述问题,在SRv6实现了网络可编程性的基础上,提出一种基于SRv6的域内路由保护方案(research on intra-domain routing protection scheme based on SRv6,RPSRv6),方案首先提出了备份路径的计算规则,并根据备份路径计算规则在生成的增量最短路径树上,为所有受链路故障影响的源目的结点对计算备份路径,在此基础上,提出了Seg-ment List的计算规则,即计算出Segment List中SID的值与个数。在计算备份路径的过程中,每个受故障影响的结点和其他结点最多被访问一次,因此RPSRv6的时间复杂度具有较好的表现。实验结果表明,与已有的实现DC(downstream criterion)规则和U-Turn算法相比较,RPSRv6算法在故障保护率和路径拉伸度两个度量指标具有更好的实验效果,达到了100%的故障保护率并且在路径拉伸度方面达到了最优路径。

结构化加密图的最短路径查询

随着云计算的快速发展,数据用户将大量图数据外包给云以节约存储和管理成本。然而,外包数据的安全隐私问题是云计算面临的一大挑战。由于云是半诚实的,为保护敏感信息的隐私安全,数据拥有者希望在将图数据外包给云服务器之前对其加密,同时保留对加密的图数据进行查询和处理的能力。最短路径查询查找图中给定两节点之间的最短路径,是图应用中最基础的查询类型之一。目前已有许多研究者提出一系列高效的方案,以支持加密图上近似或精确最短距离查询、约束最短距离查询和top-k最近关键字查询,但支持最短路径查询的方案较少,且已有方案的存储与时间开销较大。本文提出一种支持在加密图上进行两节点间最短路径查询的结构化加密图方案。在本方案中,我们基于2-Hop标签技术构造支持有向图上最短路径查询的标签索引并加密,然后将加密的标签外包给云服务器。利用改进的保序编码算法编码距离值,实现加法运算和值的比较,提高最短路径查询的效率。在查询阶段,通过递归式地计算两节点间最短路径上的第一条边和最后一条边,最终输出完整的最短路径。安全性和性能分析证明本文方案是安全有效的,能以较小的存储和较高的查询效率实现两节点间的最短路径查询并保护图数据的隐私。

融合物品转换关系和时序信息的会话推荐算法

针对现有图神经网络会话推荐算法忽略了各类辅助信息,导致不能准确地建模会话序列的问题,提出了一种融合物品的转换关系和时序信息的会话推荐算法(RTSR)。首先利用图网络结构得到任意两个节点之间的最短路径序列,经过双向门控循环单元(GRU)将其编码为对应物品之间的转换关系,再结合自注意力机制从图的角度捕捉会话的全局依赖信息。同时设计了一种无损图编码方案来缓解会话图编码过程中信息损失的问题。该方案将会话序列中的时序信息进行合理的量化,并将其作为会话图中边的权重,再结合门控图神经网络获取会话的局部依赖信息。最后,线性组合全局依赖信息和局部依赖信息并结合反向位置信息,最终生成用户对物品的兴趣偏好,并给出推荐列表。在公共基准数据集Gowalla和Diginetica上与SR-GNN、GC-SAN、GCE-GNN等主流模型进行性能对比实验,结果表明RTSR在平均倒数排名方面分别至少提高了6.13%和1.58%,同时推荐精准度方面也有相应的提高。

基于人工势场引力因子的机械臂避障规划算法

针对机械臂的安全避障问题,提出一种基于人工势场引力因子的机械臂最短避障路径规划模型。研究算法中各个参数对机械臂末端运动路径的影响;构建引力因子,提出一种基于引力因子的最短避障路径规划模型,利用梯度下降法求解机械臂末端的最短避障路径及其最优解;研究分析不同障碍物大小和位置的最短路径特征,以工业SCARA机器人的平面模型分析关节角度路径特征。实验结果表明,模型参数决定避障路径的弧度变化。所提算法能够适应障碍物位置和大小的变化,使机械臂末端以最短路径避障的同时,其运动轨迹可以与障碍物相切。

基于机器学习算法的卷烟营销智能客户拜访策略研究

为提高卷烟行业客户经理的工作效率和服务质量,提出一种基于机器学习算法的卷烟营销智能客户拜访策略。在构建卷烟客户价值分类模型的基础上,利用K均值聚类机器学习算法对零售客户进行分类,合理设置LKH超启发算法和Dijkstra最短路径算法的参数,对客户经理拜访路径进行最优规划和智能导航。仿真结果表明,基于机器学习算法的卷烟营销智能客户拜访策略显著提高了客户经理人均拜访户数、商户满意度,大大缩减了户均在途时间和商户拜访服务覆盖周期。文中提出的策略有助于推动卷烟营销工作质量变革、效率变革和动力变革。

时变交通拥挤和需求随机的移动设施运营优化

为了优化移动设施(Mobile Facility,MF)的运营,在充分考虑时变交通状况和用户需求随机性的基础上,构建了一个两阶段随机规划模型,以期为决策者提供有力的工具。在第一阶段,模型针对MF的数量、时刻表和路径进行决策;第二阶段则聚焦于用户需求的分配和未满足服务量的确定。在求解此模型的过程中,本研究结合了时间依赖最短路径算法与L-shaped算法。在解决MF的移动路径和用户到达服务点的时间依赖最短路径问题时,将时变路段行驶速度离散化为分段函数,使得路段行驶时间成为连续分段线性函数,并且满足网络先进先出的原则,从而可以修改现有最短路径算法高效求解时间依赖最短路径。在L-shaped算法中,视一阶段模型为主问题,二阶段模型为子问题。首先通过求解主问题获得一阶段的决策变量,然后利用这些变量求解子问题,为主问题生成最优割。通过主、子问题的迭代交互,实现了对模型全局最优解的收敛,同时,通过加入有效不等式,使得算法能够快速收敛。在上海市嘉定区COVID-19核酸检测服务的MF实例中,对所提出的模型和算法进行了实证研究。结果表明:多割L-shaped算法结合有效不等式显著提升求解效率;同时,随着用户需求分布情况数量的增加,完美信息期望值和随机解价值均显著增加,这强调了在决策过程中获取准确信息和考虑时变交通状况与需求随机性的重要性。

远程联合打击下防空火力单元机动路线预测研究

红蓝双方演习进攻作战中,为全面夺取战场制空权,通常将蓝方防空火力单元作为首波重点打击目标,因此如何准确预测蓝方防空火力单元活动规律,科学设计联合侦察打击行动具有重要意义。首先,系统分析防空火力单元所采用的机动保障模式,结合防御能力定义给出防御能力计算公式并引入栅格网络模型完成定量计算,基于保障范围约束、阵地资源约束以及机动流程约束,面向实际保障需求,以最短机动路线和最高防御能力为优化目标,建立了适用于地面防空火力单元机动路线的预测模型。其次,针对所构建的非线性模型求解难题,提出了模型线性化转换和求解方法。然后,在最优转移路线的基础上,设计了一种构建机动路线库的算法,从而生成蓝方机动路线的概率预测方案,解析蓝方防空火力单元的机动规律。最后,基于案例仿真,验证了所设计模型和方法的可行性和全局高效性,可实现对蓝方防空火力单元机动路线的有效预测。

基于分布式SDN的机动通信系统拓扑发现方法

针对目前传统机动通信系统、主流软件定义网络(software defined network,SDN)的拓扑发现方法不适合基于分布式SDN的机动通信系统这一问题,遵循OpenFlow拓扑发现算法(OpenFlow discovery protocol,OFDP)移植传输控制协议/网际协议(transmission control protocol/Internet protocol,TCP/IP)相关协议到SDN网络的研究思路,对开放最短路径优先(open shortest path first,OSPF)协议进行优化,精简协议状态机、优化协议报文、增加协议功能并设计拓扑发现算法,提出一种适合基于分布式SDN的机动通信系统的拓扑发现方法,并搭建仿真实验平台进行验证。实验结果表明,优化后OSPF协议适应于分布式SDN网络,网络拓扑建链时间降低80%且重新收敛时间显著降低,建链开销平均每秒接收字节数、发送字节数分别下降了31.7%和21.5%,维持开销平均每秒收发字节数降低了45%,增加了收集信道种类等网络信息的新功能。

低轨大型星座分布式数据接收资源调度方法

许多监视与早期预警应用通过具备高时效性的对地观测数据实现。低轨大型星座观测数据接收任务调度的主要挑战是卫星数量大,中心化资源调度冲突消解面临困难。为此,提出一种新的分布式数据接收资源调度方法。首先,基于星间与星地链路融合构建卫星与地面设备之间的分布式传输链路,在卫星、设备、链路组成的无向网络图中,计算数据下传任务期间分布式链路的最短路径及其持续时长;其次,针对由每个设备的最短路径时间窗口合并构成的集合,利用Q学习方法求解数据接收完成率的优化问题。仿真测试结果表明,在典型的数据接收场景下,采用Q学习求解的数据接收完成率优于“先可见先跟踪”的基准资源调度方法,提升接近1%;与仅使用境内地面站的数据接收资源调度相比,数据接收完成率提升超过50%。

复杂背景下的结构光条纹中心提取算法研究

线结构光三维扫描建模系统中最关键的一步是提取光条中心线,但环境中各种因素的干扰给中心线提取带来困难。针对线结构光条纹图像存在光斑干扰、光强分布不均、光条宽度差别大、背景复杂等多种问题,提出解决方案。首先采用Otsu对结构光图像二值化;其次采用改进DBSCAN(density-based spatial clustering of applications with noise)算法保留核心点,去除边界点和噪声点;最后将核心点作为输入,构建图数据结构,采用适用于线结构光条纹图像的最短路径搜索算法得到光条中心线。实验结果表明,该算法运行时间在150 ms以内,误差在0.2像素以内,并适用于多种复杂环境,满足实时性、准确性和稳定性的要求。

面向枢纽机场的多因素滑行路径规划综合研究

针对枢纽机场滑行道容量不足问题,结合安全间隔、冲突解脱和公平性原则,以滑行路径最短作为优化目标,考虑燃油消耗和废气排放,建立滑行路径规划模型。采用Dijkstra算法将滑行路径转化为邻接矩阵,以加权的方式进行冲突解脱,在保证滑行道零冲突的前提下,减少总的滑行距离。以国内某枢纽机场2018年某日18:00—19:00内的实际运行数据结合19个跑道节点、71个滑行道节点进行验证分析。结果表明,提出的滑行路径规划方法可行,可提高机场场面滑行效率,有效降低油耗量及污染物排放。

考虑行程时间相关性的可靠最短路径算法

可靠最短路径(RSP)问题反映了出行时间的可变性,比只考虑平均出行时间的标准最短路径问题更加实际可行。本文提出了一种考虑路段行程时间相关性的均值-标准偏差RSP问题的求解思路。该算法采用拉格朗日代入和协方差矩阵分解技术,解决了混合整数非线性规划(MINLP)的非线性和不可加性带来的困难。将该问题分解为标准最短路径问题和凸优化问题,证明了凸优化问题的最优解,并将拉格朗日乘子范围与协方差矩阵的特征值联系起来,提出采用次梯度法进行拉格朗日乘子更新。该算法能降低了原问题的复杂性,可扩展到大型网络。