I actually managed to derive an analytical expression for the (shortest) distance between nodes, which you can find here:

https://www.researchgate.net/publication/379118066_Exact_analytic_expressions_for_discrete_first-passage_time_probability_distributions_in_Markov_networks