一种用于查询时变最短路径上TOP-k关键顶点的延迟自适应神经网络

《Neural Networks》：A Delay-Adaptive Neural Network for Querying TOP-k Critical Vertices on Time-Dependent Shortest Paths

延迟自适应神经网络（DANN）在时间依赖网络中查询TOP-k关键顶点的研究，提出无需训练的权重网络架构，通过三类神经元（源周边、目的周边、中间神经元）实现信息动态扩散与同步，确保全局最优解的高效计算，并在真实路网数据验证有效性。

　　

徐志磊|张文文|黄伟|毕家倩

北京理工大学网络空间科学与技术学院，北京，100081，中国

摘要

本研究提出了一种延迟自适应神经网络（DANN），用于查询时变最短路径上的TOP-k个关键顶点（kCV）。传统的kCV查询通常基于具有固定边权的静态网络进行，而现实世界中的网络状态往往存在显著的时间依赖性。为了解决这一挑战，本文正式定义了时变网络上kCV查询的数学模型，并设计了一组延迟自适应神经元以及相应的DANN操作机制。根据kCV查询问题的特点，延迟自适应神经元被分为三种类型：源外围神经元模拟源顶点并为神经网络生成输入信息；目的地外围神经元模拟目的地顶点并输出kCV；中间神经元模拟其他顶点，完成信息的接收、处理和传播。这种方法具有多个优势：首先，DANN是一个无权重的计算网络，具有物理网络拓扑映射结构，无需训练，能够很好地适应不同规模和结构的时变网络中的kCV查询；其次，延迟自适应神经元的每个组件模块都具有确定性的计算逻辑，本质上是一个由确定性逻辑门组成的信息处理单元；第三，DANN架构赋予神经元并行计算能力和类似于芯片时钟的同步机制，显著提高了查询响应速度，同时确保获得全局最优解。最后，本文通过时间复杂度分析和正确性证明评估了该算法的性能。在真实道路网络数据上进行的比较实验验证了所提出方法的有效性和先进性。

引言

对网络统计特性的研究持续受到关注，特别是基于最短路径的查询（Alzboon, Khassawneh, Nagy, 2020; Cheng, Grossman, Qiu, Shen, 2013; Mihalak, Sramek, Widmayer, 2014; Ren, Ay, Kahveci, 2018; Routray, Sahin, Ferreira Da Rocha, Pinto, 2015）。然而，当应用于现实世界的网络时，传统方法面临重大挑战，主要是由于边权的时间依赖性。例如，在道路交通网络中，随着交通状况的变化，穿越同一道路段所需的行驶时间可能会发生变化（Qiu等人，2022）。为了解决这个问题，最近的研究提出了更具表现力的时变网络模型（Adamo, Gendreau, Ghiani, Guerriero, 2024; Delling, Nannicini, 2012; Leng, Yang, Wang, Hu, Wang, 2018; Ma, Tang, 2022; Yu, Qian, Hu, Chen, Wang, 2022）。这些模型在一定程度上缓解了时间变化带来的挑战，使经典的最短路径算法能够适应并提供更优的路由结果。

然而，对于非出行导向的用户（如服务提供商）来说，最短路径查询可能涉及超出路线优化的其他问题，包括识别结构上关键的位置。例如，如果从源点到目的地的所有最短路径都经过顶点，那么可以被视为一个关键顶点。在物流和路线优化中，最短路径上的关键位置可以帮助服务提供商选择站点（如加油站、便利店或供应点），从而实现有效的资源分配并提高服务覆盖范围。识别出的关键顶点还可以支持数据驱动的决策制定，例如设施选址规划和供应链管理。在城市规划和风险管理中，查询关键顶点可以让规划者识别交通瓶颈或高风险位置（如事故多发交叉口或拥堵的道路段）。此外，在涉及关键物资运输的紧急响应和对抗性场景中，快速识别关键顶点的能力有助于选择关键保障点，促进及时决策并增强系统韧性。基于这一观察，人们对识别最短路径上的关键顶点的问题给予了越来越多的关注。

据我们所知，关于识别最短路径上关键顶点的最新相关研究是Ma等人的工作（Ma等人，2018），该研究专注于静态图。他们的方法在预定义的静态网络上执行查询，以识别给定源-目的地对之间最短路径上的top-k个关键顶点（kCV）。虽然这种方法在静态环境中表现良好，但将其扩展到时变网络仍然具有挑战性，而且在时间依赖的边动态下发现关键顶点的问题仍未得到充分解决。

在Ma等人（Ma等人，2018）的工作基础上，本文将关键顶点查询问题从静态图扩展到时变网络。此外，我们取消了预定义顶点重要性的假设，从而能够更客观地评估顶点的重要性。在时变网络上的top-k关键顶点查询中，一个关键挑战是准确评估顶点的重要性，这需要计算给定源-目的地对之间的最短路径集合。尽管已有大量研究调查了时变网络中的最短路径计算，但现有方法在全局最优性和多条最短路径的枚举方面存在明显局限性。在现实世界场景中，旅行者可能需要在中间顶点等待以选择更有利的出发时间，且两个顶点之间可能存在多条最短路径，提供多种路由选择。然而，大多数现有方法要么忽略等待策略，要么仅关注单条最短路径，因此不适合用于识别时变网络中的关键顶点。

