Topological versus spectral properties of random geometric graphs

In this work we perform a detailed statistical analysis of topological and spectral properties of random geometric graphs (RGGs), a graph model used to study the structure and dynamics of complex systems embedded in a two-dimensional space. RGGs, $G(n,\ell )$, consist of $n$ vertices uniformly and independently distributed on the unit square, where two vertices are connected by an edge if their Euclidian distance is less than or equal to the connection radius $\ell \in [0,\sqrt{2}]$. To evaluate the topological properties of RGGs we chose two well-known topological indices, the Randić index $R\left(G\right)$ and the harmonic index $H\left(G\right)$. We characterize the spectral and eigenvector properties of the corresponding randomly weighted adjacency matrices by the use of random matrix theory measures: the ratio between consecutive eigenvalue spacings, the inverse participation ratios, and the information or Shannon entropies $S\left(G\right)$. First, we review the scaling properties of the averaged measures, topological and spectral, on RGGs. Then we show that (i) the averaged-scaled indices, $〈R\left(G\right)〉$ and $〈H\left(G\right)〉$, are highly correlated with the average number of nonisolated vertices $〈V_{\times }\left(G\right)〉$; and (ii) surprisingly, the averaged-scaled Shannon entropy $〈S\left(G\right)〉$ is also highly correlated with $〈V_{\times }\left(G\right)〉$. Therefore, we suggest that very reliable predictions of eigenvector properties of RGGs could be made by computing topological indices.

Figure 1

(a) Average number of nonisolated vertices $〈V_{\times }\left(G\right)〉$, (d) average Randić index $〈R\left(G\right)〉$, and (g) average harmonic index $〈H\left(G\right)〉$ as a function of the connection radius $\ell$ of random geometric graphs of four different sizes $n$. Normalized average indices $〈V_{\times }\left(G\right)〉/n, 〈R\left(G\right)〉/(n/2)$, and $〈H\left(G\right)〉/(n/2)$ as a function of $\ell$ [(b), (e), and (h)] and $\xi$ [(c), (f), and (i)]. Orange lines in (a) correspond to Eq. (7). The horizontal dashed line in (b), (e), and (h) marks $〈\overline{X}\left(G\right)〉=0.5$. The insets in (b), (e), and (h) show ${\ell }^{*}$ vs $n$; the black lines represent the best fittings of the data with Eq. (8), with fitting parameters reported in Table 1. The orange dashed line in the inset of (b) is Eq. (9). The insets in (c), (f), and (i) show the same curves of the main panels but in semilog scale. The orange line, shown for comparison purposes in the main panels (c), (f), and (i) and the insets, is the curve $V_{\times }\left(G\right)/n$ vs $\xi$ of Eq. (11).

Figure 2

Scatter plots of the log of the normalized indices reported in Fig. 1. Data corresponding to $n=1000$ is shown. The red-dashed lines, shown as a reference, are the identity function. The Pearson correlation coefficients $\rho$ are reported in the corresponding panels.

Figure 3

(a) Average ratio between consecutive eigenvalue spacings $〈r\left(G\right)〉$, (d) average inverse participation ratio $〈\mathrm{IPR}\left(\mathrm{G}\right)〉$, and (g) average Shannon entropy $〈S\left(G\right)〉$ as a function of the connection radius $\ell$ of random geometric graphs of four different sizes $n$. Normalized average measures $〈\overline{r}\left(G\right)〉, 〈\overline{\mathrm{IPR}}\left(G\right)〉$, and $〈S\left(G\right)〉/S_{\mathrm{GOE}}$ as a function of $\ell$ [(b), (e), and (h)] and $\xi$ [(c), (f), and (i)]. The insets in (b), (e), and (h) show ${\ell }^{*}$ vs $n$; the black lines represent the best fittings of the data with Eq. (8), with fitting parameters reported in Table 1. The horizontal dashed line in (b), (e), and (h) marks $〈\overline{X}\left(G\right)〉=0.5$. The insets in (c), (f), and (i) show the same curves of the main panels but in semilog scale. The orange line, shown for comparison purposes in the main panels (c), (f), and (i) and the insets, is the curve $V_{\times }\left(G\right)/n$ vs $\xi$ of Eq. (11).

Figure 4

Scatter plots of the log of the normalized spectral measures reported in Fig. 3 versus the log of the normalized average number of nonisolated vertices $〈V_{\times }\left(G\right)〉/n$. Data corresponding to $n=1000$ is shown. The red-dashed lines, shown as a reference, are the identity function. The Pearson correlation coefficients $\rho$ are reported in the corresponding panels.