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)$.
翻译:我们研究图象结构( 即, 未经标记的图解) 的全方位共度的丰富性。 对于固定的 $, 结构的数量是 $_theta (a) 美元, 由 $n 的节点随机分散在 $[0, 1美元], 如果在连接范围内, 则连接到 $r\ in $[0, 1美元。 因此, 我们提供在任何美元、 $ 和节点分布上具有普遍上限的可能结构数量的界限。 对于大 美元, 我们从 美元 的 结构昆虫上绑到 $(a) 美元, 以 美元为 美元, 以 美元= 2 美元 的直线性图形模型为美元 。 当连接范围为 $_ 美元 美元, 则以 美元 美元 的直线性 。