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

Abstract

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,\theta )$, obeying the probability density functions $\rho (l)$ and $\rho (\theta )$. Here we choose $\rho (l)$ as a normal distribution with zero mean and variance $\sigma \in (0,\infty )$ and $\rho (\theta )$ as an uniform distribution in the interval $\theta \in [0,2\pi )$. 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,\sigma ,\ell )$, by the use of the average degree $⟨k⟩$ 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 $⟨k(n,\sigma ,\ell )⟩$. Then, we look for the scaling properties of the normalized average measure $⟨\overline{X}⟩$ (where $X$ stands for $V_{\times }$, $r$ and $S$) over graph ensembles. We demonstrate that the scaling parameter of $⟨\overline{V_{\times }}⟩=⟨V_{\times }⟩/n$ is indeed $⟨k⟩$; with $⟨\overline{V_{\times }}⟩\approx 1-\exp (-⟨k⟩)$. Meanwhile, the scaling parameter of both $⟨\overline{r}⟩$ and $⟨\overline{S}⟩$ is proportional to $n^{-\gamma }⟨k⟩$ with $\gamma \approx 0.16$.

15 pages, 14 figures

References in corpus (8)

• The distribution of the ratio of consecutive level spacings in random matrix ensembles
• Proximity Networks and Epidemics
• Worm Epidemics in Wireless Adhoc Networks
• Universality in the spectral and eigenfunction properties of random networks
• Random Rectangular Graphs
• Spacing ratio characterization of the spectra of directed random networks
• Topological versus spectral properties of random geometric graphs
• Normal mode analysis of spectra of random networks