11.4. Erdös-Rényi (ER) Random Networks

The Erdös Rényi model formalizes this relatively simple situation with a single parameter and an \(iid\) assumption:

Parameter	Space	Description
\(p\)	\([0, 1]\)	Probability that an edge exists between a pair of nodes, which is identical for all pairs of nodes

From here on out, when we talk about an Erdös Rényi random variable, we will simply call it an ER network. In an ER network, each pair of nodes is connected with probability \(p\), and therefore not connected with probability \(1-p\). Statistically, we say that for each edge \(\mathbf{a}_{ij}\) for every pair of nodes where \(j > i\) (in terms of the adjacency matrix, this means all of the edges in the upper right triangle), that \(\mathbf{a}_{ij}\) is sampled independently and identically from a Bernoulli distribution with probability \(p\). The word “independent” means that edges in the network occurring or not occurring do not affect one another. For instance, this means that if we knew a student named Alice was friends with Bob, and Alice was also friends with Chadwick, that we do not learn any information about whether Bob is friends with Chadwick. The word “identical” means that every edge in the network has the same probability \(p\) of being connected. If Alice and Bob are friends with probability \(p\), then Alice and Chadwick are friends with probability \(p\), too. We assume here that the networks are undirected, which means that if an edge \(\mathbf a_{ij}\) exists from node \(i\) to \(j\), then the edge \(\mathbf a_{ji}\) also exists from node \(j\) to node \(i\). We also assume that the networks are loopless, which means that no edges \(\mathbf a_{ii}\) can go from node \(i\) to itself. If \(\mathbf A\) is the adjacency matrix for an ER network with probability \(p\), we write that \(\mathbf A \sim ER_n(p)\).

Next, let’s formalize an example of one of the limitations of an ER random network. Remember that we said that ER random networks are often too simple. Well, one way in which they are simple is called degree homogeneity, which is a property in which all of the nodes in an ER network have the exact same expected node degree! What this means is that if we were to take an ER random network \(\mathbf A\), we would expect that all of the nodes in the network had the same degree. Let’s see how this works:

Working Out the Expected Degree in an Erdös-Rényi Network

Suppose that \(\mathbf A\) is a simple network which is random. The network has \(n\) nodes \(\mathcal V = (v_i)_{i = 1}^n\). Recall that the in a simple network, the node degree is \(deg(v_i) = \sum_{j = 1}^n \mathbf a_{ij}\). What is the expected degree of a node \(v_i\) of a random network \(\mathbf A\) which is Erdös-Rényi?

To describe this, we will compute the expectated value of the degree \(deg(v_i)\), written \(\mathbb E\left[deg(v_i)\right]\). Let’s see what happens:

\[\begin{align*} \mathbb E\left[deg(v_i)\right] &= \mathbb E\left[\sum_{j = 1}^n \mathbf a_{ij}\right] \\ &= \sum_{j = 1}^n \mathbb E[\mathbf a_{ij}] \end{align*}\]

We use the linearity of expectation in the line above, which means that the expectation of a sum with a finite number of terms being summed over (\(n\), in this case) is the sum of the expectations. Finally, by definition, all of the edges \(A_{ij}\) have the same distribution: \(Bern(p)\). The expected value of a random quantity which takes a Bernoulli distribution is just the probability \(p\). This means every term \(\mathbb E[\mathbf a_{ij}] = p\). Therefore:

\[\begin{align*} \mathbb E\left[deg(v_i)\right] &= \sum_{j = 1}^n p = n\cdot p \end{align*}\]

Since all of the \(n\) terms being summed have the same expected value. This holds for every node \(v_i\), which means that the expected degree of all nodes is an undirected ER network is the same number, \(n \cdot p\).

11.4.1. Probability

What is the probability for realizations of Erdös-Rényi networks? Remember that for Independent-edge graphs, that the probability can be written:

\[\begin{align*} Pr_{\theta}(A) &= \prod_{j > i} Pr_\theta(\mathbf{a}_{ij} = a_{ij}) \end{align*}\]

Next, we recall that by assumption of the ER model, that the probability matrix \(P = (p)\), or that \(p_{ij} = p\) for all \(i,j\). Therefore:

\[\begin{align*} Pr_\theta(A) &= \prod_{j > i} p^{a_{ij}}(1 - p)^{1 - a_{ij}} \\ &= p^{\sum_{j > i} a_{ij}} \cdot (1 - p)^{\binom{n}{2} - \sum_{j > i}a_{ij}} \\ &= p^{m} \cdot (1 - p)^{\binom{n}{2} - m} \end{align*}\]

This means that the probability \(Pr_\theta(A)\) is a function only of the number of edges \(m = \sum_{j > i}a_{ij}\) in the network represented by adjacency matrix \(A\). The equivalence class on the Erdös-Rényi networks are the sets:

\[\begin{align*} E_{i} &= \left\{A \in \mathcal A_n : m = i\right\} \end{align*}\]

where \(i\) index from \(0\) (the minimum number of edges possible) all the way up to \(n^2\) (the maximum number of edges possible). All of the relationships for equivalence classes discussed above apply to the sets \(E_i\).

11.4.2. Network Models for networks which aren’t simple

