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… 😉
You can try it yourself in our interactive Python shell:
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.
Where to Go From Here?
Enough theory, let’s get some practice!
To become successful in coding, you need to get out there and solve real problems for real people. That’s how you can become a six-figure earner easily. And that’s how you polish the skills you really need in practice. After all, what’s the use of learning theory that nobody ever needs?
Practice projects is how you sharpen your saw in coding!
Do you want to become a code master by focusing on practical code projects that actually earn you money and solve problems for people?
Then become a Python freelance developer! It’s the best way of approaching the task of improving your Python skills—even if you are a complete beginner.
Join my free webinar “How to Build Your High-Income Skill Python” and watch how I grew my coding business online and how you can, too—from the comfort of your own home.
While working as a researcher in distributed systems, Dr. Christian Mayer found his love for teaching computer science students.
To help students reach higher levels of Python success, he founded the programming education website Finxter.com. He’s author of the popular programming book Python One-Liners (NoStarch 2020), coauthor of the Coffee Break Python series of self-published books, computer science enthusiast, freelancer, and owner of one of the top 10 largest Python blogs worldwide.
His passions are writing, reading, and coding. But his greatest passion is to serve aspiring coders through Finxter and help them to boost their skills. You can join his free email academy here.