Erdős-Réyni Random Graphs with Matlab

David Gleich, Purdue University

http://www.cs.purdue.edu/homes/dgleich
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:

Wikipedia: Erdős–Rényi model
Amin Saberi’s MS&E 337 Lecture Notes: Emergence of the giant connected component

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.

components.m – A file from the MESHPART toolkit
neato_layout.m – A file based on drawGraph.m and draw_dot.m from AT&T GraphViz/Matlab interface and http://code.google.com/p/matlabtools/source/browse/trunk/graphics/drawGraph.m?r=121&spec=svn121
graph_to_dot.m – from AT&T GraphViz/Matlab interface
neato – the graph layout program from AT&T GraphViz

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

Erdős-Rényi matlab files
Erdős-Rényi github repo @ github

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

Installing graphviz

ubuntu just use apt-get

sudo apt-get install graphviz
OSX use homebrew to install graphviz

brew install 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']);

Windows Install graphviz from the precompiled binaries, see AT&T GraphViz

Examples

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