Paper detail

Non-uniform random graphs on the plane: A scaling study

We consider random geometric graphs on the plane characterized by a non-uniform density of vertices. In particular, we introduce a graph model where $n$ vertices are independently distributed in the unit disc with positions, in polar coordinates $(l,θ)$, obeying the probability density functions $ρ(l)$ and $ρ(θ)$. Here we choose $ρ(l)$ as a normal distribution with zero mean and variance $σ\in(0,\infty)$ and $ρ(θ)$ as an uniform distribution in the interval $θ\in [0,2π)$. Then, two vertices are connected by an edge if their Euclidian distance is less or equal than the connection radius $\ell$. We characterize the topological properties of this random graph model, which depends on the parameter set $(n,σ,\ell)$, by the use of the average degree $\left\langle k \right\rangle$ and the number of non-isolated vertices $V_\times$; while we approach their spectral properties with two measures on the graph adjacency matrix: the ratio of consecutive eigenvalue spacings $r$ and the Shannon entropy $S$ of eigenvectors. First we propose a heuristic expression for $\left\langle k(n,σ,\ell) \right\rangle$. Then, we look for the scaling properties of the normalized average measure $\left\langle \overline{X} \right\rangle$ (where $X$ stands for $V_\times$, $r$ and $S$) over graph ensembles. We demonstrate that the scaling parameter of $\left\langle \overline{V_\times} \right\rangle=\left\langle V_\times \right\rangle/n$ is indeed $\left\langle k \right\rangle$; with $\left\langle \overline{V_\times} \right\rangle \approx 1-\exp(-\left\langle k \right\rangle)$. Meanwhile, the scaling parameter of both $\left\langle \overline{r} \right\rangle$ and $\left\langle \overline{S} \right\rangle$ is proportional to $n^{-γ} \left\langle k \right\rangle$ with $γ\approx 0.16$.