Apollonian Networks: Simultaneously Scale-Free, Small World, Euclidean, Space Filling, and with Matching Graphs

We introduce a new family of networks, the Apollonian networks, that are simultaneously scale-free, small-world, Euclidean, space filling, and with matching graphs. These networks describe force chains in polydisperse granular packings and could also be applied to the geometry of fully fragmented porous media, hierarchical road systems, and area-covering electrical supply networks. Some of the properties of these networks, namely, the connectivity exponent, the clustering coefficient, and the shortest path are calculated and found to be particularly rich. The percolation, the electrical conduction, and the Ising models on such networks are also studied and found to be quite peculiar. Consequences for applications are also discussed.

Figure 1

(a) Classical Apollonian packing. (b) Apollonian network (AN); first, second, and third generation are symbols $◯$, $\blacksquare$, and $•$, respectively.

Figure 2

Shortest path $l$ as a function of the number of sites $N$. The solid line is a guide to the eye with slope $3/4$. The inset shows the semilog plot of the clustering coefficient $C$ as a function of $N$. The dashed line is a guide to the eye for $C=0.828$, observed at large values of $N$.

Figure 3

Conductance $G$ as function of the number $N$ of sites when a potential is applied either between the center and all the sites of the last generation (upper curve) or between two corners of the network (lower curve). The inset shows the distribution of local currents for the first case.

Figure 4

Double logarithmic plot of the percolation threshold $p_c$ as function of the inverse system size $N$.

Figure 5

Double logarithmic plot of the critical temperature as function of the generation number $n$ for different exponents $\alpha$.