I am trying to know if there is a notion of "distance" or pseudo-metric between markov-chains or graphs. For the purpose of the question, the graph is weighted, and can be considered as labelled, so it is not exactly the graph-isomorphism problem. Consider 2 graphs or 2 reversible Markov-chains of same node size. The graph G is G(V,E), with each edge carrying an edge weight.
Equivalent picture for Markov chain: The set of vertices V form the domain of Markov chain. The transition matrix of the markov chain is given by the weighted adjacency matrix of the graph.
My interest in this problem comes from problem of clustering: Using graph Laplacian techniques, one can cluster a given graph. So any distance should reflect the clustering behavior, i.e. if two graphs give similar clusters, they should be closer than two random graphs.
Relatedly, if one wants to modify the edge weights of the graphs (or equivalently, the transition probabilities of the Markov chains) to morph one graph to the other, some sort of gradient flow could be envisioned. E.g. Ricci flow type of object is one example.
I am aware of recent literature by Ollivier, Maas and related authors. However, it seems like a distance on Markov chains is missing.
