Skip to main content
MathOverflow

Return to Question

Bumped by Community user
Clarified Graph/Markov chain terminology
Source Link
Chain12
Chain12
  • 51
  • 2

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 givengive 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 go frommorph 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.

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 can considered as labelled, so it is not exactly the graph-isomorphism problem. Consider 2 graphs or 2 reversible Markov-chains of same node size.

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 given 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 go from 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.

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.

Source Link
Chain12
Chain12
  • 51
  • 2

Distance on Markov-chains/graphs and discrete Ricci-flow

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 can considered as labelled, so it is not exactly the graph-isomorphism problem. Consider 2 graphs or 2 reversible Markov-chains of same node size.

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 given 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 go from 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.