| Resumo: | 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 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 Θ(a2n) with a=a(r)=2cos(π⌈1/r⌉+2) , and therefore the structural entropy is upper bounded by 2nlog2a(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 rn is O(1/n) , the obtained upper bound is given in terms of a function that increases with nrn 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)log2e , respectively. When rn is vanishing but dominates 1/n (e.g., rn∝lnn/n ), the normalized entropy is between log2e≈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 log2(n!)=nlog2n−n+O(log2n).
|
|---|