Exact analytical solution of average path length for Apollonian networks

Abstract

The exact formula for the average path length of Apollonian networks is found. With the help of recursion relations derived from the self-similar structure, we obtain the exact solution of average path length, ${\bar{d}}_t$, for Apollonian networks. In contrast to the well-known numerical result ${\bar{d}}_t\propto (\ln N_t{)}^{3/4}$ [Phys. Rev. Lett. \textbf{94}, 018702 (2005)], our rigorous solution shows that the average path length grows logarithmically as ${\bar{d}}_t\propto \ln N_t$ in the infinite limit of network size $N_t$. The extensive numerical calculations completely agree with our closed-form solution.

8 pages, 4 figures

References in corpus (8)

• Fractal and Transfractal Recursive Scale-Free Nets
• Self-similar disk packings as model spatial scale-free networks
• A deterministic small-world network created by edge iterations
• Recursive graphs with small-world scale-free properties
• Maximal planar scale-free Sierpinski networks with small-world effect and power-law strength-degree correlation
• Self-similarity, small-world, scale-free scaling, disassortativity, and robustness in hierarchical lattices
• Griffiths singularities and algebraic order in the exact solution of an Ising model on a fractal modular network
• Correlations in random Apollonian network

Cited by in corpus (8)

• Standard random walks and trapping on the Koch network with scale-free behavior and small-world effect
• Exact solution of mean geodesic distance for Vicsek fractals
• Random walks on the Apollonian network with a single trap
• Random Sierpinski network with scale-free small-world and modular structure
• Fractal scale-free networks resistant to disease spread
• Average distance in a hierarchical scale-free network: an exact solution
• Infinitely Robust Order and Local Order-Parameter Tulips in Apollonian Networks with Quenched Disorder
• Contact graphs of disk packings as a model of spatial planar networks