📂Graph Theory

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")

Generalization

• Chung-Lu Fitness Model