# Structural Complexity of One-Dimensional Random Geometric Graphs

Mihai-Alin Badiu and Justin P. Coon The authors are with the Department of
Engineering Science, University of Oxford, Parks Road, Oxford, OX1 3PJ, UK,
(email<EMAIL_ADDRESS>justin.coon@eng.ox.ac.uk).This material is
based upon work supported by, or in part by, the U. S. Army Research
Laboratory and the U. S. Army Research Office under contract/grant number
W911NF-19-1-0048, and the EPSRC grant number EP/T02612X/1.

###### 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 $r\in[0,1]$. We characterize the number of possible
structures and obtain a universal upper bound on the structural entropy of
$2n-\frac{3}{2}\log_{2}n-\frac{1}{2}\log_{2}\pi$, which holds for any $n$, $r$
and distribution of the node locations. For large $n$, we derive bounds on the
structural entropy normalized by $n$, 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
$nr_{n}$ and asymptotically attains $2$ bits per node. If the connection range
is bounded away from zero and one, the upper bound decreases with $r$ as
$2(1-r)$. When $r_{n}$ is vanishing but dominates $1/n$ (e.g.,
$r_{n}\propto\ln n/n$), the normalized entropy is between $\log_{2}e\approx
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 $\log_{2}(n!)\sim n\log_{2}n$.

###### Index Terms:

Random geometric graph, entropy, graphical structure, graph isomorphism,
maximal cliques, graph compression

##  I Introduction

Graphs are important mathematical structures used in network science for
representing and analysing systems composed of multiple entities (represented
by the nodes of the graph) that are related or interact in some sense
(indicated through edges that connect some pairs of nodes). There are a
multitude of applications in various disciplines, including biological systems
(e.g., protein-protein interactions, neuronal networks), information networks
(computer networks, wireless sensor networks), social networks, economic
networks, etc.

Several random graph models whose typical instances are representative of
real-world networks exist in the literature [1, 2]. The Erdős-Rényi model
where edges between $n$ nodes are drawn independently with probability $p$ is
an emblematic basic model that is convenient for theoretical analysis,
although it does not exhibit important properties of real networks, such as
transitivity, clustering, or inhomogeneity.

As many real networks are increasingly large, the storage or transmission of
graphs and data on graphs becomes problematic. It thus becomes important to
quantify the amount of information embodied in networks and develop efficient
methods of representing graphs and data associated with them compactly by
exploiting any potential statistical redundancy. From an information
theoretical perspective, the limit to compression of random graphs is the
entropy of the graph distribution, according to Shannon’s source coding
theorem. The case of the Erdős-Rényi model is simple, as the random graph can
be treated as a collection of ${n\choose 2}$ independent binary sources, such
that the entropy is ${n\choose 2}h(p)$ with
$h(p)=-p\log_{2}p-(1-p)\log_{2}(1-p)$. More realistic random graphs, however,
exhibit intricate dependencies which makes exact computation complicated.

A relevant question is how much of the complexity of a graph is structural,
i.e., pertaining to the unlabeled graph, and how much of it is data complexity
related to the labels carried by the nodes for given structure (equivalently,
how informative the random structure is about the labels of the graph).
Furthermore, there are cases in which it is not necessary to distinguish
between the nodes, i.e., their identities are irrelevant. For example, many of
the graph properties (e.g., node degrees, connectedness, $k$-connectivity,
etc.) depend on the structures in the ensemble, and not on the labels of the
nodes. In such cases, one may be interested in storing or transmitting only
the structural information relevant for reconstructing the unlabelled graph
(i.e., up to graph isomorphisms). That is, the focus is on the graph
structures and the problem is of compressing graphs with node labels removed.

Compression of unlabeled graphs was addressed by Turán [3] more than three
decades ago, who showed that unlabeled planar graphs can be represented
(optimally within a constant factor) using $12n$ bits and gave an
asymptotically optimal encoding of labeled planar graphs that requires
$n\left\lceil{\log_{2}n}\right\rceil+12n$ bits. Turán also suggested a lower
bound on the number of bits in the representation of general unlabeled graphs
of ${n\choose 2}-n\log_{2}n+O(n)$ and raised the problem of finding an
efficient (i.e., computable in polynomial time) coding method. This problem
was solved a few years later by Naor [4], who proposed a linear-time encoding
method that is optimal up to the $O(n)$ term. More recently, Choi &
Szpankowski [5, 6] addressed compression of unlabeled graphs (which they name
_graphical structures_) for the Erdős-Rényi model and showed that the
corresponding Shannon entropy (coined _structural entropy_) is ${n\choose
2}h(p)-n\log_{2}n+O(n)$. Note the $n\log_{2}n$ reduction of the entropy
compared to the entropy of labeled Erdős-Rényi graphs. A similar study of
entropy as a measure of structural complexity is performed in [7] for random
binary trees. Motivated by the fact that real networks are inhomogeneous and
exhibit cluster structures, properties that are not captured by the Erdős-
Rényi model, [8] studies fundamental limits on the compression of the
stochastic block model with labeled vertices. Compression of unlabeled
preferential attachment graphs is addressed in [9].

Since many real-world networks are spatial [10], random geometric graphs
(RGGs, where pairs of nodes are connected based on the distance between them
in some latent space) are often used as models of practical applications [11].
For example, starting with the paper by Gupta and Kumar [12], the properties
and performance of wireless networks are commonly analyzed by modelling them
as RGGs. The entropy as a measure of complexity of wireless network topologies
and, more generally, spatial graphs was studied in [13, 14, 15]. For example,
in a topology discovery application, the entropy of a wireless network
ensemble would give a measure of the minimum amount of information that has to
be collected from the network such that reconstruction of the topology of the
network is possible. Simple bounds on the entropy of labelled spatial graphs
were obtained in [13, 14, 15] based on the subadditivity property of joint
entropy; the bounds scale as $n^{2}$, as in the case of the Erdős-Rényi graph
model. However, RGGs have salient features (e.g., strong transitivity) induced
by the spatial embedding of the nodes and distance-based connectivity that
have not been fully exploited in the aforementioned bounds. This motivates us
to investigate in this paper the structural complexity of RGGs more closely.
In particular, we consider the one-dimensional (1D) RGG model, which has been
studied extensively from the connectivity point of view (e.g., see [16] and
the references therein), often as a model of 1D wireless networks (e.g.,
vehicular networks, sensors deployed along a river, military convoys, train
backbone network, etc. [17, 18]).

In this paper, we study how rich the ensemble of structures (i.e., unlabeled
graphs) of the 1D RGG model is, how its complexity (quantified by the
structural entropy) scales with the number of nodes and how the connection
range impacts the structural entropy. In Sec. II, we define the considered 1D
RGG model, which has $n$ nodes randomly located on $[0,1]$ and connection
range $r$. We also discuss its connectivity and introduce the notions of
graphical structures and structural entropy.

In Sec. III, we make a connection between the structure of the 1D RGG and a
particular graph, which we call the _ordered graph_ , whose nodes are indexed
according to the order of their underlying locations. We show that, up to
left-right reversal, the ordered graphs identify the connected graphical
structures produced by the 1D RGG model, and the total number of possible
structures in the model is upper bounded by the number of ordered graphs. This
enables us to characterize in Sec. IV the structural complexity of the 1D RGG
model by estimating the number of possible ordered graphs. Based on their
representation in terms of maximal cliques, we find that the number of ordered
graphs and consequently the number of structures with $n$ nodes is upper
limited by the $n$th Catalan number, whereas the number of connected
structures is bounded by the $(n-1)$th Catalan number. Based on this count, in
Sec. V we immediately obtain an upper limit on the structural entropy whose
dominant term is $2n$ (Theorem 1). This result holds for any distribution of
the nodes and connection range $r$, and therefore cannot be universally
accurate. For example, when $r$ approaches zero (one) the graph is empty
(complete) with high probability, such that the entropy would approach zero.

We subsequently establish bounds on the structural entropy in terms of the
entropy of the ordered graph. We evaluate the bounds for independent and
uniformly distributed point locations (which is typically assumed for the 1D
RGG), for different scaling regimes of the connection range $r$, as $n$ grows
large (Theorem 2). In particular, in the asymptotically connected regime,
which is of practical interest and relevance, we find that the normalized
structural entropy is somewhere between $\log_{2}e\approx 1.44$ and $2$ bits
per node, for large $n$. We also give a simple encoding scheme for 1D random
geometric graphical structures that requires $2n$ bits, i.e., it achieves the
obtained upper limit in the asymptotically connected regime.

The upper bounds in this paper easily extend to the entropy of the _labeled_
1D RGG, since this is no larger than 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 $\log_{2}(n!)\sim n\log_{2}n$.

##  II Preliminaries

###  II-A Graph Model

The one-dimensional random geometric graph $G_{n,r}$ is constructed by placing
$n$ points randomly on a line segment and connecting by an edge every pair of
nodes that are separated by a distance smaller than a threshold $r$. More
formally, assume the $n$ points have the random locations $X_{1},\ldots,X_{n}$
in the interval $[0,1]$. For now, we refrain from defining the (joint)
distribution of $X_{1},\ldots,X_{n}$, since some results shown below are
universal. However, we will consider the specific case where
$X_{1},\ldots,X_{n}$ are i.u.d. in Theorem 2. The corresponding graph
$G_{n,r}=(V,E)$ has the set of vertices $V=\\{1,\ldots,n\\}$ and the set of
undirected edges $E=\\{(i,j)\in V^{2}\mid|X_{i}-X_{j}|\leq r,\,i<j\\}$, for a
fixed connection range $r>0$.

The graph $G_{n,r}$ depends deterministically on the node locations. However,
it does not retain the locations but only the connectivity among the nodes.
Also, an infinite number of configurations of locations may be mapped to the
same graph. We denote by $\mathcal{G}_{n,r}$ the set of all possible graphs
that are produced by this model, i.e., the support of $G_{n,r}$. Fig. 1
illustrates two such graphs. The probability distribution of
$(X_{1},\ldots,X_{n})$ induces a distribution of graphs in
$\mathcal{G}_{n,r}$, such that a graph $G\in\mathcal{G}_{n,r}$ occurs with
probability $P(G)$.

$0$$1$$\bullet$$x_{2}$$\bullet$$x_{3}$$\bullet$$x_{1}$$\bullet$$x_{5}$$\bullet$$x_{4}$

$1$$2$$3$$4$$5$

(a)

$0$$1$$\bullet$$x_{3}$$\bullet$$x_{5}$$\bullet$$x_{2}$$\bullet$$x_{4}$$\bullet$$x_{1}$

$1$$2$$3$$4$$5$

(b)

Figure 1: Two outcomes of $G_{n,r}$ for $n=5$ and $r=1/3$; the points are
i.u.d. on $[0,1]$ (left); the resulting graph (right).

###  II-B Connectivity

A graph is said to be connected if there exists at least one path between
every pair of distinct vertices. The connectivity of one-dimensional random
geometric graphs has been studied extensively, e.g., see [19] and the
references therein. Trivially, $G_{n,r}$ is connected for $r\geq 1$, as
$G_{n,r}$ is deterministically a complete graph in that case. For $r\in(0,1)$
and finite $n$, the graph is connected with a probability smaller than one in
general (e.g., when the random locations have a non-vanishing density on
$[0,1]$); for $X_{1},\ldots,X_{n}$ independent and uniformly distributed, the
probability is available in a closed form expression [20, 21].

Most of the works consider the connectivity of $G_{n,r}$ for large $n$ and
study how the connection range $r$ should scale with $n$ to achieve
connectivity, i.e., what scaling functions $r:\mathbb{N}\to\mathbb{R}_{+}$,
$n\to r_{n}$, are appropriate. For i.u.d. point locations, the connectivity
exhibits a typical behaviour in the sense that there exists a critical range
function $r^{\ast}_{n}=\frac{\ln n}{n}$ such that, as $n$ becomes large, the
graph is connected (or disconnected) with high probability depending on how
the scaling $r$ that is being used deviates from the critical scaling
$r^{\ast}$. Specifically, for a connection range function in the form
$r_{n}=r_{n}^{\ast}+\frac{\alpha_{n}}{n}$ for some
$\alpha:\mathbb{N}\to\mathbb{R}$, it holds that[19]

