Evolving Apollonian networks with small-world scale-free topologies

Zhongzhi Zhang, Lili Rong, Shuigeng ZhouPhysical 2006 · DOI · arXiv

Abstract: We propose two types of evolving networks: evolutionary Apollonian networks (EANs) and general deterministic Apollonian networks (GDANs), established by simple iteration algorithms. We investigate the two networks by both simulation and theoretical prediction. Analytical results show that both networks follow power-law degree distributions, with distribution exponents continuously tuned from 2 to 3. The accurate expression of clustering coefficient is also given for both networks. Moreover, the investigation of the average path length of EAN and the diameter of GDAN reveals that these two types of networks possess small-world feature. In addition, we study the collective synchronization behavior on some limitations of the EAN.

Introduction

In network science, researchers strive to model real-world systems like the internet, social circles, and biological pathways. These systems typically exhibit three core features: a scale-free distribution (where a few "hubs" have many connections), the small-world property (short separation between nodes), and high clustering.

While famous models like the Barabási-Albert (BA) model capture scale-free properties, they often fail to produce the high clustering seen in reality. Conversely, the Watts-Strogatz model captures clustering but isn't scale-free. Apollonian networks—based on ancient geometric circle-packing principles—offer a promising alternative. This paper addresses the need for a generalized framework that allows for "tunable" randomness and growth rules, bridging the gap between perfectly ordered and purely random structures.

The Apollonian Framework

The authors use iterative algorithms based on $d$-dimensional Apollonian packing to grow their networks. Two primary models are introduced:

  • Evolutionary Apollonian Networks (EAN): This model introduces a probability parameter $q$. In each step, every available "interstice" (a $d$-simplex or triangular gap) is filled with a new node with probability $q$. By varying $q$ from 0 to 1, the model transitions from a Random Apollonian Network (RAN) to a Deterministic Apollonian Network (DAN).
  • General Deterministic Apollonian Networks (GDAN): This model remains deterministic but introduces a parameter $m$, representing the number of new vertices added to each interstice per iteration.
The geometric basis of Apollonian networks: circle packing in 2D.

Key Results and Topological Properties

Through a combination of rigorous analytical derivations and numerical simulations (reaching sizes up to $N \approx 7000$ nodes), the authors verified several critical properties of these networks:

Tunable Heterogeneity

The most significant finding is that the power-law exponent $\gamma$ is not a fixed constant. Both models follow a power-law $P(k) \sim k^{-\gamma}$. For EANs, $\gamma$ is a function of the dimension $d$ and the probability $q$. For GDANs, $\gamma = 1 + \ln[m(d+1)]/\ln(md)$. By adjusting these parameters, researchers can tune $\gamma$ anywhere between 2 and 3, allowing the models to accurately mimic diverse real-world systems.

Cumulative degree distributions for EANs with different values of q, demonstrating the tunable scale-free nature.

Clustering and Small-World Features

Because these networks are built on simplices (like triangles or tetrahedrons), they are inherently highly clustered. The clustering coefficient $C$ remains high (often $>0.7$) even as the network grows, which is a much better fit for social networks than the BA model. Furthermore, the average path length (APL) for EANs and the diameter for GDANs both grow logarithmically with the number of nodes ($\sim \ln N$), confirming the small-world property.

Synchronizability

When studying collective synchronization behavior, the authors found that deterministic networks ($q=1$) are easier to synchronize than their random counterparts ($q \to 0$), even when they share the same average degree. This suggests that structural regularity, not just "small-worldness," plays a vital role in network dynamics.

Conclusion and Future Work

The EAN and GDAN models provide a robust theoretical framework for generating networks that are simultaneously scale-free, small-world, and highly clustered. While mathematically robust, future work could involve applying these models to specific real-world datasets—such as protein-interaction maps—to determine which parameters ($q$ or $m$) provide the best fit. Additionally, exploring the full range of $q$ could reveal more about how partial randomness affects network synchronization dynamics.

Summary updated

Abstract

We propose two types of evolving networks: evolutionary Apollonian networks (EANs) and general deterministic Apollonian networks (GDANs), established by simple iteration algorithms. We investigate the two networks by both simulation and theoretical prediction. Analytical results show that both networks follow power-law degree distributions, with distribution exponents continuously tuned from 2 to 3. The accurate expression of clustering coefficient is also given for both networks. Moreover, the investigation of the average path length of EAN and the diameter of GDAN reveals that these two types of networks possess small-world feature. In addition, we study the collective synchronization behavior on some limitations of the EAN.
BibTeX
@inproceedings{zhang2006evolving,
  author = {Zhongzhi Zhang and Lili Rong and Shuigeng Zhou},
  title = {{Evolving Apollonian networks with small-world scale-free topologies}},
  booktitle = {Physical},
  year = {2006},
  doi = {10.1103/physreve.74.046105},
}
Figure