To make the discussions a little more easy to handle, in the above descriptions and all our successive descriptions, we will describe network models for simple networks. To recap, networks which are simple are binary networks which are both loopless and undirected. Stated another way, simple networks are networks whose adjacency matrices are only \(0\)s and \(1\)s, they are hollow (the diagonal is entirely 0), and symmetric (the lower and right triangles of the adjacency matrix are the same). What happens our networks don’t quite look this way?

For now, we’ll keep the assumption that the networks are binary, but we will discuss non-binary network models in a later chapter. We have three possibilities we can consider, and we will show how the “relaxations” of the assumptions change a description of a network model. A relaxation, in statistician speak, means that we are taking the assumptions that we had (in this case, that the networks are simple), and progressively making the assumptions weaker (more relaxed) so that they apply to other networks, too. We split these out so we can be as clear as possible about how the generative model changes with each relaxation step.

We will compare each relaxation to the statement about the generative model for the ER generative model. To recap, for a simple network, we wrote:

“Statistically, we say that for each edge \(\mathbf{a}_{ij}\) for every pair of nodes where \(j > i\) (in terms of the adjacency matrix, this means all of the nodes in the upper right triangle), that \(\mathbf{a}_{ij}\) is sampled independently and identically from a Bernoulli distribution with probability \(p\)…. We assume here that the networks are undirected, which means that if an edge \(\mathbf a_{ij}\) exists from node \(i\) to \(j\), then the edge \(\mathbf a_{ji}\) also exists from node \(j\) to node \(i\). We also assume that the networks are loopless, which means that no edges \(\mathbf a_{ii}\) can go from node \(i\) to itself.”

Any additional parts that are added are expressed in green font. Omitted parts are struck through with red font.

Note that these generalizations apply to any of the successive networks which we describe in the Network Models section, and not just the ER model!

11.4.2.1. Binary network model which has loops, but is undirected

Here, all we want to do is relax the assumption that the network is loopless. We simply ignore the statement that edges \(\mathbf a_{ii}\) cannot exist, and allow that the \(\mathbf a_{ij}\) which follow a Bernoulli distribution (with some probability which depends on the network model choice) now applies to \(j \geq i\), and not just \(j > i\). We keep that an edge \(\mathbf a_{ij}\) existing implies that \(\mathbf a_{ji}\) also exists, which maintains the symmetry of \(\mathbf A\) (and consequently, the undirectedness of the network).

Our description of the ER network changes to:

Statistically, we say that for each edge \(\mathbf{a}_{ij}\) for every pair of nodes where \(\mathbf{\color{green}{j \geq i}}\) (in terms of the adjacency matrix, this means all of the nodes in the upper right triangle and the diagonal), that \(\mathbf{a}_{ij}\) is sampled independently and identically from a Bernoulli distribution with probability \(p\)…. We assume here that the networks are undirected, which means that if an edge \(\mathbf a_{ij}\) exists from node \(i\) to \(j\), then the edge \(\mathbf a_{ji}\) also exists from node \(j\) to node \(i\). We also assume that the networks are loopless, which means that no edges \(\mathbf a_{ii}\) can go from node \(i\) to itself.

11.4.2.2. Binary network model which is loopless, but directed

Like above, we simply ignore the statement that \(\mathbf a_{ji} = \mathbf a_{ij}\), which removes the symmetry of \(\mathbf A\) (and consequently, removes the undirectedness of the network). We allow that the \(\mathbf a_{ij}\) which follows a Bernoulli distribution now apply to \(j \neq i\), and not just \(j > i\). We keep that \(\mathbf a_{ii} = 0\), which maintains the hollowness of \(\mathbf A\) (and consequently, the undirectedness of the network).

Our description of the ER network changes to:

Statistically, we say that for each edge \(\mathbf{a}_{ij}\) for every pair of nodes where \(\mathbf{\color{green}{j \neq i}}\) (in terms of the adjacency matrix, this means all of the nodes in the upper right trianglewhich are not along the diagonal), that \(\mathbf{a}_{ij}\) is sampled independently and identically from a Bernoulli distribution with probability \(p\)…. We assume here that the networks are undirected, which means that if an edge \(\mathbf a_{ij}\) exists from node \(i\) to \(j\), then the edge \(\mathbf a_{ji}\) also exists from node \(j\) to node \(i\). We also assume that the networks are loopless, which means that no edges \(\mathbf a_{ii}\) can go from node \(i\) to itself.

11.4.2.3. Binary network model which is has loops and is directed

Finally, for a network which has loops and is directed, we combine the above two approaches. We ignore the statements that \(\mathbf a_{ji} = \mathbf a_{ij}\), and the statement that \(\mathbf a_{ii} = 0\).

Our descriptiomn of the ER network changes to:

Statistically, we say that for each edge \(\mathbf{a}_{ij}\) where \(j > i\) (in terms of the adjacency matrix, this means all of the nodes in the upper right triangle), that \(\mathbf{a}_{ij}\) is sampled independently and identically from a Bernoulli distribution with probability \(p\), for all possible combinations of nodes \(j\) and \(i\). We assume here that the networks are undirected, which means that if an edge \(\mathbf a_{ij}\) exists from node \(i\) to \(j\), then the edge \(\mathbf a_{ji}\) also exists from node \(j\) to node \(i\). We also assume that the networks are loopless, which means that no edges \(\mathbf a_{ii}\) can go from node \(i\) to itself.