On the entropy of a random geometric graph

Conference item

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 Gm 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 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) ∼ dm log₂ m for 0 < r ≤ 1/4 in the case of 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 T d , which is the entropy of an unlabelled RGG, is Ω((d−1)m log₂ m) for 0 < r ≤ 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.

Authors: Vippathalla, PK; Coon, JP; Badiu, M-A

• Publication status: Accepted
• Peer review status: Peer reviewed
• Publisher: IEEE
• Acceptance date: 2026-03-28
• Event title: IEEE International Symposium in Information Theory (ISIT 2026)
• Event location: Guangzhou, China
• Event website: https://2026.ieee-isit.org/
• Event start date: 2026-06-28
• Event end date: 2026-07-03
• Language: English