A metric on directed graphs and Markov chains based on hitting probabilities
A metric on directed graphs and Markov chains based on hitting probabilities
复制标题
DOI：
10.1137/20m1348315
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Z. Boyd;Nicolas Fraiman;J. Marzuola;P. Mucha;B. Osting;J. Weare
中科院分区：
文献类型：
--
作者：
Z. Boyd;Nicolas Fraiman;J. Marzuola;P. Mucha;B. Osting;J. Weare
无向图上的最短路径、通勤时间和扩散距离在降维、路段预测和出行规划等方面有着广泛的应用。越来越多地，人们有兴趣使用来自马尔可夫链和有向图的数据的非对称结构，但很少有指标是专门适用于这一任务。我们介绍了一个度量的状态空间的任何遍历，有限状态，时间齐次马尔可夫链，特别是在任何马尔可夫链来自有向图。我们的建设是基于命中概率，在度量空间中的接近度相关的随机游走从一个节点转移到另一个平稳。值得注意的是，我们的度量是不敏感的最短和平均路径距离，从而提供新的信息相比，现有的指标。我们使用可能的退化的度量发展一个有趣的结构理论的有向图，并探讨相关的reprodenting程序。我们的度量可以在$O（n^3）$时间内计算，其中$n$是状态的数量，在示例中，我们在台式计算机上扩展到$n= 10，000 $个节点和$\approximat 38 M $条边。在几个例子中，我们探讨了度量的性质，将其与其他方法进行比较，并展示了其在稠密图，可视化，结构恢复，动态探索和多尺度聚类检测中的社区结构弱恢复方面的实用性。
The shortest-path, commute time, and diffusion distances on undirected graphs have been widely employed in applications such as dimensionality reduction, link prediction, and trip planning. Increasingly, there is interest in using asymmetric structure of data derived from Markov chains and directed graphs, but few metrics are specifically adapted to this task. We introduce a metric on the state space of any ergodic, finite-state, time-homogeneous Markov chain and, in particular, on any Markov chain derived from a directed graph. Our construction is based on hitting probabilities, with nearness in the metric space related to the transfer of random walkers from one node to another at stationarity. Notably, our metric is insensitive to shortest and average path distances, thus giving new information compared to existing metrics. We use possible degeneracies in the metric to develop an interesting structural theory of directed graphs and explore a related quotienting procedure. Our metric can be computed in $O(n^3)$ time, where $n$ is the number of states, and in examples we scale up to $n=10,000$ nodes and $\approx 38M$ edges on a desktop computer. In several examples, we explore the nature of the metric, compare it to alternative methods, and demonstrate its utility for weak recovery of community structure in dense graphs, visualization, structure recovering, dynamics exploration, and multiscale cluster detection.