Erdos-Reyni Random Graphs with Matlab

David Gleich
Last Edited: 16 January, 2006.


Giant Component

In this tutorial/record, we'll look at generating Erdos-Reyni random graphs in Matlab, and see the giant component in the graph.

The first step is to pick the number of vertices in the graph and the probability of an edge between two vertices.

>> n = 150; >> p = 0.01;

With these two parameters, we can instantiate the graph. The variable G is the adjacency matrix for the graph. The second operation symmetrizes the adjacency matrix by discarding half of it.

>> G = rand(n,n) < p; >> G = triu(G,1); >> G = G + G';

From the theory of Erdos-Reyni graphs, we know that a giant connected component should emerge when p > 1/(n-1).

>> thres_giant = 1/(n-1) thres_giant = 0.0067

Because p = 0.01 > 0.0067, we expect our graph to have such a giant component. Using the Matlab interface to the AT&T Graphvis program neato, we can generate a layout for this graph and visualize it using the matlab gplot function. That way, we can see if it really does have a giant component.

>> [x y] = draw_dot(G); >> gplot(G, [x' y'], '.-');

In the center of the picture, we see the large connected component of the graph.


Now that we know how to generate Erdos-Reyni random graphs, let's look at how they evolve in p -- the probability of an edge between two nodes. Effectively, as we keep adding edges randomly to a graph, what happens?

From theory, we expect to see a giant component with approximately log(n) vertices emerge when p is near 1/(n-1). Then, we expect the graph to become completely connected when p is close to log(n)/n.

First, we need to setup our graph as a function of p. The new anonymous functions in Matlab 7 make this easy.

>> n = 200; >> A = rand(n,n); >> A = triu(A,1); >> A = A + A'; >> G = @(p) A < p;

Now, let's compute the thresholds and look at the graph near the thresholds.

>> thres_conn = log(n)/n thres_conn = 0.0265 >> thres_giant = 1/(n-1) thres_giant = 0.0050

For each graph, we generate coordinates using the AT&T Graphvis tool, and then plot using Matlab's gplot.

>> [x y] = draw_dot(G(thres_giant)); >> gplot(G(thres_giant), [x' y'], '.-')

>> [x y] = draw_dot(G(thres_conn)); >> gplot(G(thres_conn), [x' y'], '.-')

While the second picture is definitely connected, the former doesn't appear to have a giant component. Remember that we aren't guaranteed to find a giant component at this p, but it has to happen soon. In this case, notice that it is very likely that the two larger components will merge together very soon.

Now, let's animate the result. To do this, let's generate a layout at the geometric mean of the connected threshold and the giant component threshold. (I'm not sure why that probability is a good one to use for drawing the graph, but it happens to work well in practice.)

>> [x y] = draw_dot(G(sqrt(thres_conn*thres_giant)));

The following script animation script depends on the largest_component function which is not standard to Matlab and uses the components function from the meshpart toolkit.

t1 = linspace(0, thres_giant, 50); t2 = linspace(thres_giant, thres_conn, 100); t = [t1 ones(1,40)*thres_giant t2]; for (tt = t) % plot the graph gplot(G(tt), [x' y'], 'b.-'); hold on; % plot the largest component of the graph [Glc p] = largest_component(G(tt)); gplot(Glc, [x(p)' y(p)'], 'r'); hold off; set(gca, 'YTick', []); set(gca, 'XTick', []); set(gcf, 'Color', [1 1 1]); title(sprintf('p = %d', tt)); pause(0.15); end;

The animation pauses briefly at the component where a giant threshold emerges.

I've provided three more examples of these plots for