There are different ways to create random graphs in Python. But first things first:
What is a graph?
For example, this is a graph:
Every edge connects exactly two vertices.
What is a random graph?
Now, given that you have a finite number of vertices
n, there is also a finite number of graphs that can be generated from those vertices (although the number of graphs with
n vertices grows exponentially).
A random graph is just one of those graphs—which is generated by a random process.
More precisely, there’s a probability distribution over all possible graphs that describes how likely each graph is selected by the random process.
What’s the Erdős–Rényi random graph generation model?
In most cases, when referring to “random graphs”, people assume the underlying “Erdős–Rényi model” as a graph generator (it’s named after the mathematicians Paul Erdős and Alfréd Rényi). An important property of random graphs generated under this model is that, given a set of vertices and a number of edges, all possible graphs are generated with the same probability. So there is no bias towards a specific type of graph.
[Algorithm] Here’s how the basic Erdős–Rényi graph generator works:
- Start with
- Go over each possible edge
- Include edge
ewith (independent) probability
pinto the graph.
- Include edge
What is the runtime of the algorithm? Correct, as there are
n * n possible edges, the runtime is
O(n^2). All graphs have equal probability.
There are two parameters to the algorithm: the number of vertices
n and the number of edges
In Python, you can simply use the
networkx package to generate such a random graph:
from networkx.generators.random_graphs import erdos_renyi_graph n = 6 p = 0.5 g = erdos_renyi_graph(n, p) print(g.nodes) # [0, 1, 2, 3, 4, 5] print(g.edges) # [(0, 1), (0, 2), (0, 4), (1, 2), (1, 5), (3, 4), (4, 5)]
If we visualize this graph, it looks like the following:
Nothing special—just a random graph… 😉
The NumPy Alternative to Generate a Random Graph
While the above method is the standard Python way of creating a random graph, you are not forced to use the networkx library (which you may have to install with pip before being able to use it). As pointed out by Conner Davis, there’s a simple alternative using the NumPy library:
import numpy as np adjacency_matrix = np.random.randint(0,2,(n,n)) print(adjacency_matrix) ''' [[0 1 0 1 0 1] [0 1 0 1 0 0] [0 1 1 0 0 1] [1 1 0 0 1 1] [0 1 1 1 0 1] [1 0 0 1 0 0]] '''
Note that this behavior is non-deterministic: if you execute the same code on your machine, you won’t see the same result (in all likelihood).
The result looks different: the graph is an adjacency matrix now. The
randint method takes three arguments:
stop to limit the random integer value to a fixed interval (it can only take values 0 and 1) and the
shape of the result matrix. For more information about these terms, please check out the NumPy tutorial on this blog. It shows you everything you need to know to get started.