Self-similar disk packings as model spatial scale-free networks

The network of contacts in space-filling disk packings, such as the Apollonian packing, is examined. These networks provide an interesting example of spatial scale-free networks, where the topology reflects the broad distribution of disk areas. A wide variety of topological and spatial properties of these systems is characterized. Their potential as models for networks of connected minima on energy landscapes is discussed.

Figure 1

An Apollonian packing of disks within a circle.

Figure 2

(Color online) The development of the 2D Apollonian network inside the interstice between three mutually touching disks, as the number of generations increases. In each picture, the network is overlaid on the underlying packing.

Figure 3

The dependence of the vertex betweenness on degree for the Apollonian network with $t=8$. There are points representing each disk and the line connects the average values for a given $k$.

Figure 4

Comparison of $k_{\mathrm{nn}}∕k_{\mathrm{nn}}^{\mathrm{uncorr}}$ for the 2D Apollonian network to that for randomized versions of the networks. Lines corresponding to different values of $t$ ( $t=7–15$ and 7–8 for the Apollonian and randomized networks, respectively) have been plotted to emphasize the universal form of this function for the Apollonian network.

Figure 5

Assortativity coefficients, $r_k$ and $r_A$, as a function of the number of generations $t$. The solid lines are for the 2D Apollonian network, and the dashed lines for randomized versions of these networks with the same degree distribution.

Figure 6

The best division of the 2D Apollonian packing into communities for $t=6$. The disks in the different communities have been displaced with respect to each other for clarity. The modularity $Q=0.5938$.

Figure 7

A dendrogram showing the progressive division of the 2D Apollonian packing into communities for $t=6$ as those sets of edges with largest edge betweenness are removed. At right no edges have been removed and there is a single community of size $n_v$, whereas at left all edges have been removed and there are $n_v$ communities of size 1. The number of steps in which sets of edges have been removed increases linearly from right to left. In total, 84 sets of edges were removed. The threefold symmetry of the packing is retained throughout this process. The vertical dashed line indicates the set of communities with largest $Q$. The inset shows how $Q$ varies as the network is broken up into communities.

Figure 8

A space-filling bearing between two half-planes. The pattern can be repeated to the left and to the right ad infinitum. In the nomenclature of Refs. 54, 55, 56, this packing is from Family 1 and has base loop size 4 and $n=m=2$. The half-planes at the top and bottom can be considered as disks with infinite radius.

Figure 9

(Color online) The development of the contact network for a subset of the packing in Fig. 8 initially consisting of four touching disks, one of which has infinite radius. The edges in the network connect the centers of the disks that touch. Those edges involving the infinitely large disk are parallel, but to emphasize that they do actually connect to the same node, a box has been added that enclosed the ends of these edges.

Figure 10

The correlation of disk area with degree for the 2D Apollonian packing (iterated to 15 generations). There is a dot representing each disk. The two lines with data points represent the average value of the area for a given degree, and correspond to both the normal and logarithmic averages. In addition, lines corresponding to ${(k∕k_{\max })}^{2.62}$ and ${(k∕k_{\max })}^{2.428}$ have been plotted for comparison.

Figure 11

(Color online) The average area of the disks that touch a disk against the area of that disk. The lines are binned averages for the Apollonian networks with $t=8$ and a randomized version of that network. There is a data point for each disk in the Apollonian packing. Those represented by a cross are in contact with at least one of the three initial disks, and those represented by a diamond are not.

Figure 12

(a) The cumulative size distribution of the disks for an Apollonian packing after a finite number of generations. The lines are labeled by their value of $t$, and an additional straight line with the exponent expected for the complete Apollonian packing has been added for comparison. (b) The cumulative degree distribution for a series of Apollonian networks where only disks with radii at least $x\%$ of that of the largest disk contribute. The lines are labeled by their value of $x$, and additional straight lines have been added for comparison, one of which has the exponent expected for the complete Apollonian packing.