Gutiérrez Ricardo, Pérez-Espigares Carlos
Complex Systems Interdisciplinary Group, Department of Mathematics, Universidad Carlos III de Madrid, 28911 Leganés, Madrid, Spain.
Departamento de Electromagnetismo y Física de la Materia, Universidad de Granada, Granada 18071, Spain.
Phys Rev E. 2021 Feb;103(2-1):022319. doi: 10.1103/PhysRevE.103.022319.
Numerous problems of both theoretical and practical interest are related to finding shortest (or otherwise optimal) paths in networks, frequently in the presence of some obstacles or constraints. A somewhat related class of problems focuses on finding optimal distributions of weights which, for a given connection topology, maximize some kind of flow or minimize a given cost function. We show that both sets of problems can be approached through an analysis of the large-deviation functions of random walks. Specifically, a study of ensembles of trajectories allows us to find optimal paths, or design optimal weighted networks, by means of an auxiliary stochastic process (the generalized Doob transform). The paths are not limited to shortest paths, and the weights must not necessarily optimize a given function. Paths and weights can in fact be tailored to a given statistics of a time-integrated observable, which may be an activity or current, or local functions marking the passing of the random walker through a given node or link. We illustrate this idea with an exploration of optimal paths in the presence of obstacles, and networks that optimize flows under constraints on local observables.
许多具有理论和实际意义的问题都与在网络中寻找最短（或以其他方式最优）路径有关，这些网络中常常存在一些障碍物或约束条件。一类与之相关的问题侧重于寻找权重的最优分布，对于给定的连接拓扑结构，这种分布能使某种流量最大化或使给定的成本函数最小化。我们表明，这两类问题都可以通过对随机游走的大偏差函数进行分析来解决。具体而言，对轨迹系综的研究使我们能够借助一个辅助随机过程（广义杜布变换）来找到最优路径或设计最优加权网络。这些路径不限于最短路径，权重也不一定能使给定函数达到最优。实际上，路径和权重可以根据时间积分可观测量的给定统计特性进行调整，该可观测量可以是一种活动或电流，或者是标记随机游走者通过给定节点或链路的局部函数。我们通过探索存在障碍物时的最优路径以及在局部可观测量约束下优化流量的网络来说明这一思想。
