Directed random geometric graphs: structural and spectral properties

Abstract

In this work we analyze structural and spectral properties of a model of directed random geometric graphs: given n vertices uniformly and independently distributed on the unit square, a directed edge is set between two vertices if their distance is smaller than the connection radius $\ell$ , which is randomly drawn from a Pareto distribution. This Pareto distribution is characterized by the power-law decay α and the lower bound of its support $\ell_0$ ; thus the graphs depend on three parameters $G(n,\alpha,\ell_0)$ . By increasing $\ell_0$ , for fixed $(n,\alpha)$ , the model transits from isolated vertices ( $\ell_0\approx 0$ ) to complete graphs ( $\ell_0 = \sqrt{2}$ ). We first propose a phenomenological expression for the average degree $\langle k(G) \rangle$ which works well for α > 3, when k is a self-averaging quantity. Then we numerically demonstrate that $\langle V_x(G) \rangle \approx n[1-\exp(-\langle k\rangle]$ , for all α , where $V_x(G)$ is the number of nonisolated vertices of G . Finally, we explore the spectral properties of $G(n,\alpha,\ell_0)$ by the use of adjacency matrices represented by diluted random matrix ensembles; a non-Hermitian and a Hermitian one. We find that $\langle k \rangle$ is a good scaling parameter of spectral and eigenvector properties of G mainly for large α .

Keywords

• directed graph
• random geometric graph
• random matrix theory