Prof. Götz Pfeiffer

School of Mathematics, Statistics and Applied Mathematics

NUI Galway

A random graph is a mathematical model of a family of networks, where certain parameters (like the number of nodes and edges) have fixed values, but other aspects (like the actual edges) are randomly assigned. The simplest example of a random graph is in fact the network $G(n,m)$ with fixed numbers $n$ of nodes and $m$ of edges, placed randomly between the vertices. Although a random graph is not a specific object, many of its properties can be described precisely, in the form of expected values, or probability distributions.

Let us denote by $G(n, m)$ a network with $n$ nodes and $m$ chosen
edges, chosen uniformly at random (out of the possible
$\binom{n}{2}$). Equivalently, one can choose uniformly at random
one network in the **set** $G(n, m)$ of **all** networks on a given set
of $n$ nodes with **exactly** $m$ edges.

**Definition (ER Model $A$: Uniform Random Graphs).**
Let $n \geq 1$, let $N = \binom{n}{2}$ and let $0 \leq m \leq N$.
The model $G(n, m)$ consists of the ensemble of graphs $G$
with $n$ nodes $X = \{1, 2, \dots, n\}$, and $m$ randomly selected
edges, chosen uniformly from the $N$ possible edges.

One could think of $G(n, m)$ as a probability distribution $P \colon G(n, m) \to \mathbb{R}$, that assigns to each network $G \in G(n, m)$ the same probability $$ P(G) = \binom{N}{m}^{-1}, $$ where $N = \binom{n}{2}$.

For example ...

In order to make some random graphs, we first need to import the standard libraries ...

In [ ]:

```
import numpy as np
import pandas as pd
import networkx as nx
import matplotlib.pyplot as plt
```

... and the `random`

module, for a function `choice`

that selects a random element from a list.

In [ ]:

```
import random
```

Picking edges at random involves picking several ($2$ to be precise)
nodes from the list of nodes of a graph, avoiding repetition. A simple
algorithm for selection without repetition can be based on the following
function `pick`

, which works on a set `elements`

and a subset `chosen`

of already chosen elements, as follows:

- pick a random element
`x`

from the set`elements`

- if
`x`

is in the subset`chosen`

go back to step 1, else return`x`

.

In [ ]:

```
def pick(elements, chosen = []):
while True:
x = random.choice(elements)
if x not in chosen:
return x
```

**Note.** This algorithm (and its implementation here) has no explict termination condition.
Hence, under unfortunate circumstances, it may run for a very long time, or indeed forever ...

In [ ]:

```
lll = [2, 3, 5, 7, 11, 13, 17, 19]
pick(lll, [2,3,5,7,11,13])
```

To select $l$ random elements, simply `pick`

$l$ times, while
keeping track of already selected elements in a list `chosen`

.

In [ ]:

```
def pick_elements(elements, count):
chosen = []
for i in range(count):
chosen.append(pick(elements, chosen))
return chosen
```

In [ ]:

```
lll = [2, 3, 5, 7, 11, 13, 17, 19]
pick_elements(lll, 3)
```

