In this article, we propose a simple rule that generates scale-free networks with very large clustering coefficient and very small average distance. These networks are called random Apollonian networks (RANs) as they can be considered as a variation of Apollonian networks. We obtain the analytic results of power-law exponent $\gamma =3$ and clustering coefficient $C=\frac{46}{3}-36\ln \frac{3}{2}\approx 0.74$, which agree with the simulation results very well. We prove that the increasing tendency of average distance of RANs is a little slower than the logarithm of the number of nodes in RANs. Since most real-life networks are both scale-free and small-world networks, RANs may perform well in mimicking the reality. The RANs possess hierarchical structure as $C\left(k\right)\sim k^{-1}$ that are in accord with the observations of many real-life networks. In addition, we prove that RANs are maximal planar networks, which are of particular practicability for layout of printed circuits and so on. The percolation and epidemic spreading process are also studied and the comparisons between RANs and Barabási-Albert (BA) as well as Newman-Watts (NW) networks are shown. We find that, when the network order $N$ (the total number of nodes) is relatively small (as $N\sim {10}^4$), the performance of RANs under intentional attack is not sensitive to $N$, while that of BA networks is much affected by $N$. And the diseases spread slower in RANs than BA networks in the early stage of the suseptible-infected process, indicating that the large clustering coefficient may slow the spreading velocity, especially in the outbreaks.

• Received 30 September 2004

DOI:https://doi.org/10.1103/PhysRevE.71.046141