Quasi-metrics on graphs

In this paper we consider some questions of the theory and practice of mean first passage time quasi-metric, a generalized metric structure closely related to ergodic homogeneous Markov
chains. In particular, we consider the structure and properties of mean first passage time quasimetrics based on several graph models, including simple cycles, simple paths and their oriented
analogues.
The introduction contains the history of the problem and provides an overview of the main ideas and results presented in the article.
The second section gives basic concepts of the theory of Markov chains. In fact, a Markov chain is a mathematical model of some random process describing a sequence of possible events
in which the probability of each event depends only on the state attained in the previous event. This section collects basic definitions needed to consider the role of graph models in
the presentation and study of ergodic homogeneous Markov chains. The Markov chain can be depicted as an oriented weighted graph of transitions whose vertices correspond to the states of the chain and the arcs correspond to the transitions between them. The process will be ergodic if this weighted oriented graph is weakly connected, and the largest common divisor of the lengths of all its cycles is equal to 1. On the other hand, any connected graph can be used as a basis for building a model of the simplest Markov chain: if a vertex 𝑖 has degree 𝑘, all incident edges are converted into arcs with the weights 1/𝑘 . Moreover, in the second section the definition of the mean first passage time for an ergodic homogeneous Markov chain is given. The algorithm of finding the mean first passage time is analyzed in detail by using converging trees of the oriented graph, related to the transition matrix of the ergodic homogeneous Markov chain. At last, a mean first passage time is analyzed as the quasi-metric 𝑚 of mean first passage time
on the vertices 𝑉 = {1, 2, ..., 𝑛} of the oriented graph corresponding to the transition matrix of a given ergodic homogeneous Markov chain: 𝑚(𝑖, 𝑗) is the expected number of steps (arcs) for random wandering on the oriented graph Γ, starting at 𝑖, to reach 𝑗 for the first time. This quasi-metric has a number of important theoretical and applied properties.
The third section deals with the construction and research of mean first passage time quasimetrics for the undirected cycles 𝐶𝑛, 𝑛 ≥ 3. Examples of constructions of mean first passage
time quasi-metrics of undirected cycles for small values of 𝑛 are considered. Illustrations of the ”graphical“ procedure of building the matrix 𝑀 are given. Properties of the resulting generalized
metric structures are analyzed.
In the fourth section, similar considerations for mean first passage time quasi-metrics of the undirected paths 𝑃𝑛, 𝑛 ≥ 2, are represented.
The fifth section deals with the construction and research of mean first passage time quasimetrics for the directed (oriented) cycles 𝐶𝑛, 𝑛 ≥ 3. Examples of constructions of mean first
passage time quasi-metrics of undirected (oriented) cycles for small values of 𝑛 are considered.
Illustrations of the ”graphical“ procedure of building the matrix 𝑀 are given. Properties of the resulting generalized metric structures are analyzed.
In the sixth section, similar considerations for mean first passage time quasi-metrics of the directed (oriented) paths 𝑃𝑛, 𝑛 ≥ 2, are represented.
In the conclusion, the results of the work are summed up and possible directions of further research are outlined.

1. Deza, M.M., Deza, E.I., Dutour Sikiri´c, М. 2015, ”Polyhedral structures associated with quasimetrics“, Chebyshevskii sbornik, Vol. 16 (2), P. 79 – 92.

2. Deza, E., Mhanna, B. ”On special properties of some special quasi-metrics“, Chebyshevskii sbornik, Vol. 21 (1), P. 145 – 164.

3. Potapov, V.N. 1999, ”Information Theory. Coding of discrete probabilistic sources“, Novosibirsk: NSU center.

4. Chebotarev, P., Agaev, R. 2011, ”Matrix forest theorem and Laplacian matrices of orgraphs“, М.: LAP LAMBERT Academic publishing.

5. Shannon, K. 1963, ”Works on Information theory and Cybernetics“, M.: IL.

6. Catral, M., Neumann, M., Xu, J. 2005, ”Proximity in group inverses of M-matrices and inverses of diagonally dominant M-matrices“, Linear Algebra and its Applications, Vol. 409, P. 32 – 50.

7. Chebotarev, P. 2008, ”Spanning forest and the Golden ratio“, Discrete Applied Mathematics, Vol. 156, P. 813 – 821.

8. Chebotarev, P. 2013, ”Studying new classes of graph metrics“, in F. Nielsen and F. Barbaresco, editors, Proceedings of the SEE Conference ”Geometric Science of Information“ (GSI-2013),

9. Lecture Notes in Computer Science, LNCS 8085, P. 207 – 214.

10. Chebotarev, P., Agaev, R. 2002, ”Forest matrices around the Laplacian matrix“, Linear Algebra and its Applications, Vol. 356, P. 253 – 274.

11. Chebotarev, P., Deza, E. 2020, ”Hitting time quasi-metric and its forest representation“, Optimization Letters, Vol. 14, P. 291 – 307.

12. Chebotarev,P.Y., Shamis E.V. 1998, ”On proximity measures for graph vertices“, Automation and Remote Control, Vol. 59, P. 1443 – 1459.

13. Deza, E., Deza, M., Dutour Sikiri´c, M. 2016, ”Generalizations of Finite Metrics and Cuts“, World Scientific.

14. Deza, M., Deza, E. 2011, ”Cones of partial metrics“, Contributions to Discrete Mathematics, Vol. 6, P. 26 – 47.

15. Deza, M. M., Deza, E. 2016, ”Encyclopedia of Distances,“ Springer, Berlin - Heidelberg.

16. Deza, M., Deza, E., Vidali, J. 2012, ”Cones of weighted and partial metrics“, in Proceedings of the Internat. Conference on Algebra 2010: Advances in Algebraic Structures, P. 177 – 197.

17. Kirkland, S. J., Neumann, M. 2012, ”Group inverses of M-matrices and their applications,“ CRC Press.

18. Klein, D., Zhu, H. 1998, ”Distances and volumina for graphs“, Journal of Mathematical Chemistry, Vol. 23, P. 179 – 195.

19. Leighton, T., Rivest, R.L. 1983, ”The Markov chain tree theorem“, Computer Science Technical Report MIT/LCS/TM-249, Laboratory of Computer Science, MIT, Cambridge, Mass.

20. Leighton, T., Rivest, R.L. 1986, ”Estimating a probability using finite memory“, IEEE Transactions on Information Theory, Vol. 32, P. 733 – 742.

21. Wilson, W. 1931, ”On quasi-metric spaces“, American Journal of Mathematics, Vol. 53, P. 675–684.