An Erdös-Rényi graph $G(n,p)$ is another example of random graph. Unlike the Galton-Watson process, we consider a number $n$ of nodes that is fixed in advance. For any pair of distinct nodes $u$ and $v$, there is an edge between $u$ and $v$ with probability $p$, independently of the other possible edges. We focus here on undirected, loop-free graphs.
If you want to deepen your theoretical knowledge of Erdös-Rényi graphs, you can read Chapters 2, 3 and 4 from the book Epidemics and Rumours in Complex Networks (this is not mandatory).
In [ ]:
%pylab inline
# equivalent for
# import numpy as np
# import matplotlib.pyplot as plt
# %matplotlib inline
# # the two modules are also copied into the main namespace so you can skip np. / plt.
Propose a function that returns a realization of the Erdös-Rényi graph $G(n,p)$. The graph can be returned for example as a list of adjacency lists.
For example, if you have the following graph (it is just an example),
In [ ]:
import networkx as nx
G=nx.Graph()
G.add_edge(0,3)
G.add_edge(0,4)
G.add_edge(1,4)
G.add_edge(2,3)
G.add_edge(2,4)
nx.draw(G,with_labels=True)
the output should look like
(or more probably, if you use numpy arrays)
Remark: There is more than one way to do that. Remember that you want an undirected graph, so if $v$ is in the adjacency list of $u$, then $u$ must be in the adjacency list of $v$.
Answer:
Propose a function that takes as input the adjacency list of an undirected graph and returns the sizes of its connected components.
Answer:
We consider a finite population of $n$ individuals indexed by $\{1,\ldots,n\}$. The Reed-Frost epidemic propagates step-by-step in the population as follows. At step $0$, a single individual $u \in \{1,\ldots,n\}$ is infected and the others are susceptible. Then, any individual that is infected at some step is contagious during one step and is (definitely) removed at the next step. While it is contagious, this individual can infect any other susceptible individual independently at random with probability $p$. Hence, at the end of any step $t \ge 1$, the individuals that were infected at step $t-1$ are removed, the susceptible individuals of step $t-1$ that are infected by an infected node become infected, and the others remain susceptible.
The Reed-Frost epidemic is closely related to the Erdös-Rényi random graph. Indeed, if we consider a Reed-Frost epidemic that starts at some individual $u$ with a probability $p$ of infection, then the individuals that are infected at some step $t \ge 0$ correspond to the nodes that are at distance $t$ of $u$ in the Erdös-Rényi random graph $G(n,p)$.
For a fixed $n$ (say between 1000 and 10000), adapt the functions of Exercice 1 to compute and display the average number of nodes that are eventually infected as a function of $p$. Choose $n$, the range of $p$ (display critical values) and the number of trials wisely according to your machine capabilities.
At this point, can you make a parallel with the phase transition of the Galton-Watson process?
Answer:
For the same value of $n$, evaluate by simulation the probability that the contagion propagates to all $n$ individuals.
Answer:
We now consider heterogeneous $G(n_1,p_1,n_2,p_2,p)$ graphs as follows:
Propose a function that returns a realization of the heterogeneous Erdös-Rényi graph $G(n_1,p_1,n_2,p_2,p)$. The graph can be returned for example as a list of adjacency lists.
Answer:
In the case where $p_1 = p_2 = 0$, using the same approach as in Question 1.3, try to guess where the critical regime occurs. The goal is not to prove anything, but to provide an educated guess based on what you have experienced before.
Answer:
Verify your guess with simulations. You can reuse the functions of Questions 1.2 and 2.1.
Answer:
Generalize for arbitrary $p_1$, $p_2$.
Answer: