A Metric on Directed Graphs and Markov Chains Based on Hitting Probabilities
DOI10.1137/20M1348315zbMath1467.05090arXiv2006.14482OpenAlexW3152893900MaRDI QIDQ4999367
Peter J. Mucha, Zachary M. Boyd, Jeremy L. Marzuola, Braxton Osting, Jonathan Weare, Nicolas Fraiman
Publication date: 6 July 2021
Published in: SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2006.14482
Directional data; spatial statistics (62H11) Computational methods in Markov chains (60J22) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms (68W40) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Inference from stochastic processes and spectral analysis (62M15) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Graph representations (geometric and intersection representations, etc.) (05C62) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)
Related Items (3)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Clustering and community detection in directed networks: a survey
- A variational approach to the consistency of spectral clustering
- Markov fundamental tensor and its applications to network analysis
- Laplacians and the Cheeger inequality for directed graphs
- Markov chain decomposition for convergence rate analysis
- Hitting time quasi-metric and its forest representation
- Mean curvature, threshold dynamics, and phase field theory on finite graphs
- Magnetic eigenmaps for the visualization of directed networks
- On the diffusion geometry of graph Laplacians and applications
- On resistance distance of Markov chain and its sum rules
- Commute times for a directed graph using an asymmetric Laplacian
- Diffusion maps
- Consistency of Cheeger and Ratio Graph Cuts
- Vector diffusion maps and the connection Laplacian
- Hitting and commute times in large graphs are often misleading
- A New Notion of Effective Resistance for Directed Graphs—Part I: Definition and Properties
- A New Notion of Effective Resistance for Directed Graphs—Part II: Computing Resistances
- Random Walks on Digraphs, the Generalized Digraph Laplacian and the Degree of Asymmetry
- Directed metrics and directed graph partitioning problems
- Markov Chains
- Community Detection and Stochastic Block Models
- Consistency of Dirichlet Partitions
- Spectral convergence of the connection Laplacian from random samples
- Effective Resistance Preserving Directed Graph Symmetrization
- Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps
- Link Evolution: Analysis and Algorithms
- Stratification as a General Variance Reduction Method for Markov Chain Monte Carlo
- Sharp Entrywise Perturbation Bounds for Markov Chains
This page was built for publication: A Metric on Directed Graphs and Markov Chains Based on Hitting Probabilities