本研究提出了一种延迟自适应神经网络（DANN）框架，用于查询时变网络中最短路径上的top-k个关键顶点（kCV-TSPs）。该框架包括设计用于模拟网络时间特性的延迟自适应神经元。具体来说，源外围神经元代表查询中指定的源顶点并启动整个计算过程；目的地外围神经元对应于目的地顶点并生成最终的top-k个关键顶点。其余顶点被建模为中间神经元，它们通过聚合来自邻近神经元的信息来更新状态，并将更新后的状态传播给后续神经元，从而实现最短路径计算。DANN用于kCV-TSPs查询的核心机制基于信息扩散和传播。源外围神经元首先将状态信息传播给相邻的中间神经元。这些中间神经元存储接收到的信息，根据时间约束更新其内部状态，并将新生成的信息转发给它们的邻居。这种扩散过程一直持续到目的地外围神经元接收并处理传播的信息，最终输出kCV。

(1)

kCV-TSPs查询模型：我们通过引入kCV-TSPs查询模型，将kCV查询问题扩展到时变网络，并对该问题进行了系统的形式化和分析。据我们所知，这项工作是首次尝试研究时变最短路径上的kCV查询，明确结合了时间动态，以更好地反映现实世界的网络场景。

(2)

延迟自适应神经元：我们设计了三种类型的延迟自适应神经元，即源外围神经元、中间神经元和目的地外围神经元，它们分别构成所提出神经网络的输入层、中间层和输出层。源外围神经元包括状态存储层、状态生成层和输出层，负责启动网络计算。中间神经元包括输入层、状态更新层、状态存储层、状态生成层和输出层，实现最短路径计算的动态状态更新。目的地外围神经元进一步包含一个关键性计算层，用于识别kCV-TSPs。

(3)

延迟自适应神经网络：我们构建的延迟自适应神经网络与传统的神经架构（如DNN或CNN）根本不同，因为它不需要训练。网络结构根据底层应用场景自我组织，实现了从现实世界网络到神经表示的直接映射，增强了适应性。此外，所提出的算法利用了基于神经元的计算的固有并行性，从而提高了查询响应效率，同时确保了全局最优性。

本文的其余部分组织如下：第2节回顾相关工作。第3节介绍问题定义。第4节介绍延迟自适应神经网络的设计和相应的理论分析。第5节报告实验结果和讨论，第6节总结本文。

章节片段

顶点重要性

顶点重要性是在最短路径上查询关键顶点时的一个关键因素。文献中提出了几种评估顶点重要性的代表性指标（Ma等人，2018），下面简要回顾。

度：顶点的度（包括入度和出度）是指连接到该顶点的边数。在大多数情况下，度较高的顶点被认为更为关键。计算公式如下：

问题描述

为了准确获得给定时变网络上两个顶点之间的最短路径，以便进行TOP-k关键顶点查询，理解相关概念非常重要。

定义1 时变函数

如果函数ξ(t)的值是正实数，并且时间变量t是非负实数，则称ξ为时变函数。

[示例1] 设ξ(t)是一个时变函数，当时间变量t在区间[0,3)内时，其值为1

模型架构设计与分析

本节介绍了一个为kCV-TSPs设计的延迟自适应神经网络（DANN）架构和算法。此外，还分析了该算法的时间复杂度和正确性。表1列出了DANN中使用的符号及其解释，以便参考。

实验

在本节中，将DANN算法的性能与众所周知的TD-dijkstra（Cooke和Halsey，1966）、TD-ACO（Balseiro等人，2011）、TD-Astar（Nannicini等人，2008）、Axiomatic方法（TD-Axio）（Kontogiannis等人，2022b）、基本kCV查询方法（BM）和纯标记kCV查询方法（PLM）（Ma等人，2018）在六个公共道路网络（https://github.com/bstabler/TransportationNetworks）以及两个具有时间信息的真实世界道路网络（城市道路）上进行了比较。

结论

主要贡献：在本文中，我们提出了一种DANN框架，用于查询时变网络中最短路径上的TOP-k个关键顶点。与其他研究相比，DANN算法的主要贡献和优势如下：首先，提出了一种延迟自适应神经网络，用于查询时变网络中最短路径上的TOP-k个关键顶点。这种神经网络不需要任何训练，可以适应各种

CRediT作者贡献声明

徐志磊：撰写——原始草稿、方法论、形式分析、数据整理、概念化。张文文：撰写——原始草稿、方法论、概念化。黄伟：验证、监督、项目管理、资金获取、概念化。毕家倩：撰写——原始草稿、软件、资源、形式分析。

利益冲突声明

作者声明他们没有已知的财务利益或个人关系可能影响本文报告的工作。

致谢

本工作得到了国家自然科学基金的国家重大科学仪器设备发展项目（项目编号：62227805）、国家重点研发计划（项目编号：2023YFB2703700）和国家重点研发计划（项目编号：2023YFB3107300）的支持。