$\lim_{n\to\infty}\mathsf{Pr}(G_{n,r}\text{ is
connected})=\begin{cases}0,&\text{if }\lim_{n\to\infty}\alpha_{n}=-\infty,\\\
1,&\text{if }\lim_{n\to\infty}\alpha_{n}=\infty.\end{cases}$ (1)

For example, a deviation function $\alpha_{n}=\pm\ln\ln n$ determines
$G_{n,r}$ to be connected or disconnected with probability one depending on
the sign, in the limit of large $n$. More generally, it is shown in [16] that
graph connectivity also obeys a strong zero-one law when the distribution of
the point locations has a non-vanishing density.

###  II-C Graphical Structures

The graphical structures produced by the model of Sec. II-A can be defined
formally based on the notion of graph isomorphism.

######  Definition 1 (Structure)

Two graphs $G_{1}=(V,E_{1})\in\mathcal{G}_{n,r}$ and
$G_{2}=(V,E_{2})\in\mathcal{G}_{n,r}$ have the same structure, which is
denoted as $G_{1}\simeq G_{2}$, if and only if there exists a graph
isomorphism between them, i.e., if and only if there exists an adjacency-
preserving permutation of the vertices $\pi:V\to V$ such that $(i,j)\in
E_{1}\iff(\pi(i),\pi(j))\in E_{2}$, for all $i,j\in V$.

For example, one can verify that the two graphs in Fig. 1 have the same
structure, because the permutation $\pi(1)=2$, $\pi(2)=3$, $\pi(3)=5$,
$\pi(4)=1$ and $\pi(5)=4$ (applied to the vertices in Fig. 1a) is edge
preserving.

The relation ‘$\simeq$’ is an equivalence relation, which partitions the set
$\mathcal{G}_{n,r}$ into disjoint equivalence classes. All graphs in an
equivalence class have the same structure, while graphs in different classes
are structurally different. Thus, one can identify a structure by its defining
equivalence class or by a representative member of that class. In the
following, we denote by $\mathcal{S}_{n,r}$ the set of all structures of
$\mathcal{G}_{n,r}$.

###  II-D Structural Entropy

The probability distribution of $G_{n,r}$ with pmf $P(G)$,
$G\in\mathcal{G}_{n,r}$, induces a probability distribution over the set of
structures $\mathcal{S}_{n,r}$. Let $f:\mathcal{G}_{n,r}\to\mathcal{S}_{n,r}$
be a deterministic surjection that maps each graph in $\mathcal{G}_{n,r}$ to
its corresponding structure in $\mathcal{S}_{n,r}$. Accordingly, the preimage
$f^{-1}(S)$ of a structure $S\in\mathcal{S}_{n,r}$ is the set of all graphs in
$\mathcal{G}_{n,r}$ that belong to the equivalent class represented by $S$.
Based on the distribution of graphs, the probability of a structure
$S\in\mathcal{S}_{n,r}$ can thus be expressed as

$P(S)=\sum_{G\in f^{-1}(S)}P(G).$ (2)

The entropy of $G_{n,r}$ is

$H(G_{n,r})=-\sum_{G\in\mathcal{G}_{n,r}}P(G)\log_{2}P(G)$ (3)

whereas the structural entropy is defined by [6]

$H(S_{n,r})=-\sum_{S\in\mathcal{S}_{n,r}}P(S)\log_{2}P(S)$ (4)

##  III Structures of $\mathcal{G}_{n,r}$

###  III-A Graph Ordering

A one-dimensional random geometric graph is naturally visualised by depicting
its nodes in the order of their locations. For example, by doing so, we
realize that the graphs in Fig. 1a and 1b have the same structure, which is
illustrated in Fig. 2. In the following such a representation of structure is
formally justified. For connected structures, we show that each equivalence
class can be represented by a particular graph whose nodes are indexed
according to the order of the underlying point locations. This special graph,
which we call ‘ordered graph’, is then designated as the structure
representative. Disconnected structures can be treated as a collection of
smaller, connected structures.

Figure 2: The common structure of the graphs depicted in Fig. 1. The nodes are
displayed in the order of the point locations and their labels are discarded.

######  Definition 2 (Ordered graph)

Let $X_{1},\ldots,X_{n}\in[0,1]$ be the random locations of $n$ points and let
$X_{(1)},\ldots,X_{(n)}$ be the order statistics of the $n$ locations, i.e.,
$X_{(k)}$ is the $k$th smallest of the $X_{1},\ldots,X_{n}$. The random graph
$G_{n,r}$ is constructed as in Sec. II-A. We define the ordered graph
$\hat{G}_{n,r}$ as the graph with nodes $V=\\{1,\ldots,n\\}$ and edges
$\hat{E}=\\{(i,j)\in V\times V\mid|X_{(i)}-X_{(j)}|\leq r,i<j\\}$.

In the following, $\hat{\mathcal{G}}_{n,r}$ denotes the support of the random
ordered graph $\hat{G}_{n,r}$.

###### Lemma 1

The graphs $G_{n,r}$ and $\hat{G}_{n,r}$ are isomorphic.

###### Proof:

Let $\sigma:\\{1,\ldots,n\\}\to\\{1,\ldots,n\\}$ be the bijection that
reindexes the points in ascending order of their location, such that
$X_{\sigma^{-1}(1)}\leq X_{\sigma^{-1}(2)}\leq\ldots\leq X_{\sigma^{-1}(n)}$,
i.e., $X_{\sigma^{-1}(i)}\equiv X_{(i)}$ is the $i$th order statistic of the
random locations. From the definitions of $G_{n,r}$ and $\hat{G}_{n,r}$, it
can be verified that $\sigma$ is an edge-preserving permutation and therefore
an isomorphism. ∎

###  III-B Maximal Cliques

In the following, an ordered geometric graph is represented in terms of its
constituent maximal cliques. A clique of a graph is a subset of the vertices
of the graph, such that any two vertices are adjacent, i.e., the subgraph
induced by the clique is complete. A clique is maximal if it is not a subset
of a larger clique, i.e., no adjacent vertex can be included to extend the
clique. The number of maximal cliques of a graph with $n$ vertices can take
any value between one and $n$, the extremes corresponding to the complete
graph and respectively the empty graph (in which case each maximal clique
consists of one isolated node).

Ordered graphs have the following basic property.

###### Lemma 2

If nodes $i$ and $j$, $i<j$, of $\hat{G}_{n,r}$ are connected by an edge, then
the set of vertices $\\{i,i+1,\ldots,j\\}$ is a clique.

###### Proof:

Given that $(i,j)$ is an edge, $|X_{(j)}-X_{(i)}|\leq r$. Furthermore, for the
order statistic $(X_{(1)},\ldots,X_{(n)})$, it holds that
$|X_{(l)}-X_{(k)}|\leq|X_{(j)}-X_{(i)}|\leq r$, for all
$k,l\in\\{i,i+1,\ldots,j\\}$. It follows that $(k,l)$ is an edge, for every
$k,l\in\\{i,i+1,\ldots,j\\}$, and therefore $\\{i,i+1,\ldots,j\\}$ is a
clique. ∎

Thus, a maximal clique of $\hat{G}_{n,r}$ can be identified by its end-nodes
only (i.e., those with lowest and highest indices), so that we denote a
maximal clique $\\{a,a+1,\ldots,b\\}$, $a\leq b$, by $[a:b]$. In this way, any
ordered graph having $k$ maximal cliques ($1\leq k\leq n$) can be represented
by the set $\\{[a_{1}:b_{1}],\ldots,[a_{k}:b_{k}]\\}$, where the indices of
the end-nodes of the maximal cliques need to satisfy

$\begin{split}&1=a_{1}<a_{2}<\ldots<a_{k}\leq n,\\\ &1\leq
b_{1}<b_{2}<\ldots<b_{k}=n,\\\ &a_{i+1}\leq
b_{i}+1,\;i=1,\ldots,k-1.\end{split}$ (5)

The above conditions ensure that the maximal cliques cannot include one
another, although they may be overlapping, and each vertex belongs to at least
one maximal clique. When $a_{i+1}\leq b_{i}$, the $i$th and $(i+1)$th maximal
cliques are overlapping, whereas when $a_{i+1}=b_{i}+1$ there is a break in
the ordered graph between vertices $b_{i}$ and $b_{i}+1$. Also, it is possible
that $a_{i}=b_{i}$ for some $i$, which occurs when node $a_{i}$ is isolated
and thus constitutes, itself, the $i$th maximal clique. The example in Fig. 3
illustrates the decomposition of an ordered graph into its constituent maximal
cliques.

$0$$1$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$
(a)

$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$ (b)

$1$$2$$3$$4$$2$$3$$4$$5$$4$$5$$6$$5$$6$$7$$8$$9$$10$ (c)

Figure 3: Illustration of the decomposition of an ordered graph into maximal
cliques: (a) the locations of $n=10$ points (b) the ordered graph determined
by the set of locations and connection range $r=0.2$; (c) the ordered graph
consists of five maximal cliques: $[1:4]$, $[2:5]$, $[4:6]$, $[5:7]$, and
$[8:10]$; each maximal clique is a complete subgraph.

###  III-C Ordered Graphs and Structures

###### Lemma 3

Any isomorphism $\pi$ between two connected ordered graphs in
$\hat{\mathcal{G}}_{n,r}$ is either the identity $\pi(i)=i$, for all $i\in V$,
or the “backward identity” $\pi(i)=n-i+1$, for all $i\in V$.

###### Proof:

Let $G$ and $G^{\prime}$ be two outcomes of $\hat{G}_{n,r}$ that are connected
and isomorphic. We consider their maximal-clique representations
$G\equiv\\{[a_{1}:b_{1}],\ldots,[a_{k}:b_{k}]\\}$ and
$G^{\prime}\equiv\\{[a^{\prime}_{1}:b^{\prime}_{1}],\ldots,[a^{\prime}_{k^{\prime}}:b^{\prime}_{k^{\prime}}]\\}$,
where the end-nodes satisfy the conditions (5) with the stronger restriction
that the strict inequalities $a_{i+1}<b_{i}+1$ and
$a^{\prime}_{j+1}<b^{\prime}_{j}+1$ must hold, because the graphs are
connected and therefore consecutive maximal cliques must overlap. Note that
the isomorphism $\pi$ maps each maximal clique of $G$ onto a unique maximal
clique of $G^{\prime}$. Therefore, the two graphs have the same number of
maximal cliques, i.e., $k^{\prime}=k$. Moreover, since consecutive maximal
cliques are overlapping, any two successive maximal cliques of $G$ are mapped
by $\pi$ onto two consecutive maximal cliques of $G^{\prime}$. In particular,
noting that the first (i.e., leftmost) maximal clique $[1:b_{1}]$ of $G$ does
not have a preceding maximal clique, it follows that $[1:b_{1}]$ is mapped
onto either $[1:b_{1}^{\prime}]$, in which case $b_{1}^{\prime}=b_{1}$ and
$\pi(i)=i$, $i=1,\ldots,b_{1}$, or $[a_{k}^{\prime},n]$, in which case
$a_{k}^{\prime}=n-b_{1}+1$ and $\pi(i)=n-i+1$, $i=1,\ldots,b_{1}$. Then, by
considering all the maximal cliques in succession, it results that $\pi$ can
only be the identity or the backward identity. ∎

###### Proposition 1

The connected graphs in $\mathcal{G}_{n,r}$ that have the same structure have
corresponding ordered graphs that are identical up to left-right reversal.

###### Proof:

The result follows from Lemma 1 and Lemma 3, together with the fact that
composition of isomorphisms is an isomorphism. ∎

Similarly to the surjection $f$ introduced earlier, which maps each graph of
$\mathcal{G}_{n,r}$ to its corresponding structure in $\mathcal{S}_{n,r}$, we
now define the surjective map
$\hat{f}:\hat{\mathcal{G}}_{n,r}\to\mathcal{S}_{n,r}$, which associates each
ordered graph with its structure.

Proposition 1 enables us to study connected ordered graphs of
$\hat{\mathcal{G}}_{n,r}$ as representatives of the connected structures in
$\mathcal{S}_{n,r}$, with the understanding that an ordered graph and its
image under left-right reversal represent the same structure. Accordingly, for
each $S\in\mathcal{S}_{n,r}$ that is connected, it holds that either
$|\hat{f}^{-1}(S)|=1$, when the ordered graph in $\hat{f}^{-1}(S)$ is left-
right symmetrical, or $|\hat{f}^{-1}(S)|=2$, otherwise.

