Erdős-Réyni Random Graphs with Matlab

David Gleich, Purdue University
Last updated 2011-09-08

In this tutorial, we’ll look at generating Erdős-Réyni random random graphs in Matlab – something that will be rather easy – and then look at how the so-called giant component evolves in these graphs.

This tutorial is not meant to be mathematical, but rather, an empirical demonstration. For mathematical references see:

Other empirical demonstration of the same phenomenon:

Getting everything working

The following demo needs a few helper codes. If you just want to see what’s going on, feel free to skip this section. But if you want to run things, you’ll need the following codes.

Some of these files need some edits due to changes in graphviz and Matlab.

I’ve packaged all the updated Matlab files into a single zip file or github repository

This includes components.m, neato_layout.m (and support files), as well as all the matlab scripts here.

Installing graphviz

For OSX, you may also need to run the following command in Matlab to add neato to the path

setenv('PATH', [getenv('PATH') ':/usr/local/bin']);


  1. Generating an Erdős-Réyni graph in Matlab (matlab)
  2. Watching the evolution (matlab)
  3. 50 node ER graph evolution
  4. 100 node ER graph evolution
  5. 150 node ER graph evolution

The last few files were generated via the function er_evolution_figure (matlab code <./er_evolution_figure.m>)