File Exchange

image thumbnail

Erdos-Renyi Random Graph

version 1.0.0.0 (2.86 KB) by Pablo Blinder
Random graph generation.

19 Downloads

Updated 25 Jan 2005

No License

The Erdos-Renyi (Erdos and Renyi, 1959) is the first ever proposed algorithm for the formation of random graphs. It selects with equal probability pairs of nodes from the graph set of nodes and connects them with a predefined probability.

To rewire, with probability (p=0.01) a 100 vertex regular graph (vertex deg=4):
>>G=erdosRenyi(40,0.01,4);

To see display the graph issue:
>>plotGraphBasic(G,6,1);

6 is the marker size. 1 tells function to add labels (0 disables labbeling)

Comments and Ratings (15)

Qiwei Yu

I agree with Fabio and Enrico. The code generates WS networks with rewiring probability p.

Nice function, but it I agree with Fabio:
it will generate SMALL WORLD (Watts and Strogatz, WS) networks and NOT Erdos-Renyi random graphs.

Azy Rz

Hi
how can I determine the intersection of two edges as a point in Erdos-Renyi Random Graph?

WARNING!!!!
The title is completely misleading. It does not generate Erdos-Renyi Random Networks, but Watts-Strogatz Random Networks.
They are always single scale networks, but the degree distribution is not a Poisson.

Its Nice

Ramez hamid

Nice

Dieter

As mentioned before this does not properly make the matrix symmetric nor does it prevent nodes from being linked to themselves.

Symmetric: David is correct. This is a good fix.

Self linking: not sold on ziqiang zuo's fix. I added a line after the creation of A to read
A=sparse(A+eye(nv));
and one just before the creation of G reading:
A=sparse(A-eye(nv));
This works because the diagonal will not be added to the list of disconnected nodes.

Otherwise, everything looks good!

Dieter

Austin

nice one

A.Y.

Good and working implementation. Might have been better if plotting function supports curved edges.

David

Also the last line does not make the matrix symmetric. SInce you work on the upper triangle of the matrix, the easiest way to make the matrix symmetric is:
replace
A=A+fliplr((flipud(triu(A))));
with
A=A+A';

ziqiang zuo

it is a good routine, but in the processof reconncetion, it permites a vertex to connect itself. To avoid this, I change the code :
vToRec=nonAdj(ceil(rand*length(nonAdj))); to
vToRec=vDisToRec;
while vToRec==vDisToRec
vToRec=nonAdj(ceil(rand*length(nonAdj)));
end

LIU Jie

GOOD

roger lin

lizhen you

Updates

1.0.0.0

Major changes
i) stablish initial node degree for the regular lattice.
ii) Implements new data structure for storing graph.
iii) Bug fixed: missing vertex in display

MATLAB Release Compatibility
Created with R13
Compatible with any release
Platform Compatibility
Windows macOS Linux