📂Graph Theory

Erdős–Rényi Model

Buildup

Let us consider a simple graph with $n$ labeled vertices and $m$ edges, which has the property $\mathscr{G}_{n,m} \subset 2^{\binom{n}{2}}$.

A random graph with exactly $m$ links can be represented as follows $\mathbb{G}_{n, m} : \Omega \to \mathscr{G}_{n,m}$. The graph produced in this manner does not care who makes it or what probability it is made with, as long as it only has $n$ nodes and $m$ links. In other words, no probability distribution has been given yet. The easiest probability distribution we can think of here is the uniform distribution, where everyone has the same probability.

Since a simple graph must connect different nodes, among $n$ nodes, choosing $2$ of them can have $\binom{n}{2}$ links, and especially since it chooses $m$ of those links, it is $\displaystyle \left| \mathscr{G}_{n,m} \right| = \binom{\binom{n}{2}}{m}$. For all $G \in \mathscr{G}_{n,m}$ $$P \left( \mathbb{G}_{n,m} = G \right) = \binom{\binom{n}{2}}{m}^{-1}$$ means that all graphs with $n$ nodes and $m$ links have an equal chance of being selected.

Definition ^{1 2}

Given a probability space $( \Omega , \mathcal{F} , P)$, let us consider the property $\mathscr{G}_{n,m} \subset 2^{\binom{n}{2}}$.

A random graph having the following probability mass function is called the Erdős–Rényi Graph $\mathbb{G}_{n,m}$. $$P \left( \mathbb{G}_{n,m} = G \right) = \binom{\binom{n}{2}}{m}^{-1} \qquad , \forall G \in \mathscr{G}_{n,m}$$

Description

The Erdős-Rényi model is the representative network among random graphs, frequently found and used throughout the scientific community, and is also referred to as the ER model for short. Since all $G \in \mathscr{G}_{n,m}$ have the same probability of being selected, following a uniform distribution, it can also be called a Uniform Random Network.

The Gilbert model $\mathbb{G}_{n,p}$ constructs a network similar to the ER model $\mathbb{G}_{n,p}$ in a different way. Although algorithmically and mathematically the two models are different, essentially, if we do not focus on the differences between the two models, they are almost the same. Unfortunately, since the ER model is too well-known, there are many cases where the Gilbert model is also referred to as the ER model, which means the author either cannot or does not feel the need to distinguish between the differences, so let’s not get too hung up on that either.

The algorithm for sampling ER networks is as follows.

Algorithm

Input

Assuming the number of nodes $n \in \mathbb{N}$ and links $m \in \mathbb{N}$ are given.

---

Step 1. Initialization

Create a null graph $G$ with $n$ nodes, and make a list (sequence) of tuples $\left\{ l_{k} \right\}$. $$\left\{ l_{k} \right\} = \left\{ (i,j) \in [n]^{2} : i \ne j \right\} \qquad , [n] = \left\{ 1, \cdots , n \right\}$$ Shuffle the order of sequence $\left\{ l_{k} \right\}$ randomly.

---

Step 2. Sampling

for $k = 1 , \cdots , m$

　　For $l_{k} = (i,j)$, add link $ij$ to network $G$ as follows. $$G \gets G + ij$$

---

Output

Obtain a simple graph $G \in \mathscr{G}_{n,m}$ with $n$ nodes and $m$ links.

Visualization

Below is the sampled ER network and the histogram of its node degrees when $n = 50$, $m = 150$.

Code

Here is the code using Julia’s Graphs, GraphRecipes packages.

cd(@__DIR__); pwd()

@time using Graphs
@time using Plots
@time using GraphRecipes

n = 50
G_nm = erdos_renyi(n, 3n, seed = 0)
plot_G_nm = graphplot(G_nm, title = "n = 50, m = 150", curves=false, size = (300,300), node_weights = degree(G_nm).^2,
 node_shape = :rect, nodecolor = :black, nodestrokealpha = 0.5, edgecolor = :black)
png(plot_G_nm, "plot_G_nm.png")
histogram_G_nm = histogram(degree(G_nm), title = "Histogram of Degree",
 color = :black, alpha = 0.8, label = :none, size = (300,300))
png(histogram_G_nm, "histogram_G_nm.png")