Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA metric on directed graphs and Markov chains based on hitting probabilities
73
0
0.0
(
0
)
Added by
Zachary Boyd
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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 walk 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.
rate research
Read More
This paper establishes a Markov chain model as a unified framework for understanding information consumption processes in complex networks, with clear implications to the Internet and big-data technologies. In particular, the proposed model is the first one to address the formation mechanism of the trichotomy in observed probability density functions from empirical data of various social and technical networks. Both simulation and experimental results demonstrate a good match of the proposed model with real datasets, showing its superiority over the classical power-law models.
In this paper, we address the approximate minimization problem of Markov Chains (MCs) from a behavioral metric-based perspective. Specifically, given a finite MC and a positive integer k, we are looking for an MC with at most k states having minimal distance to the original. The metric considered in this work is the bisimilarity distance of Desharnais et al.. For this metric we show that (1) optimal approximations always exist; (2) the problem has a bilinear program characterization; and (3) prove that its threshold problem is in PSPACE and NP-hard. In addition to the bilinear program solution, we present an approach inspired by expectation maximization techniques for computing suboptimal solutions to the problem. Experiments suggest that our method gives a practical approach that outperforms the bilinear program implementation run on state-of-the-art bilinear solvers.
Let 0<alpha<1/2. We show that the mixing time of a continuous-time reversible Markov chain on a finite state space is about as large as the largest expected hitting time of a subset of stationary measure at least alpha of the state space. Suitably modified results hold in discrete time and/or without the reversibility assumption. The key technical tool is a construction of a random set A such that the hitting time of A is both light-tailed and a stationary time for the chain. We note that essentially the same results were obtained independently by Peres and Sousi [arXiv:1108.0133].
In the present paper, we construct quantum Markov chains (QMC) over the Comb graphs. As an application of this construction, it is proved the existence of the disordered phase for the Ising type models (within QMC scheme) over the Comb graphs. Moreover, it is also established that the associated QMC has clustering property with respect to translations of the graph. We stress that this paper is the first one where a nontrivial example of QMC over non-regular graphs is given.
In this paper we introduce a notion of spectral approximation for directed graphs. While there are many potential ways one might define approximation for directed graphs, most of them are too strong to allow sparse approximations in general. In contrast, we prove that for our notion of approximation, such sparsifiers do exist, and we show how to compute them in almost linear time. Using this notion of approximation, we provide a general framework for solving asymmetric linear systems that is broadly inspired by the work of [Peng-Spielman, STOC`14]. Applying this framework in conjunction with our sparsification algorithm, we obtain an almost linear time algorithm for solving directed Laplacian systems associated with Eulerian Graphs. Using this solver in the recent framework of [Cohen-Kelner-Peebles-Peng-Sidford-Vladu, FOCS`16], we obtain almost linear time algorithms for solving a directed Laplacian linear system, computing the stationary distribution of a Markov chain, computing expected commute times in a directed graph, and more. For each of these problems, our algorithms improves the previous best running times of $O((nm^{3/4} + n^{2/3} m) log^{O(1)} (n kappa epsilon^{-1}))$ to $O((m + n2^{O(sqrt{log{n}loglog{n}})}) log^{O(1)} (n kappa epsilon^{-1}))$ where $n$ is the number of vertices in the graph, $m$ is the number of edges, $kappa$ is a natural condition number associated with the problem, and $epsilon$ is the desired accuracy. We hope these results open the door for further studies into directed spectral graph theory, and will serve as a stepping stone for designing a new generation of fast algorithms for directed graphs.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
