On the Entropy of a Random Geometric Graph

Abstract

In this paper, we study the entropy of a hard random geometric graph (RGG), a commonly used model for spatial networks, where the connectivity is governed by the distances between the nodes. Formally, given a connection range $r$, a hard RGG $G_m$ on $m$ vertices is formed by drawing $m$ random points from a spatial domain, and then connecting any two points with an edge when they are within a distance $r$ from each other. The two domains we consider are the $d$-dimensional unit cube $[0,1{]}^d$ and the $d$-dimensional unit torus ${\mathbb{T}}^d$. We derive upper bounds on the entropy $H(G_m)$ for both these domains and for all possible values of $r$. In a few cases, we obtain an exact asymptotic characterization of the entropy by proving a tight lower bound. Our main results are that $H(G_m)\sim dm{\log }_{2}m$ for $0<r\le 1/4$ in the case of ${\mathbb{T}}^d$ and that the entropy of a one-dimensional RGG on $[0,1]$ behaves like $m\log m$ for all $0<r<1$. As a consequence, we can infer that the asymptotic structural entropy of an RGG on ${\mathbb{T}}^d$, which is the entropy of an unlabelled RGG, is $\hat{I}\text{c◯}((d-1)m{\log }_{2}m)$ for $0<r\le 1/4$. For the rest of the cases, we conjecture that the entropy behaves asymptotically as the leading order terms of our derived upper bounds.

13 pages, 2 figures