Disconnected structures can be treated similarly. In this case, permutations
of connected components of an ordered graph should also be considered
identical, in addition to left-right reversal. Thus, in general, the number of
ordered graphs that have a common structure $S$ with $N_{S}$ connected
components satisfies

$1\leq|\hat{f}^{-1}(S)|\leq 2^{N_{S}}N_{S}!$ (6)

##  IV Counting Structures

In this section, we assess the number of distinct structures of the graphs in
$\mathcal{G}_{n,r}$, i.e., the cardinality of $\mathcal{S}_{n,r}$, for any
number of nodes $n$, connection range $r>0$, and probability distribution of
the node locations. Specifically, we exploit the connection between structure
and ordered graphs made in the previous section to find an upper bound on
$|\mathcal{S}_{n,r}|$.

###  IV-A Total Number of Structures

Based on the surjection $f$ defined in Sec. II, the number of structures can
be expressed as

$|\mathcal{S}_{n,r}|=\sum_{G\in\mathcal{G}_{n,r}}\frac{1}{|f^{-1}(f(G))|},$
(7)

where the denominator gives the size of the equivalence class the graph
$G\in\mathcal{G}_{n,r}$ belongs to. We will however consider the following
alternative expression based on the ordered graphs

$|\mathcal{S}_{n,r}|=\sum_{G\in\hat{\mathcal{G}}_{n,r}}\frac{1}{|\hat{f}^{-1}(\hat{f}(G))|}\leq|\hat{\mathcal{G}}_{n,r}|,$
(8)

because we are able to find an upper limit for the number of ordered graphs.
Moreover, the set $\hat{\mathcal{G}}_{n,r}$ is smaller than
$\mathcal{G}_{n,r}$. By doing so, we obtain the following upper bound on the
number of structures.

###### Proposition 2

For any number of nodes $n$, spatial distribution of the nodes, and connection
range $r>0$, the number of structures in $\mathcal{S}_{n,r}$ is upper bounded
by the $n$th Catalan number, i.e.,

$|\mathcal{S}_{n,r}|\leq c_{n}=\frac{1}{n+1}{2n\choose
n}<\frac{4^{n}}{n^{3/2}\sqrt{\pi}}.$ (9)

###### Proof:

In Appendix A, we show that $|\hat{\mathcal{G}}_{n,r}|$ is upper bounded by
the $n$th Catalan number. The first inequality holds because
$|\mathcal{S}_{n,r}|\leq|\hat{\mathcal{G}}_{n,r}|$, as given in (8). The final
strict inequality follows from the upper bound on the central binomial
coefficient ${2n\choose n}<\frac{4^{n}}{\sqrt{\pi n}}$ (for a proof, see,
e.g., [22]). ∎

It is well known that the Catalan number $c_{n}$ and
$\frac{4^{n}}{n^{3/2}\sqrt{\pi}}$ are asymptotically equivalent, which means
that the last inequality in (9) is tight for large $n$.

###  IV-B Number of Connected Structures

Considering now only connected graphs, let
$\hat{\mathcal{G}}_{n,r}^{\text{c}}$ and $\mathcal{S}_{n,r}^{\text{c}}$ be the
subsets that include all the connected graphs/structures of
$\hat{\mathcal{G}}_{n,r}$ and $\mathcal{S}_{n,r}$, respectively. In the
asymptotically connected regime (i.e., for an appropriate connection range $r$
such that $G_{n,r}$ is connected with probability one as $n$ grows large, as
defined in Sec. II-B),
$\hat{\mathcal{G}}_{n,r}^{\text{c}}=\hat{\mathcal{G}}_{n,r}$ and
$\mathcal{S}_{n,r}^{\text{c}}=\mathcal{S}_{n,r}$ with probability one (the
sets $\hat{\mathcal{G}}_{n,r}$ and $\mathcal{S}_{n,r}$ include only connected
graphs and structures).

The following bounds on the number of connected structures follow from the
fact that $\hat{f}^{-1}(S)$ has at most two elements for connected $S$:

$\frac{1}{2}|\hat{\mathcal{G}}_{n,r}^{\text{c}}|\leq|\mathcal{S}_{n,r}^{\text{c}}|\leq|\hat{\mathcal{G}}_{n,r}^{\text{c}}|.$
(10)

By finding an upper limit for $|\hat{\mathcal{G}}_{n,r}^{\text{c}}|$, we
obtain the following upper bound for $|\mathcal{S}_{n,r}^{\text{c}}|$.

###### Proposition 3

For any number of nodes $n$, spatial distribution of the nodes, and connection
range $r>0$, the number of connected structures in $\mathcal{S}_{n,r}$ is
upper bounded by

$|\mathcal{S}_{n,r}^{\text{c}}|\leq c_{n-1}=\frac{1}{n}{2n-2\choose n-1}.$
(11)

###### Proof:

In Appendix B, we show that $|\hat{\mathcal{G}}_{n,r}^{\text{c}}|\leq
c_{n-1}$. The result follows from (10). ∎

##  V Bounds on the Structural Entropy

In the previous section, we characterized the structural complexity of the
considered random geometric graph model by studying the number of possible
structures in $\mathcal{S}_{n,r}$. That is, all the different structures were
equally accounted for without taking into account the connection range or the
distribution of the node locations. Given that the entropy of any distribution
is upper bounded by the cardinality of the support, we have
$H(\mathcal{S}_{n,r})\leq\log_{2}|\mathcal{S}_{n,r}|$, such that Proposition 2
immediately gives the following upper limit for the structural entropy.

###### Theorem 1

For any number of points $n$, spatial distribution of the points, and
connection range $r>0$, the structural entropy is upper bounded by

$H(S_{n,r})\leq 2n-\frac{3}{2}\log_{2}n-\frac{1}{2}\log_{2}\pi.$ (12)

The connection range and the distribution of the node locations dictate how
prevalent the different structures are in the ensemble of graphs. This is not
captured by Theorem 1. For example, the structural entropy approaches zero as
$r\to 0$ or $r\to 1$, such that we would expect that, as $r$ increases from
zero, the entropy first increases, reaches a maximum, and then decreases
towards zero. However, the upper bound given by Theorem 1 is constant with
respect to $r$. In this section, we focus on the structural entropy
$H(S_{n,r})$ given by (4) and thus explicitly consider the connection range
and the distribution of the locations.

###  V-A Relationship Between $H(S_{n,r})$ and $H(\hat{G}_{n,r})$

We further exploit the connection between the random structure $S_{n,r}$ and
the ordered graph $\hat{G}_{n,r}$ to obtain upper and lower bounds on
$H(S_{n,r})$.

###### Lemma 4

For any number of nodes $n$, distribution of the locations, and connection
range $r$,

$H(S_{n,r})\leq H(\hat{G}_{n,r}).$ (13)

###### Proof:

According to the map $\hat{f}$ introduced in Sec. III-C,

$H(S_{n,r})=H(\hat{f}(\hat{G}_{n,r}))\leq H(\hat{G}_{n,r}),$ (14)

where the inequality holds because the entropy of deterministic functions of a
random variable is no larger than the entropy of the variable [23]. ∎

When considering only the connected graphs, we find an upper bound and a lower
bound that determine the structural entropy within one bit.

###### Lemma 5

Let $S_{n,r}^{\text{c}}$ denote the random structure conditioned on it being
connected. The connected ordered graph $\hat{G}_{n,r}^{\text{c}}$ is similarly
defined. Then, for any number of nodes $n$, distribution of the locations, and
connection range $r$,

$H(\hat{G}_{n,r}^{\text{c}})-1\leq H(S_{n,r}^{\text{c}})\leq
H(\hat{G}_{n,r}^{\text{c}}).$ (15)

###### Proof:

As established earlier, the preimage $\hat{f}^{-1}(S)$ for connected
structures contains only one element when $S$ is left-right symmetrical, and
two elements, otherwise. Thus, for any $S\in\mathcal{S}_{n,r}^{\text{c}}$, (2)
gives

$P(S)=\begin{cases}P(\hat{G}),&\text{if }S\text{ is
symm.},S=\hat{f}(\hat{G}),\\\ P(\hat{G}_{1})+P(\hat{G}_{2}),&\text{if }S\text{
is asymm.},\\{\hat{G}_{1},\hat{G}_{2}\\}\equiv\hat{f}^{-1}(S).\end{cases}$
(16)

We now write

$\displaystyle H(\hat{G}_{n,r}^{\text{c}})$
$\displaystyle=-\sum_{\hat{G}\in\hat{\mathcal{G}}_{n,r}^{\text{c}}}P(\hat{G})\log_{2}P(\hat{G})$
$\displaystyle=-\sum_{S\in\mathcal{S}_{n,r}^{\text{c}}}\sum_{\hat{G}\in
f^{-1}(S)}P(\hat{G})\log_{2}P(\hat{G}).$ (17)

For any asymmetrical structure $S$, define
$q_{S}=\frac{1}{P(S)}\min(P(\hat{G}_{1}),P(\hat{G}_{2}))$, where
$\\{\hat{G}_{1},\hat{G}_{2}\\}\equiv\hat{f}^{-1}(S)$. From (16), $q_{S}<1$.
Using (16), we further express (V-A) as

$\displaystyle H(\hat{G}_{n,r}^{\text{c}})$
$\displaystyle=-\sum_{S\in\mathcal{S}_{n,r}^{\text{c}}}P(S)\log_{2}P(S)-\sum_{\begin{subarray}{c}S\in\mathcal{S}_{n,r}^{\text{c}}\\\
S\text{
asymm.}\end{subarray}}P(S)\left[q_{S}\log_{2}q_{S}+(1-q_{S})\log_{2}(1-q_{S})\right]$
$\displaystyle=H(S_{n,r}^{\text{c}})+\sum_{\begin{subarray}{c}S\in\mathcal{S}_{n,r}^{\text{c}}\\\
S\text{ asymm.}\end{subarray}}P(S)H_{\text{b}}(q_{S}),$ (18)

where $H_{\text{b}}(\cdot)$ is the binary entropy function. Given that
$H_{\text{b}}$ takes on values smaller than one and $P(S)$ is a probability
distribution, the sum term above is between zero and one, and the desired
result follows. ∎

Lemmas 4 and 5 give upper and lower bounds on the structural entropy in terms
of the entropy of the ordered graph, $H(\hat{G}_{n,r})$. In the following, we
find bounds on $H(\hat{G}_{n,r})$ and study them for i.u.d. point locations
and different scaling functions $r_{n}$, results which ultimately transfer to
bounds for the structural entropy.

###  V-B Bounds on $H(\hat{G}_{n,r})$

We represent $\hat{G}_{n,r}$ in terms of the number of leftward neighbours the
nodes have, as follows. Recall that the vertices of $\hat{G}_{n,r}$ are
indexed in increasing order from left to right, according to the order of
their locations. For all $i\in\\{2,\ldots,n\\}$, let $L_{i}$ be the number of
neighbours that node $i$ has to the left, which satisfies $0\leq L_{i}\leq
i-1$. It can be inspected (e.g., see Fig. 4) that $0\leq L_{i+1}\leq L_{i}+1$.

…$i-L_{i}$…$i+1-L_{i+1}$…$i$$i+1$… Figure 4: In this illustration, node
$i-L_{i}$ is the leftmost neighbour of node $i$, i.e., node $i$ is connected
by an edge to nodes $i-L_{i},i-L_{i}+1,\ldots,i-1$ but not to nodes
$1,\ldots,i-L_{i}-1$. Similarly, node $i+1$ has $L_{i+1}$ neighbours to the
left.

As there is a one-to-one relationship between $\hat{G}_{n,r}$ and
$(L_{2},\ldots,L_{n})$, and according to the chain rule for entropy, we have

$\displaystyle H(\hat{G}_{n,r})$ $\displaystyle=H(L_{2},\ldots,L_{n})$
$\displaystyle=H(L_{2})+\sum_{i=2}^{n-1}H(L_{i+1}\mid L_{2},\ldots,L_{i}),$
(19)

###### Lemma 6

The following upper bound holds for any number $n$ of points, spatial
distribution of the points, and connection range $r$:

$H(\hat{G}_{n,r})\leq H(L_{2})+\sum_{i=2}^{n-1}H(L_{i+1}\mid L_{i}).$ (20)

###### Proof:

Given that conditioning reduces the entropy, the result immediately follows
from (V-B). ∎

