Structural Complexity of One-Dimensional Random Geometric Graphs

DOI10.1109/TIT.2022.3207819MaRDI QIDQ6193558zbMATH OpenOpenAlexFDO

Authors Mihai-Alin Badiu, Justin P. Coon

Publication date 18 March 2024

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2107.13495

zbMATH Keywords

entropygraph compressiongraph isomorphismgraphical structuremaximal cliquesrandom geometric graph

Mathematics Subject Classification ID

Information and communication theory, circuits (94-XX)

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 $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)=2cosleft(fracpilceil1/rceil+2ight)$, and therefore the structural entropy is upper bounded by $2nlo{g}_{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)lo{g}_{2}e$, respectively. When $r_n$ is vanishing but dominates $1/n$ (e.g., $r_{n}proptolnn/n$), the normalized entropy is between $lo{g}_{2}eapprox1.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 $lo{g}_2(n!)=nlo{g}_{2}n-n+O(lo{g}_{2}n)$.

Cited in

(2)

• Connecting probability for random bounded-range one-dimensional network
• An uniformity index for random geometric graphs

This page was built for publication: Structural Complexity of One-Dimensional Random Geometric Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6193558)