Gilbert Model
Definition 1 2
Simple Definition
A random network where links of a simple network are connected independently according to probability $p \in [0,1]$ is called the Gilbert Model $\mathbb{G}_{n,p}$.
Complicated Definition
Given a probability space $( \Omega , \mathcal{F} , P)$, and a network’s properties $2^{\binom{n}{2}} \subseteq 2^{\binom{n}{2}}$ with $n$ labeled nodes. A function that is measurable with respect to $\mathcal{F}$ and has the following probability mass function for the number of links $0 \le m \le \binom{n}{2}$ is called the Gilbert Model. $$ P \left( \mathbb{G}_{n,p} = G \right) = p^{m} \left( 1 - p \right)^{\binom{n}{2} - m} \qquad , \forall G \in \mathscr{G}_{n,m} \subset 2^{\binom{n}{2}} $$
Explanation
The Gilbert model, along with the Erdős-Rényi Model (ER Model), is mentioned in numerous documents, but in reality, many refer to the ER model when they actually use the Gilbert Model. There are differences between the two models. In fact, delving into it reveals they are different models enough to fill an entire thick book, but especially in the context of applied network theory, there is a strong tendency to lump these two together under the ER model. Although not a commonly used expression, it can also be called a Binomial Random Network given that its probability distribution is the binomial distribution.
$\mathbb{G}_{n,p}$ is expected to have approximately $\displaystyle m = \binom{n}{2} p \approx {{ n^{2} p } \over { 2 }}$ links. Unlike the ER model, which exactly has $m$ links, the number of links in the Gilbert Model is proportional to the network size by a coefficient $p$, but the number of links is not fixed.
The definition might seem complex at a glance, but the algorithm is actually simple. Sampling a network using the Gilbert Model follows this algorithm.
Algorithm
Input
Assume the number of nodes $n \in \mathbb{N}$ and the link probability $p \in \left( 0, 1 \right)$ are given.
Step 1. Initialization
Create a null graph $G$ with $n$ nodes.
Step 2. Bernoulli Trials
for $i = 1 , \cdots , n$
for $j = 1 , \cdots , n$
if $i \ne j$
Add a link $ij$ to the network $G$ with probability $p$.$$G \gets G + ij$$
Output
Obtain a simple graph $G \in 2^{\binom{n}{2}}$ with $n$ nodes and approximately $m \approx n^{2} p / 2$ links.
Properties
- [1]: The number of links sampled from the Gilbert Model $\mathbb{G}_{n,p}$ exactly needing to be $m$ is the same as being sampled in $\mathbb{G}_{n,m}$.
- [2] Degree distribution: If $\lambda = np$, then when $n \to \infty$, the degree of each node converges in distribution to the Poisson distribution $\displaystyle \text{Poi} \left( np \right)$. $$ P \left( \deg v = k \right) \to {{ e^{-\lambda} \lambda^{k} } \over { k! }} \qquad , \lambda \approx np $$
Proof
[1]
Erdős-Rényi Model: This random graph is called the Erdős–Rényi Graph $\mathbb{G}_{n,m}$, with the following probability mass function. $$ P \left( \mathbb{G}_{n,m} = G \right) = \binom{\binom{n}{2}}{m}^{-1} \qquad , \forall G \in \mathscr{G}_{n,m} $$
Claim: For any $G_{0} \in \mathscr{G}_{n,m}$, it suffices to prove the following. $$ P \left( \mathbb{G}_{n,p} = G_{0} | \mathbb{G}_{n,p} \in \mathscr{G}_{n,m} \right) = \binom{\binom{n}{2}}{m}^{-1} $$
Obviously, the probability of having exactly $G_{0}$ links in $\mathbb{G}_{n,p}$ is less than having $\mathbb{G}_{n,p} \in \mathscr{G}_{n,m}$ links, i.e., sampling with the Gilbert Model and ending up with $m$ links in total. Representing this as an event gives $$ \begin{align*} \left\{ \mathbb{G}_{n,p} = G_{0} \right\} & \subset \left\{ \mathbb{G}_{n,p} \in \mathscr{G}_{n,m} \right\} \\ \implies \left\{ \mathbb{G}_{n,p} = G_{0} \right\} & \cap \left\{ \mathbb{G}_{n,p} \in \mathscr{G}_{n,m} \right\} = \left\{ \mathbb{G}_{n,p} = G_{0} \right\} \qquad \cdots (\star) \end{align*} $$ Calculating each probability gives $\displaystyle P \left( \mathbb{G}_{n,p} = G_{0} \right) = p^{m} \left( 1 - p \right)^{\binom{n}{2} - m}$ thus $$ \begin{align*} & P \left( \mathbb{G}_{n,p} \in \mathscr{G}_{n,m} \right) \\ =& P \left( \bigcup_{G \in \mathscr{G}_{n,m}} \left\{ \mathbb{G}_{n,p} = G \right\} \right) \\ =& \sum_{G \in \mathscr{G}_{n,m}} P \left( \mathbb{G}_{n,p} = G \right) \\ =& \binom{\binom{n}{2}}{m} p^{m} \left( 1 - p \right)^{\binom{n}{2} - m} \end{align*} $$ Now, the conditional probability can be shown as $$ \begin{align*} P \left( \mathbb{G}_{n,p} = G_{0} | \mathbb{G}_{n,p} \in \mathscr{G}_{n,m} \right) =& {{ P \left( \mathbb{G}_{n,p} = G_{0} \land \mathbb{G}_{n,p} \in \mathscr{G}_{n,m} \right) } \over { P \left( \mathbb{G}_{n,p} \in \mathscr{G}_{n,m} \right) }} \\ =& {{ P \left( \mathbb{G}_{n,p} = G_{0} \right) } \over { P \left( \mathbb{G}_{n,p} \in \mathscr{G}_{n,m} \right) }} & \because (\star) \\ =& {{ p^{m} \left( 1 - p \right)^{\binom{n}{2} - m} } \over { \binom{\binom{n}{2}}{m} p^{m} \left( 1 - p \right)^{\binom{n}{2} - m} }} \\ =& \binom{\binom{n}{2}}{m}^{-1} \end{align*} $$ where $\land$ is the logical product.
[2]
Given $n$ nodes and each node having a connection probability of $p$, the degree of the node depends on whether it is connected to the remaining $(n-1)$ other nodes, hence follows the binomial distribution $B(n-1,p)$. Expressing it with a formula yields the following. $$ P \left( \deg v = k \right) = \binom{n-1}{k} p^{k} \left( 1 - p \right)^{n-1-k} $$
Poisson Distribution as a Limit of the Binomial Distribution: Let’s say $X_{n} \sim B(n,p)$.
If $\lambda \approx np$, then $$ X_{n} \overset{D}{\to} \text{Poi} (\lambda) $$
According to the lemma, the degree of nodes in a sufficiently large Gilbert network follows the Poisson distribution.
■
Visualization
Here are the sampled ER network and histogram of node degrees when $n = 50$, $p = 12\%$.
Code
Here is the code using Graphs and GraphRecipes packages of Julia.
cd(@__DIR__); pwd()
@time using Graphs
@time using Plots
@time using GraphRecipes
n = 50
G_np = erdos_renyi(n, 6/n, seed = 0)
plot_G_np = graphplot(G_np, title = "n = 50, p = 12%", curves=false, size = (300,300), node_weights = degree(G_np).^2,
node_shape = :rect, nodecolor = :black, nodestrokealpha = 0.5, edgecolor = :black)
png(plot_G_np, "plot_G_np.png")
histogram_G_np = histogram(degree(G_np), title = "Histogram of Degree",
color = :black, alpha = 0.8, label = :none, size = (300,300))
png(histogram_G_np, "histogram_G_np.png")