###### Lemma 7

When the point locations $X_{1},\ldots,X_{n}$ are independently sampled from a
continuous distribution, the following lower bound holds for any number $n$ of
points and connection range $r$:

$H(\hat{G}_{n,r})\geq H(L_{2})+\sum_{i=2}^{n-1}H\left(L_{i+1}\mid
L_{i},X_{(i-L_{i})},\ldots,X_{(i)}\right).$ (21)

###### Proof:

Since conditioning reduces the entropy, the terms of the sum in (V-B) are
lower bounded by

$\displaystyle H(L_{i+1}\mid L_{2},\ldots,L_{i})$ $\displaystyle\geq
H\left(L_{i+1}\mid L_{2},\ldots,L_{i},X_{(i-L_{i})},\ldots,X_{(i)}\right)$
(22) $\displaystyle=H\left(L_{i+1}\mid
L_{i},X_{(i-L_{i})},\ldots,X_{(i)}\right)$ (23)

The equality holds because, given $L_{i}$, node $i+1$ may be connected by an
edge only to nodes $i-L_{i},i-L_{i}+1,\ldots,i$ and thus $L_{i+1}$ is dictated
by the gap $X_{(i+1)}-X_{(i)}$ and the locations
$X_{(i-L_{i})},\ldots,X_{(i)}$. Then, given that the order statistics of
independent variables drawn from a continuous distribution have the Markov
property [24], the gap $X_{(i+1)}-X_{(i)}$ is conditionally independent of
$L_{2},\ldots,L_{i}$, given $X_{(i)}=x$; consequently, $L_{i+1}$ is
conditionally independent of $(L_{2},\ldots,L_{i-1})$, given the number of
leftward neighbors $L_{i}$ and the locations $X_{(i-L_{i})},\ldots,X_{(i)}$. ∎

Next, we evaluate the obtained bounds for i.u.d. point locations and different
scaling functions $r_{n}$.

###### Proposition 4

When the point locations $X_{1},\ldots,X_{n}$ are i.u.d. on $[0,1]$, the upper
bound on the normalized entropy of the ordered graph satisfies the asymptotic
equivalence

$\displaystyle\frac{1}{n}H(\hat{G}_{n,r_{n}})$
$\displaystyle\leq\frac{1}{n}H(L_{2})+\frac{1}{n}\sum_{i=2}^{n-1}H(L_{i+1}\mid
L_{i})$ $\displaystyle\sim\begin{cases}h_{\mathrm{U}}(nr_{n}),&\text{if
}r_{n}=O(1/n),\\\ 2,&\text{if }r_{n}=\omega(1/n)\text{ and }r_{n}=o(1),\\\
2(1-r),&\text{if }r_{n}=r\in(0,1),\end{cases}$ (24)

as $n\to\infty$, where the function
$h_{\mathrm{U}}:[0,\infty)\to\mathbb{R}_{+}$ is given by

$h_{\mathrm{U}}(x)=\frac{x\,e^{-x}}{\ln
2}-\sum_{a=0}^{\infty}\frac{x^{a}e^{-x}}{a!}\sum_{k=0}^{a}\frac{x}{a+1}M(k+1,a+2,-x)\log_{2}\left(\frac{x}{a+1}M(k+1,a+2,-x)\right)$
(25)

with $M$ being Kummer’s confluent hypergeometric function,

$M(\alpha,\beta,z)=\frac{\Gamma(\beta)}{\Gamma(\alpha)\,\Gamma(\beta-\alpha)}\int_{0}^{1}t^{\alpha-1}(1-t)^{\beta-\alpha-1}e^{zt}\mathrm{d}t.$

###### Proof:

See Appendix C. ∎

###### Proposition 5

When the point locations $X_{1},\ldots,X_{n}$ are i.u.d. on $[0,1]$, the lower
bound on the normalized entropy of the ordered graph satisfies the asymptotic
equivalence

$\displaystyle\frac{1}{n}H(\hat{G}_{n,r_{n}})$
$\displaystyle\geq\frac{1}{n}H(L_{2})+\frac{1}{n}\sum_{i=2}^{n-1}H\left(L_{i+1}\mid
L_{i},X_{(i-L_{i})},\ldots,X_{(i)}\right)$
$\displaystyle\sim\begin{cases}h_{\mathrm{L}}(nr_{n}),&\text{if
}r_{n}=O(1/n),\\\ 1/\ln 2,&\text{if }r_{n}=\omega(1/n)\text{ and
}r_{n}=o(1),\end{cases}$ (26)

as $n\to\infty$, where the function
$h_{\mathrm{L}}:[0,\infty)\to\mathbb{R}_{+}$ is given by

$h_{\mathrm{L}}(x)=\frac{1-e^{-x}}{\ln
2}-\left(1-e^{-x}\right)^{2}\log_{2}\left(1-e^{-x}\right).$ (27)

###### Proof:

See Appendix D. ∎

###  V-C Discussion

Fig. 5 illustrates the upper and lower bounds given by Propositions 4 and 5
when the connection range function is $r_{n}=\frac{x}{n}$, $x>0$, and $n$ is
large. We notice that the bounds approach the values of $2$ bits and
respectively $1/\ln 2\approx 1.443$ bits, as $x$ increases; these values
correspond to the asymptotic value (in $n$) of the normalised entropy of the
ordered graph when $r_{n}$ dominates $1/n$ but is still vanishing with $n$
(e.g., $r_{n}\propto\ln n/n$ or $r_{n}\propto 1/\sqrt{n}$). Finally, if the
scaling function is constant, $r_{n}=r$ with $r$ bounded away from $0$ and
$1$, the upper bound decreases linearly with $r$. The decrease is due to the
margin effect caused by the finite domain over which the points are
distributed: roughly speaking, for large $n$, approximately a fraction $r$ of
the nodes form the leftmost clique (i.e., they are all connected to node $1$),
such that only a fraction of about $1-r$ of the $L$ variables contribute to
the uncertainty.

Figure 5: Upper and lower bounds on the normalised entropy of the ordered
graph when $r_{n}=\frac{x}{n}$ and $n\to\infty$.

The results obtained in this section are summarized in terms of the structural
entropy in the following theorem.

###### Theorem 2

When the locations $X_{1},\ldots,X_{n}$ are i.u.d. over $[0,1]$, the
normalized structural entropy is upper bounded by (4), as $n\to\infty$.
Moreover, when the connection range function $r_{n}$ is vanishing but stays
above the critical scaling, such that the graph is connected with probability
one (i.e., $r_{n}$ is in the form required in (1)), the normalized structural
entropy is bounded by

$\log_{2}e<\frac{1}{n}H(S_{n,r})<2.$ (28)

###### Proof:

The first part follows from Lemma 4 and Proposition 4. For the asymptotically
connected regime (i.e., although vanishing, $r_{n}$ is such that the graph is
connected with probability one), Lemma 5 gives that the normalized structural
entropy is equal to the normalized entropy of the ordered graph as
$n\to\infty$. Then, the upper and lower limits follow from Propositions 4 and
5. ∎

Thus, in the asymptotically connected regime, it should be possible to encode
the random structures using no more than $2n$ bits. A simple encoding scheme
that is based on the maximal clique representation (see Sec. III-B) and
requires $2n$ bits is as follows. We use two binary strings $\mathbf{a}$ and
$\mathbf{b}$, each of length $n$. The ones give the indices of the end-nodes
of the maximal cliques. Specifically, the position of the $k$th one in
$\mathbf{a}$ ($\mathbf{b}$) gives the index of the leftmost (rightmost) node
of the $k$th maximal clique. For example, the graph in Fig. 3 is encoded as
$\mathbf{a}=1101100100$ and $\mathbf{b}=0001111001$.

##  VI Conclusions

In this paper, we examined the complexity of the ensemble of structures
(unlabeled graphs) of the one-dimensional random geometric graph model. We
introduced the ordered graph, which has the nodes labeled according to the
order of their underlying locations, and showed that the connected ordered
graphs of the model can be used as representatives of the connected
structures, up to left-right reversal. A disconnected structure can also be
represented by the ordered graph by additionally discounting the possible
permutations of the connected components. Based on the decomposition of the
ordered graph into its constituent maximal cliques, we found that the number
of ordered graphs and thus of possible structures in the 1D RGG model is upper
limited by the $n$th Catalan number. This result immediately gave an upper
bound on the structural entropy of
$2n-\frac{3}{2}\log_{2}n-\frac{1}{2}\log_{2}\pi$ which is universal, in the
sense that it holds for any distribution of the point locations and connection
range. By establishing relationships between the structural entropy and the
entropy of the ordered graph, we then investigated the influence of the
connection range on the structural entropy for i.u.d. points, in the limit of
large number of nodes. The obtained upper bound exhibits the expected
behaviour of the structural entropy, i.e., as $r$ increases from zero, the
structural entropy first increases starting from zero but then decreases when
$r$ is bounded away from zero, due to the finite embedding domain. In the
asymptotically connected regime, the structural entropy normalized by the
number of nodes is between $1.44$ and $2$ bits per node. We also proposed a
simple encoding scheme that reflects the decomposition into maximal cliques
and requires $2n$ bits.

The upper bounds we obtained in this paper translate to the entropy of the
labeled graph model by adding $\log_{2}(n!)\sim n\log_{2}n$; it would be
relevant to improve this term by considering the sizes of the automorphism
groups of the graphs. We are also interested in finding bounds or
approximations for the dependency of the structural entropy on the connection
range that include correction terms, which would refine the asymptotic results
obtained here. We intend to extend the analysis to RGGs in two (or higher)
dimensions. We think it is also relevant to study RGGs with soft connection
functions (i.e., where pair of nodes are connected by an edge with a
probability that decreases with the distance between them), as opposed to the
hard connection model assumed in this paper.

