# Erdős–Rényi model (G(n, p) vs G(n, M)) distribution

1. Jul 4, 2009

### John Creighto

I also posted the following question on wikipedia:
http://en.wikipedia.org/wiki/Talk:Erdős–Rényi_model

According to:

http://en.wikipedia.org/wiki/Watts_and_Strogatz_model#Rationale_for_the_model

And in the main article it says: "Properties of G(n, p)

As mentioned above, a graph in G(n, p) has on average \tbinom{n}{2} p edges. The distribution of the degree of any particular vertex is binomial:"

Am I right to assume that it is the G(n, M) model which has a poisson distribution or did I miss something or is there a mistake. As a general comment the main article seems to focus mainly on the G(n, M) model with little discussion on the G(n, p) model.

S243a (talk) 21:45, 4 July 2009 (UTC)John Creighton

2. Jul 4, 2009

### CRGreathouse

They're both Poisson-distributed.

3. Jul 4, 2009

### John Creighto

I've thought about it well going for my run and a bit after I got home. The following is correct:

http://en.wikipedia.org/wiki/Erdős–Rényi_model#Definition

However, if the number of nodes is large relative to the average order then the statistics tend towards Poisson statistics. I'll be more precise later. Anyway, in most networks of interest in sociology the number of nodes (people) can be very large (up to five billion) well, the average number of links can be very small (less then a few hundred). In the famous six degrees of seperation the number of nodes was chosen to be Thus if N = 300,000,000 (90% US pop.) and the average number of links was chosen to be 30.
http://en.wikipedia.org/wiki/Six_degrees_of_separation#Mathematics

http://en.wikipedia.org/wiki/Poisson_distribution#Related_distributions

So for a given vertex the probabilty of an endge being included is

p=<edges/nodes>/nodes~total edges/(total nodes)^2

and the total possible number of edges for a given node is
n=nodes

therefore
n*p=edges/nodes.

Therefore if there are 10 times as nodes as the average order then by the above rule of thumb a poison distribution is a suitable approximation.

Last edited: Jul 4, 2009