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

[John Creighto]

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

According to:

They do not account for the formation of hubs. Formally, the degree distribution of ER graphs converges to a Poisson distribution, rather than a power law observed in most real-world, scale-free networks.

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

 

[CRGreathouse]

They're both Poisson-distributed.

 

[John Creighto]

They're both Poisson-distributed.

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

In the G(n, p) model, a graph is thought to be constructed by connecting nodes randomly. Each edge is included in the graph with probability p, with the presence or absence of any two distinct edges in the graph being independent. Equivalently, all graphs with n nodes and M edges have equal probability of p^M (1-p)^{{n \choose 2}-M}. The parameter p in this model can be thought of as a weighting function; as p increases from 0 to 1, the model becomes more and more likely to include graphs with more edges and less and less likely to include graphs with fewer edges. In particular, the case p = 0.5 corresponds to the case where all 2^\tbinom{n}{2} graphs on n vertices are chosen with equal probability.

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 separation 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

The Poisson distribution can be derived as a limiting case to the binomial distribution as the number of trials goes to infinity and the expected number of successes remains fixed. Therefore it can be used as an approximation of the binomial distribution if n is sufficiently large and p is sufficiently small. There is a rule of thumb stating that the Poisson distribution is a good approximation of the binomial distribution if n is at least 20 and p is smaller than or equal to 0.05, and an excellent approximation if n ≥ 100 and np ≤ 10.[1]

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.