## References

  * [1] B. Bollobás, _Random Graphs_ , 2nd ed., ser. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2001.
  * [2] M. Newman, _Networks: An Introduction_. Oxford University Press, 2010.
  * [3] G. Turán, “On the succinct representation of graphs,” _Discrete Applied Mathematics_ , vol. 8, no. 3, pp. 289 – 294, 1984.
  * [4] M. Naor, “Succinct representation of general unlabeled graphs,” _Discrete Applied Mathematics_ , vol. 28, no. 3, pp. 303 – 307, 1990.
  * [5] Y. Choi and W. Szpankowski, “Compression of graphical structures,” in _2009 IEEE International Symposium on Information Theory_ , June 2009, pp. 364–368.
  * [6] ——, “Compression of graphical structures: Fundamental limits, algorithms, and experiments,” _IEEE Transactions on Information Theory_ , vol. 58, no. 2, pp. 620–638, Feb 2012.
  * [7] J. C. Kieffer, E.-H. Yang, and W. Szpankowski, “Structural complexity of random binary trees,” in _2009 IEEE International Symposium on Information Theory_ , June 2009, pp. 635–639.
  * [8] E. Abbe, “Graph compression: The effect of clusters,” in _2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , Sep. 2016, pp. 1–8.
  * [9] T. Łuczak, A. Magner, and W. Szpankowski, “Compression of preferential attachment graphs,” in _2019 IEEE International Symposium on Information Theory (ISIT)_ , July 2019, pp. 1697–1701.
  * [10] M. Barthélemy, “Spatial networks,” _Physics Reports_ , vol. 499, no. 1, pp. 1 – 101, 2011.
  * [11] M. Penrose, _Random Geometric Graphs_. Oxford University Press, 2003.
  * [12] P. Gupta and P. R. Kumar, “Critical power for asymptotic connectivity in wireless networks,” in _Stochastic analysis, control, optimization and applications_. Springer, 1999, pp. 547–566.
  * [13] J. P. Coon, “Topological uncertainty in wireless networks,” in _2016 IEEE Global Communications Conference (GLOBECOM)_ , Dec 2016, pp. 1–6.
  * [14] J. P. Coon, C. P. Dettmann, and O. Georgiou, “Entropy of spatial network ensembles,” _Phys. Rev. E_ , vol. 97, p. 042319, Apr 2018.
  * [15] M.-A. Badiu and J. P. Coon, “On the distribution of random geometric graphs,” in _2018 IEEE International Symposium on Information Theory (ISIT)_ , June 2018, pp. 2137–2141.
  * [16] G. Han and A. M. Makowski, “One-dimensional geometric random graphs with nonvanishing densities—part I: A strong zero-one law for connectivity,” _IEEE Transactions on Information Theory_ , vol. 55, no. 12, pp. 5832–5839, 2009.
  * [17] Y. Liu, J. Feng, O. Simeone, J. Tang, Z. Wen, A. M. Haimovich, and M. Zhou, “Topology discovery for linear wireless networks with application to train backbone inauguration,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 17, no. 8, pp. 2159–2170, Aug 2016.
  * [18] I. Jawhar, S. Zhang, J. Wu, N. Mohamed, and M. M. Masud, “Efficient topology discovery and routing in thick wireless linear sensor networks,” in _2017 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_ , May 2017, pp. 91–96.
  * [19] G. Han and A. M. Makowski, “A very strong zero-one law for connectivity in one-dimensional geometric random graphs,” _IEEE Communications Letters_ , vol. 11, no. 1, pp. 55–57, 2007.
  * [20] M. Desai and D. Manjunath, “On the connectivity in finite ad hoc networks,” _IEEE Communications Letters_ , vol. 6, no. 10, pp. 437–439, 2002\.
  * [21] A. Ghasemi and S. Nader-Esfahani, “Exact probability of connectivity in one-dimensional ad hoc wireless networks,” _IEEE Communications Letters_ , vol. 10, no. 4, pp. 251–253, 2006.
  * [22] N. D. E. (https://mathoverflow.net/users/14830/noam-d elkies), “Upper limit on the central binomial coefficient,” MathOverflow, uRL:https://mathoverflow.net/q/133752 (version: 2013-06-14). [Online]. Available: https://mathoverflow.net/q/133752
  * [23] T. M. Cover and J. A. Thomas, _Elements of Information Theory_ , 2nd ed. USA: Wiley-Interscience, 2006.
  * [24] H. A. David, _Order statistics_ , 2nd ed., ser. Wiley series in probability and mathematical statistics. New York ; London: Wiley, 1981.

##  Appendix A Number of Ordered Graphs

Let $\mathcal{C}_{n}$ be the set of graphs with vertices $\\{1,\ldots,n\\}$
that have the property that, if an edge exists between two vertices $i$ and
$j$, $i<j$, then the vertices $\\{i,i+1,\ldots,j\\}$ form a clique, for any
$i$ and $j$. According to Lemma 2,
$\hat{\mathcal{G}}_{n,r}\subseteq\mathcal{C}_{n}$ and therefore

$|\hat{\mathcal{G}}_{n,r}|\leq|\mathcal{C}_{n}|.$ (29)

In the rest of this subsection we determine a closed-form expression for
$|\mathcal{C}_{n}|$, which will be used in Proposition 2.

We define the set $\mathcal{C}_{n,k}$ to include the graphs of
$\mathcal{C}_{n}$ that have $k$ maximal cliques, $k=1,\ldots,n$. Thus,
$|\mathcal{C}_{n}|=\sum_{k=1}^{n}|\mathcal{C}_{n,k}|$. Every graph in
$\mathcal{C}_{n,k}$ can be represented as the set of $k$ maximal cliques
$\\{[a_{1}:b_{1}],\ldots,[a_{k}:b_{k}]\\}$, where the indices of the end-nodes
must satisfy the conditions given in (5). To compute $|\mathcal{C}_{n,k}|$, we
first determine the number $p(m,n,k)$ of graphs in $\mathcal{C}_{n,k}$ whose
$k$th (i.e., last) maximal clique is fixed to $[a_{k},b_{k}]=[m,n]$. When
$k=1$, all nodes must belong to the single clique, such that

$p(m,n,1)=\begin{cases}1,&m=1,\\\ 0,&m>1.\end{cases}$ (30)

For $k\geq 2$, $m$ must satisfy $k\leq m\leq n$. We obtain the following
result.

###### Lemma 8

The number of graphs in $\mathcal{C}_{n,k}$, $k\geq 2$, whose last maximal
clique is fixed to $[a_{k},b_{k}]=[m,n]$, $k\leq m\leq n$, is

$p(m,n,k)={n\choose k-1}{m-2\choose k-2}-{n-1\choose k-2}{m-1\choose k-1}$
(31)

###### Proof:

The proof is by induction over $k$. From the conditions (5) (and by inspecting
the decomposition example in Fig. 3), we establish the following recurrence
relation over the number of maximal cliques:

$p(m,n,k+1)=\sum_{u=k}^{m-1}\sum_{v=m-1}^{n-1}p(u,v,k).$ (32)

Using (30) in (32), we obtain

$p(m,n,2)=\sum_{u=1}^{m-1}\sum_{v=m-1}^{n-1}p(u,v,1)=\sum_{v=m-1}^{n-1}1=n-m+1.$
(33)

The same expression is obtained by substituting $k=2$ in (31). Thus, the
claimed result (31) is satisfied for $k=2$.

Now, assume (31) holds for some $k>2$. Eq. (32) becomes

$\displaystyle p(m,n,k+1)$ $\displaystyle=\sum_{u=k}^{m-1}{u-2\choose
k-2}\sum_{v=m-1}^{n-1}{v\choose k-1}$
$\displaystyle\phantom{=}-\sum_{u=k}^{m-1}{u-1\choose
k-1}\sum_{v=m-1}^{n-1}{v-1\choose k-2}.$ (34)

We next calculate the sums in (34). Using the identity for the rising sum of
binomial coefficients, we obtain

$\sum_{u=k}^{m-1}{u-2\choose k-2}=\sum_{i=0}^{m-k-1}{k-2+i\choose
k-2}={m-2\choose k-1}$ (35)

and, similarly,

$\sum_{u=k}^{m-1}{u-1\choose k-1}={m-1\choose k}.$ (36)

Then, we write

$\displaystyle\sum_{v=m-1}^{n-1}{v\choose k-1}$
$\displaystyle=\sum_{v=k-1}^{n-1}{v\choose k-1}-\sum_{v=k-1}^{m-2}{v\choose
k-1}$ (37) $\displaystyle={n\choose k}-{m-1\choose k}$ (38)

and similarly obtain

$\sum_{v=m-1}^{n-1}{v-1\choose k-2}={n-1\choose k-1}-{m-2\choose k-1}.$ (39)

Finally, plugging these results back in (34), we obtain

$p(m,n,k+1)={n\choose k}{m-2\choose k-1}-{n-1\choose k-1}{m-1\choose k}.$ (40)

This establishes the inductive step, and thus the proof is complete. ∎

###### Lemma 9

The number of graphs in $\mathcal{C}_{n,k}$, $1\leq k\leq n$, is

$|\mathcal{C}_{n,k}|=\frac{1}{n}{n\choose k}{n\choose k-1}.$ (41)

###### Proof:

For $k=1$, the set $\mathcal{C}_{n,1}$ contains only the complete graph, such
that $|\mathcal{C}_{n,1}|=1$. For $k\geq 2$, the $k$th maximal clique can
start anywhere between $k$ and $n$, i.e., $k\leq a_{k}\leq n$. Therefore, we
have

$\displaystyle|\mathcal{C}_{n,k}|$ $\displaystyle=\sum_{m=k}^{n}p(m,n,k)$
$\displaystyle={n\choose k-1}\sum_{m=k}^{n}{m-2\choose k-2}-{n-1\choose
k-2}\sum_{m=k}^{n}{m-1\choose k-1}$ $\displaystyle={n\choose k-1}{n-1\choose
k-1}-{n-1\choose k-2}{n\choose k}$ $\displaystyle=\frac{1}{n}{n\choose
k}{n\choose k-1}.$

∎

###### Lemma 10

The number of graphs in $\mathcal{C}_{n}$ is given by the $n$th Catalan
number,

$|\mathcal{C}_{n}|=c_{n}=\frac{1}{n+1}{2n\choose n}.$ (42)

###### Proof:

We have

$\displaystyle|\mathcal{C}_{n}|$
$\displaystyle=\sum_{k=1}^{n}|\mathcal{C}_{n,k}|$ (43)
$\displaystyle=\frac{1}{n}\sum_{k=1}^{n}{n\choose k}{n\choose k-1}$ (44)
$\displaystyle=\frac{1}{n}\sum_{k=1}^{n}{n\choose k}{n\choose n+1-k}$ (45)
$\displaystyle=\frac{1}{n}{2n\choose n+1}$ (46)
$\displaystyle=\frac{1}{n+1}{2n\choose n},$ (47)

where we have used Vandermonde’s identity. ∎

##  Appendix B Number of Connected Ordered Graphs

Starting from the set of graphs $\mathcal{C}_{n}$ defined in Appendix A, let
$\mathcal{C}_{n}^{\text{c}}$ be the subset consisting of all the connected
graphs of $\mathcal{C}_{n}$ and let $\mathcal{C}_{n,k}^{\text{c}}$ include all
the graphs of $\mathcal{C}_{n}^{\text{c}}$ that have $k$ maximal cliques,
$1\leq k\leq n-1$.111Connected $n$-node graphs cannot have $n$ maximal
cliques, because that would correspond to an empty graph. An example of a
graph with $k=n-1$ maximal cliques is one where each maximal clique consists
of two nodes and every two successive maximal cliques have one node in common.

Similarly to before, Lemma 2 gives

$|\hat{\mathcal{G}}_{n,r}^{\text{c}}|\leq|\mathcal{C}_{n}^{\text{c}}|=\sum_{k=1}^{n-1}|\mathcal{C}_{n,k}^{\text{c}}|.$
(48)

In the maximal-clique representation of each graph in
$\mathcal{C}_{n,k}^{\text{c}}$, $\\{[a_{1}:b_{1}],\ldots,[a_{k}:b_{k}]\\}$,
the indices $a$ and $b$ must satisfy the conditions given in (5) with the
stronger requirement that $a_{i+1}\leq b_{i}$, for all $i=1,\ldots,k-1$,
because consecutive maximal cliques must be overlapping. We define the number
$q(m,n,k)$ of graphs in $\mathcal{C}_{n,k}^{\text{c}}$ whose $k$th maximal
clique is fixed to $[a_{k},b_{k}]=[m,n]$. When $k=1$, $q(1,n,1)=1$ and
$q(m,n,1)=0$, for $m>1$. For $k\geq 2$, $m$ must satisfy $k\leq m\leq n-1$.
The following result is the counterpart of Lemma 8.

###### Lemma 11

The number of graphs in $\mathcal{C}_{n,k}^{\text{c}}$, $k\geq 2$, with
$[a_{k},b_{k}]=[m,n]$, $k\leq m\leq n-1$, is

$q(m,n,k)={n-1\choose k-1}{m-2\choose k-2}-{n-2\choose k-2}{m-1\choose k-1}$
(49)

###### Proof:

The following recursion is found to hold (similarly to the recursion for $p$
in the proof of Lemma 8):

$q(m,n,k+1)=\sum_{u=k}^{m-1}\sum_{v=m}^{n-1}q(u,v,k).$ (50)

The proof is then by induction over $k$ and involves similar steps as for
Lemma 8, which we omit. ∎

###### Lemma 12

The number of graphs in $\mathcal{C}_{n,k}^{\text{c}}$, $1\leq k\leq n-1$, is

$|\mathcal{C}_{n,k}^{\text{c}}|=\frac{1}{n-1}{n-1\choose k}{n-1\choose k-1}.$
(51)

###### Proof:

We omit the proof, as it is similar to that of Lemma 9. ∎

###### Lemma 13

The number of graphs in $\mathcal{C}_{n}^{\text{c}}$ is given by the $(n-1)$th
Catalan number,

$|\mathcal{C}_{n}^{\text{c}}|=c_{n-1}=\frac{1}{n}{2n-2\choose n-1}.$ (52)

###### Proof:

The proof is similar to that of Lemma 10. ∎

##  Appendix C Proof of Proposition 4

To evaluate the upper bound (20), we need the joint distribution of the
numbers of leftward neighbors nodes $i$ and $i+1$ have in the ordered graph.

###  C-A Joint Distribution of $L_{i}$ and $L_{i+1}$

For all $i\in\\{2,\ldots,n-1\\}$, we study $\mathsf{Pr}(L_{i}=a,L_{i+1}=b)$,
$0\leq a\leq i-1$ and $0\leq b\leq a+1$. In the case where node $i$ is not
connected by an edge to node $1$, i.e., $a<i-1$, we find that the joint
probabilities do not depend on $i$.

When $0\leq a\leq i-2$ and $1\leq b\leq a+1$, for nodes $i$ and $i+1$ to have
$a$ and respectively $b$ leftward neighbours, they must be spatially located
as follows: $i-a-1$ points in $[0,X_{(i)}-r)$; $a-b+1$ points in
$[X_{(i)}-r,X_{(i+1)}-r)$; $b-1$ points in $[X_{(i+1)}-r,X_{(i)})$; $0$ points
in $(X_{(i)},X_{(i+1)})$; and, finally, $n-i-1$ points in $(X_{(i+1)},1]$.
When the $n$ points are independent and uniformly distributed on $[0,1]$, we
obtain the joint probability by integrating the multinomial distribution over
the feasible values of the locations $x$ and $y$ of nodes $i$ and $i+1$,
respectively. That is,

$\mathsf{Pr}(L_{i}=a,L_{i+1}=b)=\iint\limits_{\mathcal{D}}\frac{n!\,(x-r)^{i-a-1}(y-x)^{a-b+1}(r+x-y)^{b-1}(1-y)^{n-i-1}}{(i-a-1)!\,(a-b+1)!\,(b-1)!\,(n-i-1)!}\mathrm{d}x\,\mathrm{d}y,$
(53)

where the integration domain is $\mathcal{D}=\\{(x,y)\in(0,1)^{2}\mid
x>r,y>x,y<x+r,y<1\\}$. Assuming $r<1/2$, we make the change of variable
$y-x=u$, such that $0<u<r$ and $r<x<1-u$, and obtain

$\displaystyle\mathsf{Pr}(L_{i}=a,L_{i+1}=b)$
$\displaystyle=\int_{0}^{r}\frac{n!\,u^{a-b+1}(r-u)^{b-1}}{(a-b+1)!\,(b-1)!}\int_{r}^{1-u}\frac{(x-r)^{i-a-1}(1-u-x)^{n-i-1}}{(i-a-1)!\,(n-i-1)!}\mathrm{d}x\,\mathrm{d}u$
$\displaystyle=\int_{0}^{r}\frac{n!\,u^{a-b+1}(r-u)^{b-1}(1-r-u)^{n-a-1}}{(a-b+1)!\,(b-1)!\,(n-a-1)!}\mathrm{d}u$
$\displaystyle=\int_{0}^{1}\frac{n!\,r^{a+1}\,t^{a-b+1}(1-t)^{b-1}(1-r-rt)^{n-a-1}}{(a-b+1)!\,(b-1)!\,(n-a-1)!}\mathrm{d}t,$
(54)

for all $0\leq a\leq i-2$ and $1\leq b\leq a+1$, and $r<1/2$.

When $0\leq a\leq i-2$ and $b=0$, the following must hold, assuming $r<1/2$:
$X_{(i+1)}-X_{(i)}>r$; $i-a-1$ points in $[0,X_{(i)}-r)$; $a$ points in
$[X_{(i)}-r,X_{(i)})$; $0$ points in $(X_{(i)},X_{(i+1)})$; and, finally,
$n-i-1$ points in $(X_{(i+1)},1]$. Thus, we write

$\displaystyle\mathsf{Pr}(L_{i}=a,L_{i+1}=0)$
$\displaystyle=\int_{r}^{1-r}\int_{x+r}^{1}\frac{n!\,(x-r)^{i-a-1}r^{a}(1-y)^{n-i-1}}{(i-a-1)!\,a!\,(n-i-1)!}\,\mathrm{d}x\,\mathrm{d}y$
$\displaystyle={n\choose a}r^{a}(1-2r)^{n-a}.$ (55)

Using (C-A) and (C-A), we find that

$\displaystyle\mathsf{Pr}(L_{i}=a)$
$\displaystyle=\sum_{b=0}^{a+1}\mathsf{Pr}(L_{i}=a,L_{i+1}=b)$
$\displaystyle={n\choose a}r^{a}(1-r)^{n-a},$ (56)

for all $a=0,\ldots,i-2$.

For $a=i-1$ (i.e., in the ordered graph, node $i$ is connected by an edge to
node $1$), we therefore have

$\displaystyle\mathsf{Pr}(L_{i}=i-1)$
$\displaystyle=1-\sum_{a=0}^{i-2}\mathsf{Pr}(L_{i}=a)$
$\displaystyle=\sum_{a=i-1}^{n}{n\choose a}r^{a}(1-r)^{n-a}$ (57)

Thus, $L_{i}$ has a truncated binomial distribution, as a consequence of the
left margin.

###  C-B The Normalized Entropy for Large $n$

We consider the entropy per node, $\frac{1}{n}H(\hat{G}_{n,r})$. From (20), we
write

$\frac{1}{n}H(\hat{G}_{n,r})\leq\underbrace{\frac{1}{n}\sum_{i=2}^{n-1}\sum_{a=0}^{i-2}\mathsf{Pr}(L_{i}=a)H(L_{i+1}\mid
L_{i}=a)}_{\equiv
h_{n}}+\underbrace{\frac{1}{n}\sum_{i=2}^{n-1}\mathsf{Pr}(L_{i}=i-1)H(L_{i+1}\mid
L_{i}=i-1)}_{\equiv c_{n}}+\frac{1}{n}H(L_{2}).$ (58)

The inner sum in the term in (58) denoted by $h_{n}$ is taken over $a<i-1$.
Consequently, the probabilities involved in $h_{n}$ (given by (C-A), (C-A),
and (C-A)) do not depend on the node index $i$, such that we can express

$h_{n}=\frac{1}{n}\sum_{a=0}^{n-3}(n-a-2)\,\mathsf{Pr}(L_{n-1}=a)H(L_{n}\mid
L_{n-1}=a).$ (59)

In the following we evaluate the normalized entropy in the large $n$ limit for
different regimes of scaling of the connection range $r_{n}$.

We find it more convenient to work with $\Delta L_{n-1}=L_{n-1}+1-L_{n}$
representing the difference between the indices of the leftmost nodes linked
to nodes $n$ and $n-1$. Given $L_{n-1}=a$, $\Delta
L_{n-1}\in\\{0,\ldots,a+1\\}$. For example, $\Delta L_{n-1}=0$ means nodes
$n-1$ and $n$ have the same leftmost node, while $\Delta L_{n-1}=a+1$
indicates that node $n$ is isolated. Note that $H(L_{n}\mid
L_{n-1}=a)=H(\Delta L_{n-1}\mid L_{n-1}=a)$. Based on (C-A) and (C-A), we find

$\mathsf{Pr}(\Delta L_{n-1}=k\mid
L_{n-1}=a)=\frac{(n-a)r_{n}}{(1-r_{n})}{a\choose
k}\int_{0}^{1}t^{k}(1-t)^{a-k}\left(1-\frac{r_{n}t}{1-r_{n}}\right)^{n-a-1}\mathrm{d}t$
(60)

for $k=0,\ldots,a$, whereas (C-A) and (C-A) give

$\mathsf{Pr}(\Delta L_{n-1}=a+1\mid
L_{n-1}=a)=\left(1-\frac{r_{n}}{1-r_{n}}\right)^{n-a}.$ (61)

####  C-B1 $r_{n}=O(1/n)$

We first consider $h_{n}$ given by (59). $L_{n-1}$ has a binomial
distribution222The truncation due to the left margin is negligible in this
case, as $P(L_{n-1}=n-2)$ (i.e., the probability that the $(n-1)$th node is
linked to node $1$, obtained from (C-A)) is $O(n^{-n})$. whose mean $nr_{n}$
is $O(1)$. Thus, the terms that have a significant contribution to the sum in
(59) correspond to small values of $a$. More specifically, for any $s>0$ and
sequence $\epsilon_{n}>0$, Markov’s inequality gives

$\displaystyle\mathsf{Pr}(L_{n-1}\geq n(r_{n}+\epsilon_{n}))$
$\displaystyle=\mathsf{Pr}(e^{sL_{n-1}}\geq e^{sn(r_{n}+\epsilon_{n}))}$
$\displaystyle\leq
e^{-sn(r_{n}+\epsilon_{n})}\operatorname{E}\left[e^{sL_{n-1}}\right]$
$\displaystyle=e^{-sn(r_{n}+\epsilon_{n})}(1-r_{n}+r_{n}e^{s})^{n}$
$\displaystyle=e^{-sn\epsilon_{n}}e^{-snr_{n}+n\ln(1-r_{n}+r_{n}e^{s})}$ (62)

Choosing $\epsilon_{n}=\ln(n)/n$ and $s=2$, and given that $r_{n}=O(1/n)$, we
obtain $\mathsf{Pr}(L_{n-1}\geq nr_{n}+\ln n)=O(1/n^{2})$. Furthermore, a
rough bound on the entropy of $L_{n}$ based on the size of its support is
$H(L_{n}\mid L_{n-1}=a)\leq\log_{2}(a+1)<\log_{2}n$. Thus, the terms in (59)
corresponding to $a\geq nr_{n}+\ln n=O(\ln n)$ have a contribution of
$O(\log_{2}n/n^{2})$, which is a negligible quantity. We therefore estimate
$H(L_{n}\mid L_{n-1}=a)$ for $a\ll n$.

It can be shown that
$\left(1-\frac{r_{n}t}{1-r_{n}}\right)^{n-a-1}=e^{-nr_{n}t}\left[1+O(\ln
n/n)\right]$, such that we obtain from (60) and (61) that, up to correction
terms that vanish as $n$ grows large, $\Delta L_{n-1}$ has the conditional pmf

$\mathsf{Pr}(\Delta L_{n-1}=k\mid
L_{n-1}=a)\sim\begin{cases}\frac{nr_{n}}{a+1}M(k+1,a+2,-nr_{n}),&k=0,\ldots,a,\\\
e^{-nr_{n}},&k=a+1,\end{cases}$ (63)

where $M$ is Kummer’s confluent hypergeometric function given by

$M(\alpha,\beta,z)=\frac{\Gamma(\beta)}{\Gamma(\alpha)\,\Gamma(\beta-\alpha)}\int_{0}^{1}t^{\alpha-1}(1-t)^{\beta-\alpha-1}e^{zt}\mathrm{d}t.$

It can be verified that (63) is a proper pmf. Thus, we get

$H(L_{n}\mid
L_{n-1}=a)=-\sum_{k=0}^{a}\frac{nr_{n}}{a+1}M(k+1,a+2,-nr_{n})\log_{2}\left(\frac{nr_{n}}{a+1}M(k+1,a+2,-nr_{n})\right)+\frac{nr_{n}\,e^{-nr_{n}}}{\ln
2}.$ (64)

Since the binomial distribution of $L_{n-1}$ approaches the Poisson
distribution with rate $nr_{n}$, the term $h_{n}$ given by (59) satisfies
$h_{n}\sim h_{\mathrm{U}}(nr_{n})$, where the function $h_{\mathrm{U}}$ is
defined in (25).

We now consider the term $c_{n}$ in (58). The probability
$\mathsf{Pr}(L_{i}=i-1)$ given by (C-A) can be viewed as a tail of the
binomial distribution. Similarly to the tail bound we obtained above for
$L_{n-1}$, we can show that $\mathsf{Pr}(L_{i}=i-1)=O(1/n^{2})$, for $i\geq
nr_{n}+\ln n$. The entropy term satisfies $H(L_{i+1}\mid
L_{i}=i-1)\leq\log_{2}i<\log_{2}n$. Therefore,

$\displaystyle c_{n}$ $\displaystyle=\frac{1}{n}\sum_{i=2}^{\lfloor nr_{n}+\ln
n\rfloor}\mathsf{Pr}(L_{i}=i-1)H(L_{i+1}\mid L_{i}=i-1)$ (65)
$\displaystyle\phantom{=}+O\left(\frac{\log_{2}n}{n^{2}}\right)$ (66)
$\displaystyle<\frac{1}{n}(nr_{n}+\ln n)\log_{2}(nr_{n}+\ln
n)+O\left(\frac{\log_{2}n}{n^{2}}\right)$ (67) $\displaystyle=O\left(\frac{\ln
n\ln\ln n}{n}\right).$ (68)

Thus, $c_{n}$ is vanishing with $n$.

The last term of (58), $H(L_{2})/n$, is also vanishing, since $L_{2}$ is
binary and therefore its entropy is no more than one bit. We can thus conclude
that, when $r_{n}=O(1/n)$, the upper bound on the normalized entropy $\sim
h_{\mathrm{U}}(nr_{n})$.

####  C-B2 $r_{n}=\omega(1/n)$

This implies $nr_{n}$ grows large with $n$. Examples include a vanishing
$r_{n}$ (e.g., $r_{n}\propto 1/\sqrt{n}$), or $r_{n}=r$, for some $r\in(0,1)$
bounded away from $0$ and $1$.

Turning again to $h_{n}$ in (59), in this case the sum is dominated by the
terms corresponding to $a$ on the order of the mean $nr_{n}$ of $L_{n-1}$. For
finite $k$ and $a$ large ($\sim nr_{n}$), we write (60) as

$\mathsf{Pr}(\Delta L_{n-1}=k\mid
L_{n-1}=a)\sim\frac{(n-a)r_{n}}{(1-r_{n})}\frac{a^{k}}{k!}\int_{0}^{1}t^{k}\exp\left\\{a\ln(1-t)+(n-a)\ln\left(1-\frac{r_{n}t}{1-r_{n}}\right)\right\\}\mathrm{d}t.$
(69)

The argument of the exponential is strictly decreasing in $t$, and thus the
integral is dominated by sufficiently small values of $t$. Linearizing the
exponent,

$\displaystyle\mathsf{Pr}(\Delta L_{n-1}=k\mid L_{n-1}=a)$
$\displaystyle\sim\frac{(n-a)r_{n}}{(1-r_{n})}\frac{a^{k}}{k!}\int_{0}^{1}t^{k}e^{-\left[a+\frac{(n-a)r_{n}}{1-r_{n}}\right]t}\mathrm{d}t$
(70)
$\displaystyle\sim\frac{1}{1+\frac{a(1-r_{n})}{(n-a)r_{n}}}\left(1-\frac{1}{1+\frac{a(1-r_{n})}{(n-a)r_{n}}}\right)^{k},$
(71)

for $k=0,1,\ldots$. Thus, $\Delta L_{n-1}\mid L_{n-1}=a$ has a geometric
distribution with success probability

$p=\left(1+\frac{a(1-r_{n})}{(n-a)r_{n}}\right)^{-1},$ (72)

and its entropy is given by

$H(\Delta L_{n-1}\mid L_{n-1}=a)=-\log_{2}p-\frac{1-p}{p}\log_{2}(1-p)$ (73)

To evaluate (59), we express the entropy as a function of
$x=\frac{a-nr_{n}}{(n-a)r_{n}}$, i.e., $H(\Delta L_{n-1}\mid L_{n-1}=a)=f(x)$
with $f:[-1,\infty)\to\mathbb{R}$,

$f(x)=(2+x)\log_{2}(2+x)-(1+x)\log_{2}(1+x).$ (74)

It can be verified that $f(0)=2$, $f^{\prime}(0)=1$, and $f^{\prime}(x)>0$ and
$f^{\prime\prime}(x)<0$ over the domain of $f$ (i.e., $f$ is strictly
increasing, strictly concave); therefore, $f(x)\leq 2+x$. Now, let
$g(x)=f(x)-(2+x-x^{2})$, which satisfies: $g(0)=0$, $g^{\prime}(0)=0$ and
$g^{\prime\prime}(0)>0$. Also, in addition to $x=0$, $g$ is also zero only at
$x=-1$. Consequently, $g(x)\geq 0$, such that

$2+x(a)-x^{2}(a)\leq H(\Delta L_{n-1}\mid L_{n-1}=a)\leq 2+x(a).$ (75)

Using these inequalities in (59), we obtain upper and lower limits on $h_{n}$
that differ by

$\displaystyle\frac{1}{n}\sum_{a=0}^{n-3}\mathsf{Pr}(L_{n-1}=a)(n-a-2)\frac{(a-nr_{n})^{2}}{(n-a)^{2}r_{n}^{2}}$
$\displaystyle=\frac{1}{n}\sum_{a=0}^{n-3}\frac{n!\,r_{n}^{a}(1-r_{n})^{n-a}}{(n-a)!\,a!}\frac{(a-nr_{n})^{2}}{(n-a+1)r_{n}^{2}}\left[1+O\left(\frac{1}{n}\right)\right]$
(76) $\displaystyle=\frac{\sum_{a=0}^{n-3}{n+1\choose
a}r_{n}^{a}(1-r_{n})^{n-a+1}(a-nr_{n})^{2}}{n(n+1)r_{n}^{2}(1-r_{n})}\left[1+O\left(\frac{1}{n}\right)\right]$
(77)
$\displaystyle=\left[\frac{(n+1)r_{n}(1-r_{n})+r_{n}^{2}}{n(n+1)r_{n}^{2}(1-r_{n})}+O\left(n^{3}r_{n}^{n-4}\right)\right]\left[1+O\left(\frac{1}{n}\right)\right]$
(78)
$\displaystyle=\frac{1}{nr_{n}}+O\left(\frac{1}{n^{2}r_{n}}\right)\xrightarrow{n\to\infty}0$
(79)

Thus, the upper and lower limits on $h_{n}$ are asymptotically equivalent to
each other, and hence

$\displaystyle h_{n}$
$\displaystyle\sim\frac{1}{n}\sum_{a=0}^{n-3}\mathsf{Pr}(L_{n-1}=a)(n-a-2)\left[2+\frac{(a-nr_{n})}{(n-a)r_{n}}\right]$
(80) $\displaystyle\sim 2(1-r_{n}),$ (81)

where the result was obtained by taking similar steps to the above.

We now prove that $c_{n}$, defined in (58) as

$c_{n}=\frac{1}{n}\sum_{i=2}^{n-1}\mathsf{Pr}(L_{i}=i-1)H(L_{i+1}\mid
L_{i}=i-1)$ (82)

goes to zero as $n$ grows large. First, we show that the terms of the sum that
defines $c_{n}$ are negligible for indices that satisfy
$|i-nr_{n}-1|>\sqrt{n\ln n}$. Since $\mathsf{Pr}(L_{i}=i-1)$ given by (C-A) is
a tail probability, Hoeffding’s inequality gives

$\mathsf{Pr}(L_{i}=i-1)\leq e^{-2n\left(\frac{i-1}{n}-r_{n}\right)^{2}}$ (83)

for all $i>nr_{n}+1$. Therefore,

$\mathsf{Pr}(L_{i}=i-1)\leq\frac{1}{n^{2}},$ (84)

for all $i>nr_{n}+1+\sqrt{n\ln n}$. Furthermore, the support of $L_{i+1}\mid
L_{i}=i-1$ is $\\{0,\ldots,i\\}$, such that $H(L_{i+1}\mid
L_{i}=i-1)\leq\log_{2}(i+1)\leq\log_{2}(n)$. Hence, the overall contribution
of the terms in (82) corresponding to $i>nr_{n}+1+\sqrt{n\ln n}$ is
$O(\log_{2}(n)/n^{2})$, which is negligible for large $n$. Similarly, from
(C-A),

$\displaystyle\mathsf{Pr}(L_{i+1}=i)$
$\displaystyle=1-\sum_{a=0}^{i-1}{n\choose a}r^{a}(1-r)^{n-a}$ (85)
$\displaystyle\geq 1-e^{-2n\left(r_{n}-\frac{i-1}{n}\right)^{2}}$ (86)
$\displaystyle\geq 1-\frac{1}{n^{2}}$ (87)

for all $i<nr_{n}+1-\sqrt{n\ln n}$. The probability that both the nodes $i$
and $i+1$ are connected by an edge to node 1 is the same as the probability
that $i+1$ is linked to node 1, which translates to
$\mathsf{Pr}(L_{i}=i-1,L_{i+1}=i)=\mathsf{Pr}(L_{i+1}=i)$, such that

$\mathsf{Pr}(L_{i+1}=i\mid
L_{i}=i-1)=\frac{\mathsf{Pr}(L_{i+1}=i)}{\mathsf{Pr}(L_{i}=i-1)}\geq
1-\frac{1}{n^{2}}.$ (88)

Therefore, using the log sum inequality and then (88),

$\displaystyle H(L_{i+1}\mid L_{i}=i-1)$
$\displaystyle=-\mathsf{Pr}(L_{i+1}=i\mid
L_{i}=i-1)\log_{2}\mathsf{Pr}(L_{i+1}=i\mid L_{i}=i-1)$ (89)
$\displaystyle\phantom{=}-\sum_{k=0}^{i-1}\mathsf{Pr}(L_{i+1}=k\mid
L_{i}=i-1)\log_{2}\mathsf{Pr}(L_{i+1}=k\mid L_{i}=i-1)$ (90)
$\displaystyle\leq-\mathsf{Pr}(L_{i+1}=i\mid
L_{i}=i-1)\log_{2}\mathsf{Pr}(L_{i+1}=i\mid L_{i}=i-1)$ (91)
$\displaystyle\phantom{\leq}-\left[1-\mathsf{Pr}(L_{i+1}=i\mid
L_{i}=i-1)\right]\log_{2}\left(\frac{1-\mathsf{Pr}(L_{i+1}=i\mid
L_{i}=i-1)}{i}\right)$ (92)
$\displaystyle=O\left(\frac{\log_{2}n}{n^{2}}\right),$ (93)

for all $i<nr_{n}+1-\sqrt{n\ln n}$. Thus, the terms in (82) corresponding to
$i<nr_{n}+1-\sqrt{n\ln n}$ have a negligible contribution. Finally, summing in
(82) over the range $nr_{n}+1-\sqrt{n\ln n}<i<nr_{n}+1+\sqrt{n\ln n}$, and
using $H(L_{i+1}\mid L_{i}=i-1)\leq\log_{2}(i+1)<\log_{2}(nr_{n}+2+\sqrt{n\ln
n})$ and that the probabilities are less than one, we obtain

$c_{n}<\frac{1}{n}2\lceil{\sqrt{n\ln n}}\rceil\log_{2}(nr_{n}+2+\sqrt{n\ln
n})\xrightarrow{n\to\infty}0.$ (94)

Since $H(L_{2})\leq 1$, we conclude that when $r_{n}=\omega(1/n)$ the upper
bound on the entropy per node given by (58) is asymptotically equivalent to
$2(1-r_{n})$.

##  Appendix D Proof of Proposition 5

Based on (21), we write

$\frac{1}{n}H(\hat{G}_{n,r})\geq\frac{1}{n}H(L_{2})+\underbrace{\frac{1}{n}\sum_{i=2}^{n-1}\sum_{a=0}^{i-2}\mathsf{Pr}(L_{i}=a)H\left(L_{i+1}\mid
L_{i}=a,X_{(i-a)},\ldots,X_{(i)}\right)}_{h_{n}^{\prime}}\\\
+\underbrace{\frac{1}{n}\sum_{i=2}^{n-1}\mathsf{Pr}(L_{i}=i-1)H\left(L_{i+1}\mid
L_{i}=i-1,X_{(1)},\ldots,X_{(i)}\right)}_{c_{n}^{\prime}},$ (95)

where we have isolated in the term denoted by $c_{n}^{\prime}$ the case when
$L_{i}=i-1$, i.e., the $i$th node is directly connected to the first node.

In the following, we evaluate the term $h_{n}^{\prime}$ in (21). The variable
$L_{i}$ has a truncated binomial distribution, see Appendix C. Focusing on the
conditional distribution of $L_{i+1}$, let $\Delta_{(i+1)}=X_{(i+1)}-X_{(i)}$
be the gap between the $i$th and $(i+1)$th consecutive points. Given
$L_{i}=a$, we define the distances $W_{0},\ldots,W_{a-1}$ as
$W_{a-b+1}=X_{(i-b+1)}-(X_{(i)}-r)$, $b=2,\ldots,a+1$. The conditional
distribution of $L_{i+1}\mid L_{i}=a$ is obtained by observing that:

  * •

$L_{i+1}=0\Leftrightarrow\Delta_{(i+1)}>r$;

  * •

$L_{i+1}=1\Leftrightarrow W_{a-1}<\Delta_{(i+1)}\leq r$;

  * •

$L_{i+1}=b\in\\{2,\ldots,a\\}\Leftrightarrow W_{a-b}<\Delta_{(i+1)}\leq
W_{a-b+1}$;

  * •

$L_{i+1}=a+1\Leftrightarrow\Delta_{(i+1)}\leq W_{0}$.

When conditioning on $X_{(i)}=x>r$, the locations $X_{(i-a)},\dots,X_{(i-1)}$
of the $a$ leftward neighbors of $i$ are independent of the $n-i$ locations
$X_{(i+1)},\ldots,X_{(n)}$; the former locations are i.u.d. on $[x-r,x]$,
given $L_{i}$, whereas the latter are i.u.d. over $[x,1]$. Therefore, the gap
$\Delta_{(i+1)}$ is independent of $L_{i}$ given $X_{(i)}$ and its
distribution is given by

$\mathsf{Pr}\left(\Delta_{(i+1)}>u\mid
X_{(i)}=x,L_{i}=a\right)=\left(1-\frac{u}{1-x}\right)^{n-i},$ (96)

where $0\leq u\leq 1-x$. Furthermore, given $L_{i}=a$, the distances
$W_{0},\ldots,W_{a-1}$ are independent of $X_{(i)}$, and their distribution is
dictated by the fact that the $a$ points are i.u.d over an interval of length
$r$. The following conditional pdfs are obtained:

$f_{W_{0}\mid L_{i}}(u\mid a)=\frac{a(r-u)^{a-1}}{r^{a}},\quad 0<u<r,$ (97)
$f_{W_{a-1}\mid L_{i}}(u\mid a)=\frac{au^{a-1}}{r^{a}},\quad 0<u<r,$ (98)

and

$f_{W_{a-b},W_{a-b+1}\mid L_{i}}(u,v\mid
a)=\frac{a!\,u^{a-b}(r-v)^{b-2}}{(a-b)!\,(b-2)!\,r^{a}},$ (99)

for $b=2,\ldots,a$ and $0<u<v<r$.

The joint distribution of $X_{(i)}$ and $L_{i}$ is characterized by

$\mathsf{Pr}\left(X_{(i)}\in[x,x+\mathrm{d}x],L_{i}=a\right)=\frac{n!\,(x-r)^{i-a-1}\,r^{a}\,(1-x)^{n-i}}{(i-a-1)!\,a!\,(n-i)!}\mathrm{d}x,$
(100)

for $a\in\\{0,\ldots,i-2\\}$ and $x>r$.333Since $a\leq i-2$, such that the
$i$th node is not connected by an edge to node $1$, it must hold that $x>r$,
otherwise the two nodes are within the range $r$. The probability (100)
follows from the fact that the $n$ points are i.u.d. in $[0,1]$ and the
desired event occurs when $i-a-1$ points fall in $[0,x-r]$, $a$ points in
$(x-r,x)$, and $n-i$ points in $(x,1]$. Using (C-A), we obtain the conditional
density

$f_{X_{(i)}\mid
L_{i}=a}(x)=\frac{(n-a)!\,(x-r)^{i-a-1}\,(1-x)^{n-i}}{(1-r)^{n-a}(i-a-1)!\,(n-i)!},$
(101)

for $a\in\\{0,\ldots,i-2\\}$ and $x\in(r,1)$; the density is zero, otherwise.
From (101), the conditional mean and variance of $X_{(i)}$ are
$\mu=r+\frac{(1-r)(i-a)}{n-a+1}$ and
$\sigma^{2}=\frac{(1-r)^{2}(i-a)(n-i+1)}{(n-a+1)^{2}(n-a+2)}$, respectively.
For large $n$, the variance vanishes, such that, for any fixed $t$, we develop
(96) as

$\displaystyle\mathsf{Pr}\left(\Delta_{(i+1)}>u\mid X_{(i)}=\mu+\sigma
t,L_{i}=a\right)$
$\displaystyle=\left(1-\frac{(n-a+1)u}{(1-r)(n-i+1)\left[1+O(1/\sqrt{n})\right]}\right)^{n-i}$
$\displaystyle\sim e^{-\lambda_{a}u},$ (102)

for all indices $i$ such that $n-i$ is large, and where
$\lambda_{a}=\frac{n-a}{1-r}$.

Based on the above, for all $i=2,\ldots,\lfloor n-\sqrt{n}\rfloor$ (such that
$n-i$ is large), we express the conditional entropy as

$H\left(L_{i+1}\mid
L_{i}=a,X_{(i-a)},\ldots,X_{(i)}\right)\sim\sum_{b=0}^{a+1}g_{a,b}$ (103)

with $g_{a,0}=-e^{-\lambda_{a}r}\log_{2}e^{-\lambda_{a}r}$,

$\displaystyle g_{a,1}$
$\displaystyle=\operatorname{E}\left[-\left(e^{-\lambda_{a}W_{a-1}}-e^{-\lambda_{a}r}\right)\log_{2}\left(e^{-\lambda_{a}W_{a-1}}-e^{-\lambda_{a}r}\right)\right],$
$\displaystyle g_{a,b}$
$\displaystyle=\operatorname{E}\left[-\left(e^{-\lambda_{a}W_{a-b}}-e^{-\lambda_{a}W_{a-b+1}}\right)\log_{2}\left(e^{-\lambda_{a}W_{a-b}}-e^{-\lambda_{a}W_{a-b+1}}\right)\right],\quad
2\leq b\leq a,$ $\displaystyle g_{a,a+1}$
$\displaystyle=\operatorname{E}\left[-\left(1-e^{-\lambda_{a}W_{0}}\right)\log_{2}\left(1-e^{-\lambda_{a}W_{0}}\right)\right],$

where the expectations are with respect to the distances with conditional pdfs
(97)–(99). By exchanging the expectation with the sum over $b$ and then
evaluating the sum from $b=2$ to $a$, we obtain

$\displaystyle\sum_{b=0}^{a+1}g_{a,b}$
$\displaystyle\sim\frac{\lambda_{a}r}{\ln
2}e^{-\lambda_{a}r}-\int_{0}^{r}\frac{au^{a-1}}{r^{a}}\left(e^{-\lambda_{a}u}-e^{-\lambda_{a}r}\right)\log_{2}\left(e^{-\lambda_{a}u}-e^{-\lambda_{a}r}\right)\mathrm{d}u$
$\displaystyle\phantom{\sim}-\iint_{0<u<v<r}\frac{a(a-1)}{r^{a}}(r-v+u)^{a-2}\left(e^{-\lambda_{a}u}-e^{-\lambda_{a}v}\right)\log_{2}\left(e^{-\lambda_{a}u}-e^{-\lambda_{a}v}\right)\mathrm{d}u\,\mathrm{d}v$
$\displaystyle\phantom{\sim}-\int_{0}^{r}\frac{a(r-v)^{a-1}}{r^{a}}\left(1-e^{-\lambda_{a}v}\right)\log_{2}\left(1-e^{-\lambda_{a}v}\right)\mathrm{d}v$
(104)

Given that for large $n$ (103) does not depend on $i$ in the range
$2,\ldots,\lfloor n-\sqrt{n}\rfloor$, we truncate the sum that defines
$h_{n}^{\prime}$ in (95) at $i=\lfloor n-\sqrt{n}\rfloor$. The error due to
discarding the $\sqrt{n}$ terms vanishes with $n$, because the conditional
entropy of $L_{i+1}$ is $O(\ln n)$ and the sum of probabilities is less than
one, such that the truncation error is $O(\frac{\sqrt{n}\ln n}{n})$. Thus, we
can express the double sum as a single sum over $a$, such that

$h_{n}^{\prime}\sim\frac{1}{n}\sum_{a=0}^{\lfloor n-\sqrt{n}\rfloor-2}(\lfloor
n-\sqrt{n}\rfloor-a-2){n\choose a}r^{a}(1-r)^{n-a}\sum_{b=0}^{a+1}g_{a,b}.$
(105)

Next, we consider a connection range that vanishes with $n$, i.e.,
$r_{n}=o(1)$. In this regime, $\mathsf{Pr}(L_{i}=a)$ is significant only for
$a\ll n$, such that, for large $n$, $\lambda_{a}\sim n$ and upon summing over
$a$ (105) becomes

$\displaystyle h_{n}^{\prime}$ $\displaystyle\sim\sum_{a=0}^{n}{n\choose
a}r_{n}^{a}(1-r_{n})^{n-a}\sum_{b=0}^{a+1}g_{a,b}$
$\displaystyle\sim\frac{1}{\ln
2}\bigg{[}nr_{n}e^{-nr_{n}}-\int_{0}^{r_{n}}n(1-r_{n}+u)^{n-1}\left(e^{-nu}-e^{-nr_{n}}\right)\ln\left(e^{-nu}-e^{-nr_{n}}\right)\mathrm{d}u$
$\displaystyle\phantom{\sim}-\iint_{0<u<v<r}n(n-1)(1-v+u)^{n-2}\left(e^{-nu}-e^{-nv}\right)\ln\left(e^{-nu}-e^{-nv}\right)\mathrm{d}u\,\mathrm{d}v$
$\displaystyle\phantom{\sim}-\int_{0}^{r_{n}}n(1-v)^{n-1}\left(1-e^{-nv}\right)\ln\left(1-e^{-nv}\right)\mathrm{d}v\bigg{]}$
(106)

Denote the three integral terms in (D) by $I_{1}$, $I_{2}$ and $I_{3}$ (in the
order of their appearance). We obtain

$\displaystyle I_{1}$
$\displaystyle\sim-\int_{0}^{r_{n}}ne^{-nr_{n}}\left(1-e^{-nr_{n}}e^{nu}\right)\left[-nu+\ln\left(1-e^{-n(r_{n}-u)}\right)\right]\mathrm{d}u$
$\displaystyle=n^{2}r_{n}^{2}e^{-nr_{n}}\int_{0}^{1}\left(x-e^{-nr_{n}}x\,e^{nr_{n}x}\right)\,\mathrm{d}x-nr_{n}e^{-nr_{n}}\int_{0}^{1}\left(1-e^{-nr_{n}x}\right)\ln\left(1-e^{-nr_{n}x}\right)\mathrm{d}x$
$\displaystyle=e^{-nr_{n}}\left(\frac{n^{2}r_{n}^{2}}{2}-nr_{n}+1-e^{-nr_{n}}\right)-nr_{n}e^{-nr_{n}}\int_{0}^{1}\left(1-e^{-nr_{n}x}\right)\ln\left(1-e^{-nr_{n}x}\right)\mathrm{d}x,$

where we substituted $x=(r_{n}-u)/r_{n}$. For $I_{2}$, we define $w=v-u$ and
write the double integral as

$I_{2}\sim-\int_{0}^{r_{n}}\int_{0}^{r-w}n^{2}e^{-nw}e^{-nu}\left(1-e^{-nw}\right)\left[-nu+\ln(1-e^{-nw}\right]\mathrm{d}u\,\mathrm{d}w.$

Integrating over $u$ and then over $w$ we finally obtain

$I_{2}\sim\frac{1}{2}\left(1-e^{-nr_{n}}\right)^{2}-\frac{n^{2}r_{n}^{2}}{2}e^{-nr_{n}}+nr_{n}e^{-nr_{n}}\int_{0}^{1}\left(1-e^{-nr_{n}x}\right)\ln\left(1-e^{-nr_{n}x}\right)\mathrm{d}x+I_{3},$

where

$\displaystyle I_{3}$
$\displaystyle\sim-\int_{0}^{r_{n}}ne^{-nv}\left(1-e^{-nv}\right)\ln\left(1-e^{-nv}\right)\mathrm{d}v$
$\displaystyle=-\int_{0}^{1-e^{-nr_{n}}}x\ln x\,\mathrm{d}x$
$\displaystyle=\frac{1}{4}\left(1-e^{-nr_{n}}\right)^{2}\left[1-2\ln\left(1-e^{-nr_{n}}\right)\right],$

where in the second line we made the substitution $x=1-e^{-nv}$. Plugging the
expressions for $I_{1}$, $I_{2}$, and $I_{3}$ back into (D), we finally obtain
that asymptotically in $n$,

$h_{n}^{\prime}\sim\frac{1-e^{-nr_{n}}}{\ln
2}-\left(1-e^{-nr_{n}}\right)^{2}\log_{2}\left(1-e^{-nr_{n}}\right).$ (107)

Given that conditioning reduces the entropy, the positive term denoted by
$c_{n}^{\prime}$ in (95) is smaller than $c_{n}$ defined in (58). As shown in
Appendix C, $c_{n}$ vanishes with $n$; therefore, $c_{n}^{\prime}$ is also
vanishing. Since $L_{2}$ is a binary variable, $H(L_{2})/n$ also vanishes with
$n$. Thus, the result follows.