A metric on directed graphs and Markov chains based on hitting probabilities

  • 2021-01-18 16:54:57
  • Zachary M. Boyd, Nicolas Fraiman, Jeremy L. Marzuola, Peter J. Mucha, Braxton Osting, Jonathan Weare
  • 0

Abstract

The shortest-path, commute time, and diffusion distances on undirected graphshave been widely employed in applications such as dimensionality reduction,link prediction, and trip planning. Increasingly, there is interest in usingasymmetric structure of data derived from Markov chains and directed graphs,but few metrics are specifically adapted to this task. We introduce a metric onthe state space of any ergodic, finite-state, time-homogeneous Markov chainand, in particular, on any Markov chain derived from a directed graph. Ourconstruction is based on hitting probabilities, with nearness in the metricspace related to the transfer of random walkers from one node to another atstationarity. Notably, our metric is insensitive to shortest and average walkdistances, thus giving new information compared to existing metrics. We usepossible degeneracies in the metric to develop an interesting structural theoryof directed graphs and explore a related quotienting procedure. Our metric canbe computed in $O(n^3)$ time, where $n$ is the number of states, and inexamples we scale up to $n=10,000$ nodes and $\approx 38M$ edges on a desktopcomputer. In several examples, we explore the nature of the metric, compare itto alternative methods, and demonstrate its utility for weak recovery ofcommunity structure in dense graphs, visualization, structure recovering,dynamics exploration, and multiscale cluster detection.

 

Quick Read (beta)

loading the full paper ...