Abstract

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∈[0,1]. We characterize the number of possible structures and obtain a universal upper bound on the structural entropy of 2n−(3/2) log n−(1/2) log π, which holds for any n, r and distribution of the node locations. For large n, we derive bounds on the structural entropy normalized by n, for independent and uniformly distributed node locations. When the connection range r is O(1/n), the obtained upper bound is given in terms of a function that increases with n*r and asymptotically attains 2 bits per node. If the connection range is bounded away from zero and one, the upper bound decreases with r as 2(1−r). When r is vanishing but dominates 1/n (e.g., r ~ (ln n)/n), the normalized entropy is between log e ≈ 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(n!) ~ n log n.