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

zbMATH Keywords

metric spaceMarkov chaindirected graph

Mathematics Subject Classification ID

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)

Kron Reduction and Effective Resistance of Directed Graphs ⋮ An Escape Time Formulation for Subgraph Detection and Partitioning of Directed Graphs ⋮ Hubs-biased resistance distances on graphs and networks

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