Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2601.10778 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908769395408896 |
|---|---|
| author | Vippathalla, Praneeth Kumar Coon, Justin P. Badiu, Mihai-Alin |
| author_facet | Vippathalla, Praneeth Kumar Coon, Justin P. Badiu, Mihai-Alin |
| contents | In this paper, we study the entropy of a hard random geometric graph (RGG), a commonly used model for spatial networks, where the connectivity is governed by the distances between the nodes. Formally, given a connection range $r$, a hard RGG $G_m$ on $m$ vertices is formed by drawing $m$ random points from a spatial domain, and then connecting any two points with an edge when they are within a distance $r$ from each other. The two domains we consider are the $d$-dimensional unit cube $[0,1]^d$ and the $d$-dimensional unit torus $\mathbb{T}^d$. We derive upper bounds on the entropy $H(G_m)$ for both these domains and for all possible values of $r$. In a few cases, we obtain an exact asymptotic characterization of the entropy by proving a tight lower bound. Our main results are that $H(G_m) \sim dm \log_2m$ for $0 < r \leq 1/4$ in the case of $\mathbb{T}^d$ and that the entropy of a one-dimensional RGG on $[0,1]$ behaves like $m\log m$ for all $0<r<1$. As a consequence, we can infer that the asymptotic structural entropy of an RGG on $\mathbb{T}^d$, which is the entropy of an unlabelled RGG, is $Ω((d-1)m \log_2m)$ for $0 < r \leq 1/4$. For the rest of the cases, we conjecture that the entropy behaves asymptotically as the leading order terms of our derived upper bounds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_10778 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the Entropy of a Random Geometric Graph Vippathalla, Praneeth Kumar Coon, Justin P. Badiu, Mihai-Alin Information Theory In this paper, we study the entropy of a hard random geometric graph (RGG), a commonly used model for spatial networks, where the connectivity is governed by the distances between the nodes. Formally, given a connection range $r$, a hard RGG $G_m$ on $m$ vertices is formed by drawing $m$ random points from a spatial domain, and then connecting any two points with an edge when they are within a distance $r$ from each other. The two domains we consider are the $d$-dimensional unit cube $[0,1]^d$ and the $d$-dimensional unit torus $\mathbb{T}^d$. We derive upper bounds on the entropy $H(G_m)$ for both these domains and for all possible values of $r$. In a few cases, we obtain an exact asymptotic characterization of the entropy by proving a tight lower bound. Our main results are that $H(G_m) \sim dm \log_2m$ for $0 < r \leq 1/4$ in the case of $\mathbb{T}^d$ and that the entropy of a one-dimensional RGG on $[0,1]$ behaves like $m\log m$ for all $0<r<1$. As a consequence, we can infer that the asymptotic structural entropy of an RGG on $\mathbb{T}^d$, which is the entropy of an unlabelled RGG, is $Ω((d-1)m \log_2m)$ for $0 < r \leq 1/4$. For the rest of the cases, we conjecture that the entropy behaves asymptotically as the leading order terms of our derived upper bounds. |
| title | On the Entropy of a Random Geometric Graph |
| topic | Information Theory |
| url | https://arxiv.org/abs/2601.10778 |