Randomized shortest paths (RSP) are a tool developed in recent years for different graph and network analysis applications, such as modelling movement or flow in networks. In essence, the RSP framework considers the temperature-dependent Gibbs-Boltzmann distribution over paths in the network. At low temperatures, the distribution focuses solely on the shortest or least-cost paths, while with increasing temperature, the distribution spreads over random walks on the network. Many relevant quantities can be computed conveniently from this distribution, and these often generalize traditional network measures in a sensible way. However, when modelling real phenomena with RSPs, one needs a principled way of estimating the parameters from data. In this work, we develop methods for computing the maximum likelihood estimate of the model parameters, with focus on the temperature parameter, when modelling phenomena based on movement, flow, or spreading processes. We test the validity of the derived methods with trajectories generated on artificial networks as well as with real data on the movement of wild reindeer in a geographic landscape, used for estimating the degree of randomness in the movement of the animals. These examples demonstrate the attractiveness of the RSP framework as a generic model to be used in diverse applications.
翻译:随机最短路径(RSP)是近年来为不同图表和网络分析应用开发的工具,例如网络中的模型移动或流动。实质上,RSP框架考虑了网络中基于温度的Gibbs-Boltzmann分布路径。在低温下,分布仅侧重于最短或费用最低的路径,而随着温度的提高,分布则分散在网络上的随机行走中。许多相关数量可以从这种分布中方便地计算出来,而且往往以合理的方式将传统网络测量尺度加以概括。然而,在与RSP模拟真实现象时,需要有一个原则性的方法来估计数据参数。在这项工作中,我们制定方法来计算模型参数的最大可能性估计,重点是温度参数,在根据移动、流动或扩散过程进行模拟时,我们用人工网络生成的轨迹以及用于估计动物移动随机性程度的关于野生驯鹿运动的真实数据来测试衍生方法的有效性。这些例子显示了RSP框架作为多种应用中通用模型的吸引力。