High Degree Vertices, Eigenvalues and Diameter of Random Apollonian Networks

Abstract

In this work we analyze basic properties of Random Apollonian Networks \cite{zhang,zhou}, a popular stochastic model which generates planar graphs with power law properties. Specifically, let $k$ be a constant and ${\Delta }_1\ge {\Delta }_2\ge ..\ge {\Delta }_k$ be the degrees of the $k$ highest degree vertices. We prove that at time $t$, for any function $f$ with $f(t)\to +\infty$ as $t\to +\infty$, $\frac{t^{1/2}}{f(t)}\le {\Delta }_1\le f(t)t^{1/2}$ and for $i=2,...,k=O(1)$, $\frac{t^{1/2}}{f(t)}\le {\Delta }_i\le {\Delta }_{i-1}-\frac{t^{1/2}}{f(t)}$ with high probability (\whp). Then, we show that the $k$ largest eigenvalues of the adjacency matrix of this graph satisfy ${\lambda }_k=(1\pm o(1)){\Delta }_k^{1/2}$ \whp. Furthermore, we prove a refined upper bound on the asymptotic growth of the diameter, i.e., that \whp the diameter $d(G_t)$ at time $t$ satisfies $d(G_t)\le \rho \log t$ where $\frac{1}{\rho }=\eta$ is the unique solution greater than 1 of the equation $\eta -1-\log \eta =\log 3$. Finally, we investigate other properties of the model.

(1) 18 pages, 6 figures (2) Updates in 2nd version: added references, corrected typos and simplifications. For more details check http://www.math.cmu.edu/~ctsourak/apolarxiv.txt

References in corpus (4)

• The diameter of the world wide web
• Maximal planar networks with large clustering coefficient and power-law degree distribution
• Self-similar disk packings as model spatial scale-free networks
• The Degree Distribution of Random k-Trees