**Note.** Suppose the vertex set $X$ has $n$ elements and that $k$ elements
$$
(x_0, x_1, \dots, x_{k-1})
$$
have already been chosen.
Then the next element $x_k$ is chosen with probability $\frac1{n-k}$ (from
the $n-k$ remaining elements at this stage:

Clearly, $x_0$ is chosen with probability $\frac1n$ from the $n$ elements. Next, in a first draw $x_1$ is chosen with probability $\frac1n$. With the same probability $\frac1n$, this first draw produces element $x_0$ again, in which case a second draw has to be carried out, where $x_1$ has another chance of $\frac1n$ to be drawn. And $x_0$ too, calling for a third draw, and so on. In total, $x_1$'s chances of being drawn are $$ P(x_1) = \frac1n + \frac1{n^2} + \frac1{n^3} + \dotsm = \frac1n \sum_{l \geq 0} \bigl(\frac1n\bigr)^l = \frac1n \frac1{1 - \frac1n} = \frac1{n-1}. $$

Similarly, $x_k$'s chances of being drawn are $$ P(x_k) = \frac1n + \frac{k}{n^2} + \frac{k^2}{n^3} + \dotsm = \frac1n \sum_{l \geq 0} \bigl(\frac{k}{n}\bigr)^l = \frac1n \frac1{1 - \frac{k}{n}} = \frac1{n-k}. $$

To pick a random edge means to pick $2$ elements from the node set of $G$. Again, one can use a list of already chosen edges to avoid repetition.

In [ ]:

```
def pick_edge(G, chosen):
while True:
edge = pick_elements(list(G.nodes()), 2)
edge.sort()
if edge not in chosen:
return edge
```

In [ ]:

```
G = nx.Graph()
G.add_nodes_from(range(16))
```

In [ ]:

```
list(G.nodes)
```

In [ ]:

```
pick_edge(G, [[11,14]])
```

To pick $m$ edges, without repetition, simply apply `pick_edge`

$m$ times.

In [ ]:

```
def pick_edges(G, m):
chosen = []
for i in range(m):
chosen.append(pick_edge(G, chosen))
return chosen
```

Now we have all the building blocks for a function `random_graph_A`

that
takes the order $n$ and the size $m$ of a random ER graph of type A
as arguments, and constructs such a graph.

In [ ]:

```
def random_graph_A(n, m):
"""construct a random type A graph
with n nodes and m = links"""
G = nx.Graph()
G.add_nodes_from(range(n))
G.add_edges_from(pick_edges(G, m))
return G
```

Now we can construct and draw a random graph on $16$ vertices with $15$ edges.

In [ ]:

```
G = random_graph_A(16, 15)
nx.draw(G, with_labels = True, node_color = 'y')
```

The `networkx`

version of this random graph constructor is called `gnm_random_graph`

and should produce the same random graphs with the same probability.

In [ ]:

```
G = nx.gnm_random_graph(16, 15)
nx.draw(G, with_labels = True, node_color = 'lightblue')
```

In [ ]:

```
list(G.nodes())
```

In [ ]:

```
%%html
<script src="https://d3js.org/d3.v3.min.js"></script>
```

In [ ]:

```
%%html
<div id="random">
<div id="count"></div>
<link rel="stylesheet" href="random.css">
<script src="random.js"></script>
</div>
```

**Definition (ER Model $B$: Binomial Random Graphs).**
Let $n \geq 1$, let $N = \binom{n}{2}$ and let $0 \leq p \leq 1$.
The model $G(n, p)$ consists of the ensemble of graphs $G$
with $n$ nodes $X = \{1, 2, \dots, n\}$, and each of the $N$
possible edges chosen with probability $p$.

The probability $P_G$ of a particular graph $G = (X, E)$ with $X = \{1, 2, \dots, n\}$ and $m = |E|$ edges in the $G(n, p)$ model is $$ P_G = p^m(1-p)^{N-m}. $$

For example ...

Such a random graph is easy to generate programmatically, using python's basic random number generator
`random.random()`

which returns a random number in the (half-open) interval $[0, 1)$,
every time it is called. If this number is less then $p$, we include the edge, if not we don't.

In [ ]:

```
def random_graph_B(n, p):
"""construct a random type B graph
with n nodes and edge probability p"""
G = nx.Graph()
G.add_nodes_from(range(n))
for a in range(n):
for b in range(a):
if random.random() < p:
G.add_edge(a, b)
return G
```

In [ ]:

```
15/120
```

In [ ]:

```
G = random_graph_B(16, 0.125)
nx.draw(G, with_labels=True, node_color = 'y')
```

In [ ]:

```
G.number_of_nodes(), G.number_of_edges()
```

In [ ]:

```
G = nx.gnp_random_graph(16,0.125)
nx.draw(G, with_labels=True, node_color='lightblue')
```

In [ ]:

```
G.number_of_nodes(), G.number_of_edges()
```

In [ ]:

```
```