A Method for Geodesic Distance on Subdivision of Trees With Arbitrary Orders and Their Applications
Fei Ma, Ping Wang, Xudong Luo
Abstract
Geodesic distance, sometimes called shortest path length, has proven useful in a great variety of applications, such as information retrieval on networks including treelike networked models. Here, our goal is to analytically determine the exact solutions to geodesic distances on two different families of growth trees which are recursively created upon an arbitrary tree <inline-formula><tex-math notation="LaTeX">$\mathcal {T}$</tex-math></inline-formula> using two types of well-known operations, first-order subdivision and ( <inline-formula><tex-math notation="LaTeX">$1,m$</tex-math></inline-formula> )-star-fractal operation. Different from commonly-used methods, for instance, spectral techniques, for addressing such a problem on growth trees using a single edge as seed in the literature, we propose a novel method for deriving closed-form solutions on the presented trees completely. Meanwhile, our technique is more general and convenient to implement compared to those previous methods mainly because there are not complicated calculations needed. In addition, the closed-form expression of mean first-passage time ( <inline-formula><tex-math notation="LaTeX">$MFPT$</tex-math></inline-formula> ) for random walk on each member in tree families is also readily obtained according to connection of our obtained results to effective resistance of corresponding electric networks. The results suggest that the two topological operations above are sharply different from each other due to <inline-formula><tex-math notation="LaTeX">$MFPT$</tex-math></inline-formula> for random walks, and, however, have likely to show the similar performance, at least, on geodesic distance.