Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Jul 4, 2009 #1
    I also posted the following question on wikipedia:

    According to:


    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. jcsd
  3. Jul 4, 2009 #2


    User Avatar
    Science Advisor
    Homework Helper

    They're both Poisson-distributed.
  4. Jul 4, 2009 #3
    I've thought about it well going for my run and a bit after I got home. The following is correct:


    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.


    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


    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - Erdős–Rényi model distribution Date
I How to plot a scaled lognormal function Mar 12, 2018
I Fitting two models in sequence with parameters in common Jan 14, 2018
I Shaky model in least squares fit Jun 16, 2017
A Transcription from SQL to FOL (First Order Logic) Jun 3, 2017