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

    CRGreathouse

    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:

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




Similar Discussions: Erdős–Rényi model (G(n, p) vs G(n, M)) distribution
Loading...