High Degree Vertices, Eigenvalues and Diameter of Random Apollonian Networks

Details High Degree Vertices, Eigenvalues and Diameter of Random Apollonian Networks High Degree Vertices, Eigenvalues and Diameter of Random Apollonian Networks

2011-04-27

arxiv.org/abs/1104.5259v3

Computer Science

Social and Information Networks

(1) 18 pages, 6 figures (2) Updates in 2nd version: added references, corrected typos and simplifications. For more details ch

Scientific paper

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$ be the degrees of the $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}$ and for $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))\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) \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.

Affiliated with

Also associated with

No associations

Rating

High Degree Vertices, Eigenvalues and Diameter of Random Apollonian Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with High Degree Vertices, Eigenvalues and Diameter of Random Apollonian Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High Degree Vertices, Eigenvalues and Diameter of Random Apollonian Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-448729