On the Structure and Computation of Random Walk Times in Finite Graphs
From MaRDI portal
Abstract: We consider random walks in which the walk originates in one set of nodes and then continues until it reaches one or more nodes in a target set. The time required for the walk to reach the target set is of interest in understanding the convergence of Markov processes, as well as applications in control, machine learning, and social sciences. In this paper, we investigate the computational structure of the random walk times as a function of the set of target nodes, and find that the commute, hitting, and cover times all exhibit submodular structure, even in non-stationary random walks. We provide a unifying proof of this structure by considering each of these times as special cases of stopping times. We generalize our framework to walks in which the transition probabilities and target sets are jointly chosen to minimize the travel times, leading to polynomial-time approximation algorithms for choosing target sets. Our results are validated through numerical study.
Cited in
(6)- Eigentime identities for random walks on a family of treelike networks and polymer networks
- Decomposing hitting times of walks on graphs into simpler ones
- Constrained minimum passage time in random geometric graphs
- scientific article; zbMATH DE number 1241390 (Why is no real title available?)
- Counting Walks and Graph Homomorphisms via Markov Chains and Importance Sampling
- A first hitting time approach to finding effective spreaders in a network
This page was built for publication: On the Structure and Computation of Random Walk Times in Finite Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5211207)
