Entropy and Distributed Source Coding of Connected Soft Random Geometric Graphs
Oliver Baker and Carl P. Dettmann · 2026
Read Entropy and Distributed Source Coding of Connected Soft Random Geometric Graphs by Oliver Baker and Carl P. Dettmann (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-04703.txt.
Introduction
Oliver Baker and Carl P. Dettmann work out how to compress a random geometric graph in a distributed way, where several encoders each hold part of the graph and code their parts separately. Their graphs place points randomly in space and connect nearby pairs with a probability that softens the usual hard distance cutoff.
Restricting attention to graphs above the connectivity threshold, where the network is essentially one connected piece, they establish the exact Slepian-Wolf rate region for this distributed compression. The proof needs new limit theorems and equipartition properties for the entropy of these soft random geometric graphs, after which standard random binning techniques deliver the coding result.
Catalog record
| CREATOR | Oliver Baker and Carl P. Dettmann |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 27 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.04703
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Entropy and Distributed Source Coding of Connected Soft Random Geometric Graphs Oliver Baker and Carl P. Dettmann Abstract We consider the distributed compression of Soft Random Geometric Graphs (SRGGs) above the connectivity threshold. We establish the Slepian-Wolf rate region for the SRGG in the setting where there are a finite number of encoders compressing sections of the graph independently. To do so, we prove novel limit theorems and asymptotic equipartition properties for the SRGG and its entropy, which allow us to use random binning techniques for distributed compression. I Introduction In the modern world, devices are more connected than ever. This results in networks becoming larger, increasing the need for research on compression of networks. In particular, in areas of application such as wireless networking, random models of large networks with a spatial embedding have gained popularity [ 8 ] . One popular model for wireless networks is the Soft Random Geometric Graph (SRGG). In this model, nodes are connected at random according to a function of their spatial distance [ 12 ] . Despite their numerous applications, the information theory of these random graphs is not well understood. In recent years there have been a growing number of works that have concentrated on this model or similar ones such as graphons. In [ 10 ] a limit theorem for the entropy of W random graphs (which include SRGGs as a special case) was proven. Since then, there have been a number of works attempting to bound or quantify the entropy, such as [ 5 , 2 , 4 ] . Also, the compression of random graphs has gained popularity recently. Models such as sparse Erdős-Rényi graphs [ 3 ] , stochastic block models [ 1 , 14 ] and preferential attachment graphs [ 15 ] have all been considered. Compression of the SRGG (or generalisations) has been studied in [ 6 , 11 , 13 ] . Crucially, all of these works focus on compression in the centralised setting. That is, we have an encoder that sees the entire graph, and compresses it for a decoder to later decompress. However, in many applications, it is perhaps more realistic to assume that nodes, or blocks of nodes only have access to partial information about the network. In [ 7 ] , the distributed compression of Erdős-Rényi and configuration model graphs is studied, but distributed compression of the SRGG is, to the best of our knowledge, unstudied. In this work, we consider the regime where we have a fixed, but arbitrary number of encoders which have access to different sections of the graph. Our other source of novelty is the specific regime in which we study the SRGG. In the above works, when the SRGG (or W random graph) is made sparse (by which we mean that the expected degree of a node is sublinear in the total number of nodes), it is done by randomly removing a fraction of the edges of a dense ensemble. However, this places less emphasis on the geometry, since the length scale of edges does not scale with the number of nodes. In our work, we study the more commonly considered regime, for example in the work of Penrose [ 12 ] , where the ‘connection range’ of each node is decreasing in the number of nodes. Equivalently, the size of the domain in which we embed the graph is growing as we add more nodes. We make this idea more precise later. To the best of our knowledge, this regime has not yet been studied in an information-theoretic context. We also note that the SRGG is an example of a non-standard source , in that it cannot be written as a string of stationary, ergodic or Markovian symbols. We must therefore employ the ideas of information spectrum theory to study its information theoretic properties. In this work, we contribute the following. 1. A limit theorem for the entropy rate of the SRGG, 2. an Asymptotic Equipartition Property (AEP) for the SRGG, 3. a complete characterisation of the Slepian-Wolf region for the distributed compression of the SRGG. In Section II we formally introduce the model, the information spectrum, and the distributed compression setting. Section III presents our main results, and Section IV contains proof ideas. The full proofs may be found in the supplemental material. Finally, Section V concludes. II Model and Problem Formulation II-A Soft Random Geometric Graphs Definition 1 (Soft Random Geometric Graph) . Let Z_{1},...,Z_{n} be independent, uniformly distributed points in a compact set \mathcal{K}\subset\mathbb{R}^{d} with unit volume, a non-empty interior, whose boundary is piecewise smooth, of finite length and has a finite number of corners. The Soft Random Geometric Graph (SRGG) G_{n}=(V_{n},E_{n}) is the graph with vertex set V_{n}=[n]:=\{1,2,...,n\} , and edge set formed by connecting each pair of vertices i,j\in V_{n} independently with probability p_{n}(R_{ij}) , where R_{ij}:=\|Z_{i}-Z_{j}\| is the Euclidean distance between nodes i and j , and p_{n}:[0,\infty)\to[0,1] is the ‘connection function’. Let \mathcal{G}_{n} be the set of all SRGGs on n nodes, then \mathcal{G}_{n} is called the ensemble of SRGGs. In this work, we will consider specifically the following form of connection function. Let \{s(n)\}_{n=1}^{\infty} be a positive, decreasing sequence of real numbers. We call s(n) the sparsity of the SRGG. Then, we focus on connection functions p_{n}(r)=p(r/s(n)) , where p:[0,\infty)\to[0,1] . One can think of this form of connection function in two equivalent ways. First, we can imagine fixing the domain \mathcal{K} , and decreasing the ‘connection range’ of each node, that is, the length scale at which two nodes are likely to be connected is decreasing with n . Alternatively, we can imagine instead fixing the connection range, and increasing the size of \mathcal{K} with n . We note that this is a different regime to the other commonly considered SRGG, where p_{n}(r)=s(n)p(r) . We will require that 1\gg s(n)\gg\left(\frac{\log n}{n}\right)^{1/d} . This requirement has two interpretations. The first is that this is the regime where the SRGG is connected with high probability as n\rightarrow\infty [ 12 ] . The second is that the entropy of the labelled graph is asymptotically equivalent to the entropy of the unlabelled graph. Definition 2 (Entropy of the SRGG) . The Shannon Entropy of the SRGG is denoted by H(\mathcal{G}_{n}) , and is given by H(\mathcal{G}_{n}):=-\sum_{G\in\mathcal{G}_{n}}\mathbb{P}\left(G_{n}\right)\log\mathbb{P}\left(G_{n}\right) (1) where the logarithm is to base 2, and we take the convention that 0\log 0=0 . Also, if Z_{n} is the random vector containing the locations of each node, then the conditional entropy H(\mathcal{G}_{n}|\mathcal{Z}_{n})=\mathbb{E}[H(\mathcal{G}_{n}|Z_{n})] is given by H(\mathcal{G}_{n}|\mathcal{Z}_{n})=\binom{n}{2}\int_{0}^{\infty}f_{\mathcal{K}}(r)h_{2}(p_{n}(r))dr (2) where f_{\mathcal{K}} is the probability density of pairwise distances in \mathcal{K} , and h_{2}(p)=-p\log p-(1-p)\log(1-p) is the binary entropy function. We treat the following as a standing assumption for the remainder of the paper. Assumption 1 . The connection function p_{n} is given by p_{n}(r)=p(r/s(n)) , where p is a Hölder continuous function, that is, for every (x,y),(x^{\prime},y^{\prime})\in\mathcal{K}^{2} , |p(x,y)-p(x^{\prime},y^{\prime})|\leq L\|(x,y)-(x^{\prime},y^{\prime})\|^{\alpha} (3) with L,\alpha>0 as constants. We assume that, if d is the dimension of the space \mathcal{K}\subset\mathbb{R}^{d} , \int_{0}^{\infty}r^{2d}h_{2}(p(r))dr<\infty (4) and \int_{0}^{\infty}r^{d-1}p(r)(1-p(r))\log^{2}\left(\frac{p(r)}{1-p(r)}\right)dr<\infty (5) We also define the following integral h^{*}:=\kappa_{d-1}\int_{0}^{\infty}r^{d-1}h_{2}(p(r))dr<\infty (6) where \kappa_{d-1} is the volume of the unit d-1 ball. II-B The Information Spectrum As briefly mentioned in the introduction, the