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 (32)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Hierarchical organization of modularity in metabolic networks
• Evolution of networks
• Characterization of complex networks: A survey of measurements
• Hierarchical Organization in Complex Networks
• Scale-Free Networks are Ultrasmall
• Pseudofractal Scale-free Web
• Deterministic Scale-Free Networks
• Average path length in random networks
• Average path length in uncorrelated random networks with hidden variables
• Maximal planar networks with large clustering coefficient and power-law degree distribution
• Fractal and Transfractal Recursive Scale-Free Nets
• A Geometric Fractal Growth Model for Scale Free Networks
• Inverted Berezinskii-Kosterlitz-Thouless Singularity and High-Temperature Algebraic Order in an Ising Model on a Scale-Free Hierarchical-Lattice Small-World Network
• 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
• Coherence in scale-free networks of chaotic maps
• Maximal planar scale-free Sierpinski networks with small-world effect and power-law strength-degree correlation
• High dimensional random Apollonian networks
• Metric structure of random networks
• Self-similarity, small-world, scale-free scaling, disassortativity, and robustness in hierarchical lattices
• High Dimensional Apollonian Networks
• Universal scaling of distances in complex networks
• Magnetic models on Apollonian networks
• Evolving Apollonian Networks with Small-world Scale-free topologies
• A general geometric growth model for pseudofractal scale-free web
• Griffiths singularities and algebraic order in the exact solution of an Ising model on a fractal modular network
• Degree-dependent intervertex separation in complex networks
• Correlations in random Apollonian network

Cited by in corpus (15)

• Spatial Networks
• 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
• Mapping Koch curves into scale-free small-world networks
• Fractal scale-free networks resistant to disease spread
• Average distance in a hierarchical scale-free network: an exact solution
• Counting spanning trees in self-similar networks by evaluating determinants
• Dynamics and Processing in Finite Self-Similar Networks
• Maximum matchings and minimum dominating sets in Apollonian networks and extended Tower of Hanoi graphs
• 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
• Degrees and distances in random and evolving Apollonian networks
• The Number of Spanning Trees in Apollonian Networks