High Degree Vertices, Eigenvalues and Diameter of Random Apollonian Networks

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 \geq \Delta_2 \geq … \geq \Delta_k$bethedegreesofthe$k$ highest degree vertices. We prove that at time $t$, for any function $f$ with $f(t) \rightarrow +\infty$as$t \rightarrow +\infty$,$\frac{t^{1/2}}{f(t)} \leq \Delta_1 \leq f(t)t^{1/2}$andfor$i=2,…,k=O(1)$,$\frac{t^{1/2}}{f(t)} \leq \Delta_i \leq \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)){\mathrm{\Delta }}_k^{1\mathrm{/}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) \leq \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.