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 $rin [{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 $2nlog _{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)$ .