## 5 Application of de Finetti Style Theorems in Random Network Analysis  
Large, random networks, such as wireless ad hoc networks, are often described by various types of random graphs, primarily by geometric random graphs. A frequently used model is when each node of the network is represented as a random point in some planar domain, and two such nodes are connected by an edge (a network link) if they are within a given distance from each other. This basic model has many variants: various domains may occur, different probability distributions of the node positions within the domain may be used, a variety of distance metrics is possible, etc. Note that it falls in the category of static random graph models, which is our focus here, in contrast to evolving ones (for a survey of random graph models, see e.g., [PERSON] and [PERSON] [21]). Let us now formalize what we mean by a general random graph model. **Definition 6** (Random graph models): _Let \(X=(X_{1},X_{2},X_{3},\ldots)\) be an infinite sequence of random variables, each taking its values from a fixed domain \(S\), which is an arbitrary measurable space. A random graph model over \(S\) is a function \(\mathbf{G}\) that maps \(X\) into a sequence of graphs:_  
\[\mathbf{G}(X)=(G_{1},G_{2},G_{3}\ldots).\]  
_If \(X\) is restricted to a subset \(C\subseteq S^{\infty}\), then we talk about a conditional random graph model, denoted by \(\mathbf{G}(X\,|\,C)\)._  
Note that even though the random graph model \(\mathbf{G}(X)\) depends on the infinite sequence \(X\), the individual graphs \(G_{n}\) typically depend only on an initial segment of \(X\), such as \((X_{1},\ldots,X_{n})\). Regarding the condition \(C\), a very simple variant is when \(C=C_{1}\times C_{2}\times C_{3}\times\ldots\), where \(C_{i}\subseteq S\), and we independently restrict each \(X_{i}\) to fall into \(C_{i}\). Note, however, that \(C\) may be much more complicated, possibly not reducible to individual restrictions on each \(X_{i}\). A most frequently occurring case is when the points (the components of \(X\)) are selected from the same distribution independently, that is, they are i.i.d. The reason is that allowing dependencies makes the analysis too messy. To this end, let us define i.i.d.-based random graph models:  
**Definition 7** (i.i.d.-based random graph models): _If the entries of \(X\) in Definition 6 are i.i.d. random variables, then we call \(\mathbf{G}(X)\) an i.i.d.-based random graph model over \(S\), and \(\mathbf{G}(X\,|\,C)\) is called an i.i.d.-based conditional random graph model over \(S\)._  
The most commonly used and analyzed static random graphs are easily seen to fall in the category of i.i.d.-based random graph models. Typical examples are Erdos-Renyi random graphs (when each edge is added independently with some probability \(p\)), different variants of geometric random graphs, random intersection graphs, and many others. On the other hand, sometimes the application provides natural reasons for considering dependent points, as shown by the following example. **Example 3**: _Consider a wireless ad hoc network. Let each node be a point drawn independently and uniformly from the unit square. Specify a transmission radius \(r>0\), and connect two nodes whenever they are within distance \(r\). (Note: \(r=r_{n}\) may depend on the number of nodes.) However, allow only those systems of points for which the arising graph has diameter (in terms of graph distance) of at most some value \(D=D_{n}\), which may again depend on \(n\). The conditioning makes the points dependent. Nevertheless, the restriction is reasonable if we want the network to experience limited delays in end-to-end transmissions._  
This example (and many possible similar ones) shows that there can be good reasons to deviate from the standard i.i.d. assumption. On the other hand, most of the analysis results build on the i.i.d. assumption. How can we bridge this gap?