Structural Complexity of One-Dimensional Random Geometric Graphs

We study the richness of the ensemble of graphical structures (i.e., unlabeled graphs) of the one-dimensional random geometric graph model defined by
$n$
nodes randomly scattered in [0, 1] that connect if they are within the connection range
$r\in [{0,1}]$
. We provide bounds on the number of possible structures which give universal upper bounds on the structural entropy that hold for any
$n$
,
$r$
and distribution of the node locations. For fixed
$r$
, the number of structures is
$\Theta (a^{2n})$
with
$a=a(r)=2 \cos {\left ({\frac {\pi }{\lceil 1/r \rceil +2}}\right)}$
, and therefore the structural entropy is upper bounded by
$2n\log _{2} a(r) + O(1)$
. For large
$n$
, we derive bounds on the structural entropy normalized by
$n$
, and evaluate them for independent and uniformly distributed node locations. When the connection range
$r_{n}$
is
$O(1/n)$
, the obtained upper bound is given in terms of a function that increases with
$n r_{n}$
and asymptotically attains 2 bits per node. If the connection range is bounded away from zero and one, the upper and lower bounds decrease linearly with
$r$
, as
$2(1-r)$
and
$(1-r)\log _{2} e$
, respectively. When
$r_{n}$
is vanishing but dominates
$1/n$
(e.g.,
$r_{n} \propto \ln n / n$
), the normalized entropy is between
$\log _{2} e \approx 1.44$
and 2 bits per node. We also give a simple encoding scheme for random structures that requires 2 bits per node. The upper bounds in this paper easily extend to the entropy of the labeled random graph model, since this is given by the structural entropy plus a term that accounts for all the permutations of node labels that are possible for a given structure, which is no larger than
$\log _{2}(n!) = n \log _{2} n {-} n + O(\log _{2} n)$
.