Some Properties of Random Apollonian Networks

Abstract

In this work, we analyze fundamental properties of random Apollonian networks [Zhang et al. 06, Zhou et al. 05], a popular random graph model that generates planar graphs with power-law properties. Specifically, we analyze the degree distribution, the k largest degrees, the k largest eigenvalues, and the diameter, where k is a constant.

Notes

¹An event A_t holds with high probability if .

²The three initial vertices participate in one face fewer than their degree. However, this slight abuse leaves our main results unchanged and simplifies the exposition.

³There is a typo in [Broutin and Devroye 06]: in “ρ is the unique solution greater than 1 of ...” one should replace “greater than” with “less than,” based on the authors’ Theorem 1. We are grateful to Abbas Mehrabian for pointing this out.

⁴We analyze the case s₁, s₂ ≥ 4. The other case is treated in the same manner.