General model for Apollonian networks

Zhongzhi Zhang, Lili RongarXiv 2005 · DOI · arXiv

Abstract

We introduce a general deterministic model for Apollonian Networks in an iterative fashion. The networks have small-world effect and scale-free topology. We calculate the exact results for the degree exponent, the clustering coefficient and the diameter. The major points of our results indicate that (a) the degree exponent can be adjusted in a wide range, (b) the clustering coefficient of each individual vertex is inversely proportional to its degree and the average clustering coefficient of all vertices approaches to a nonzero value in the infinite network order, and (c) the diameter grows logarithmically with the number of network vertices.

Introduction

Most real-world networks—ranging from the internet's infrastructure to social circles and protein interactions—exhibit three universal characteristics: scale-free topology, high clustering, and the small-world effect. While stochastic models like the Barabási-Albert model can replicate these traits, they often lack the analytical tractability required for exact mathematical proofs. Conversely, existing deterministic models are often too rigid to capture the diversity of real-world systems. This paper bridges this gap by introducing a generalized deterministic model for Apollonian networks that allows for precise tuning of structural properties.

Model Construction

The proposed model is inspired by the geometric concept of Apollonian packing, where circles are nested within the gaps of larger touching circles.

Apollonian circle packing illustrating the geometric basis of the network model.

The network is constructed iteratively:

  1. Initial State: Begin with a clique (fully connected group) of $d+2$ vertices.
  2. Iterative Step: In each subsequent step, for every $(d+1)$-clique created in the previous step, $m$ new vertices are added.
  3. Connectivity: Each new vertex connects to all vertices within its respective $(d+1)$-clique.

By introducing the parameter $m$ alongside the dimension $d$, the model generalizes previous Apollonian frameworks (which were restricted to $m=1$), providing a flexible mechanism to adjust the network's growth rate and density.

Network Properties and Results

The authors derive exact analytical solutions for the network's fundamental properties, demonstrating its utility in simulating diverse real-world systems.

Degree Exponent

The model produces a scale-free topology where the degree distribution follows a power law. The degree exponent is found to be $\gamma \approx 1 + \frac{\ln[m(d+1)]}{\ln(md)}$. By adjusting $m$ and $d$, the "top-heaviness" of the network hubs can be precisely calibrated.

Clustering Coefficient

A defining feature of this model is its high clustering. The clustering coefficient of a vertex is inversely proportional to its degree ($C(k) \sim 1/k$), a hallmark of hierarchical networks where small, dense groups organize into larger, less dense structures.

Average clustering coefficient $C$ as a function of parameters $m$ and $d$.

As shown in Figure 2, the average clustering coefficient $C$ remains high and converges to a nonzero constant as the network size approaches infinity. For a 2D model ($d=2$), $C$ is approximately 0.8284, significantly higher than what is observed in random network models. However, the relationship between $C$, $d$, and $m$ is non-monotonic, suggesting a complex dependence that warrants further research.

Small-World Effect

The diameter of the network—the longest shortest path between any two nodes—grows logarithmically with the total number of vertices $N$. This mathematically confirms that the model successfully captures the small-world phenomenon.

Conclusion

This generalized Apollonian model provides a robust mathematical framework for studying complex networks. By allowing for the tuning of the degree exponent and maintaining high clustering, the model offers a deterministic alternative to stochastic growth models. Future research may explore the introduction of stochastic elements to better simulate the inherent randomness of real-world network growth while maintaining the analytical advantages of the Apollonian framework.

Summary updated

Abstract

We introduce a general deterministic model for Apollonian Networks in an iterative fashion. The networks have small-world effect and scale-free topology. We calculate the exact results for the degree exponent, the clustering coefficient and the diameter. The major points of our results indicate that (a) the degree exponent can be adjusted in a wide range, (b) the clustering coefficient of each individual vertex is inversely proportional to its degree and the average clustering coefficient of all vertices approaches to a nonzero value in the infinite network order, and (c) the diameter grows logarithmically with the number of network vertices.
BibTeX
@misc{zhang2005general,
  author = {Zhongzhi Zhang and Lili Rong},
  title = {{General model for Apollonian networks}},
  year = {2005},
  eprint = {cond-mat/0512229},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/cond-mat/0512229},
}
Figure