Analytical solution of average path length for Apollonian networks

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

Figure 1

(a) Second construction method of the Apollonian network. $A_{t+1}$, is obtained by joining three copies of $A_t$ denoted as $A_t^{\left(\phi \right)}$ $\left(\phi =1,2,3\right)$, which are connected to one another at the edge nodes (i.e., $X$, $Y$, $Z$, and $O$). Note that the central node is represented as $O$ (marker not visible). (b) Illustration of the recursive definition of node classification. From the node classification of $A_t^{\left(1\right)}$, $A_t^{\left(2\right)}$, and $A_t^{\left(3\right)}$, we can derive recursively the classification of nodes in network $A_{t+1}$.

Figure 2

Average path length ${\overline{d}}_t$ versus network order $N_t$ on a semilogarithmic scale. The solid line is a guide to the eye, which clearly shows that the APL scales logarithmically with the network size.