A Method for Geodesic Distance on Subdivision of Trees with Arbitrary Orders and Their Applications

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 $\mathcal{T}$ using two types of well-known operations, first-order subdivision and ($1,m$)-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 ($MFPT$) 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 $MFPT$ for random walks, and, however, have likely to show the similar performance, at least, on geodesic distance.

References in corpus (10)

• Hierarchical structure and the prediction of missing links in networks
• Self-similarity of complex networks
• Self-similarity of complex networks and hidden metric spaces
• Exact mean first-passage time on the T-graph
• Determining mean first-passage time on a class of treelike regular fractals
• Growing complex network of citations of scientific papers -- measurements and modeling
• Shortest Path Discovery in the Multi-layered Social Network
• Efficiency analysis of diffusion on T-fractals in the sense of random walks
• Random walks on Fibonacci treelike models: emergence of power law
• Exact solutions for geodesic distance on treelike models with some constraints