论文标题
通用的最佳路径和重量分布通过网络上随机步行的巨大偏差揭示
Generalized optimal paths and weight distributions revealed through the large deviations of random walks on networks
论文作者
论文摘要
理论和实际兴趣的许多问题与在网络中找到最短（或其他最佳）路径有关，通常在存在某些障碍或约束的情况下。某种相关类别的问题的重点是寻找权重的最佳分布，对于给定的连接拓扑，最大程度地提高了某种流量或最小化给定的成本函数。我们表明，可以通过分析随机步行的大差异功能来解决这两组问题。具体而言，对轨迹集合的研究使我们能够通过辅助随机过程（广义的DOOB变换）找到最佳的路径或设计最佳加权网络。与标准方法相反，路径不限于最短路径，并且权重不一定要优化给定的功能。实际上，可以将路径和权重量身定制为具有时间集成的可观察到的给定统计数据，该统计数据可能是活动或电流，或局部功能，以标志着随机助行器通过给定节点或链接的传递。我们通过在存在障碍的情况下探索最佳路径的探索来说明这一想法，以及在局部可观察物的约束下优化流量的网络。
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). In contrast to standard approaches, 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.
