How to Generate Random Graphs with Python?

5/5 - (1 vote)
How to Generate Random Graphs with Python?

There are different ways to create random graphs in Python. But first things first:

What is a Graph?

According to Merriam-Webster, a graph is “a collection of vertices and edges that join pairs of vertices According to Merriam-Webster, 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 n unconnected vertices.
  • Go over each possible edge e.
    • Include edge e with (independent) probability p into the graph.

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 e.

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)

# [0, 1, 2, 3, 4, 5]

# [(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))

[[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: start and 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!

Coders get paid six figures and more because they can solve problems more effectively using machine intelligence and automation.

To become more successful in coding, solve more real problems for real people. 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?

You build high-value coding skills by working on practical coding projects!

Do you want to stop learning with toy projects and focus on practical code projects that earn you money and solve real problems for people?

🚀 If your answer is YES!, consider becoming 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.

If you just want to learn about the freelancing opportunity, feel free to watch my free webinar “How to Build Your High-Income Skill Python” and learn how I grew my coding business online and how you can, too—from the comfort of your own home.

Join the free webinar now!

Leave a Comment