Graph View

Backlinks

The Library

Search

SearchSearch

Random Network

Sep 25, 2024, 5 min read

Erdos-Renyi Model

  • The Erdos-Renyi Model is a model for generating random graphs. We may more formally define Random Networks using two definitions

    • The model is where the network is chosen uniformly from a collection of networks with nodes and links
    • The model is here a network of nodes is generated with probability of connecting any two nodes

  • In the model, the number of links is given with a binomial distribution

  • The expected value of links is given as

Evaluation

  • An Erdos-Renyi model has a degree distribution best captured by a Binomial Distribution, but in practice, it is much more convenient to approximate this using a Poisson Distribution.

    • More specifically if is the probability that a node ha a link, then
    • This can be approximated as

  • In a large random network, the degree of most nodes is in the narrow vicinity of the average degree .

  • We can derive the following about the clustering coefficient of the Erdos-Renyi model

    • The clustering coefficient is determined by the link probability of the network.

    • For fixed the larger the network the smaller a node’s clustering coefficient. The decrease is .

    • The clustering coefficient of a node is independent of its degree.

    • These results follow because

      So that

Theorems

Theorem on Connectivity

  • A threshold function for the connectivity is

    • This implies that if is the link probability and if , then the network is connected.
    • The average degree is

  • A stronger result is as follows. Let . Thus

  • In the first case, it suffices to show that the probability of there being an isolated node goes to .

    • Let be a Bernoulli random variable defined as

    • The probability that an individual node is isolated is

      And we use the approximation

      Now let denote the number of isolated nodes. We have the expectation as

      If , we have that . We want to show this implies .

      Now we may show this using the variance and covariance of . We have that

    • We are able to simplify the second line by the fact that all are identically distributed. The third line follows from the variance of a Bernoulli distribution

      Continuing we have that

      We get the full variance of using the above and the expectation of a Bernoulli distribution

      Now for large , observe that (see its definition above). That is to say . Also, we have (see the definition of ).

      It follows

      Misplaced &\text{Var}[X] &= nq+n^2q^2 \frac{p}{1-p} \\ &\sim nq +n^2q^2p \\ &= nn^{-\lambda} + \lambda n\ln(n)n^{-2\lambda} \\ &\sim nn^{-\lambda} \\ &= E[X] \end{split}\end{equation}

      So that which denotes that as

      This implies that

      Thus rearranging terms gives us that

Theorem on Giant Components

  • A giant component is a component of a given random graph which contains a significant fraction of the entire graph’s vertices

  • A threshold function for the emergence of the giant component of the Erdos-Renyi Model is

    • If then all components are small
    • Otherwise, there is a giant component

  • The giant component emerges if the average degree is .

  • This means that as the random network grows, eventually a giant component emerges. When the giant component emerges, there is a significant jump in the size of the giant component.

  • In practice real networks are supercritical.

  • The Molloy-Reed Criterion is a criterion where randomly wired network has a giant component if

    • Most nodes must be connected to at least two other nodes

    • For a real network, this is given as

Others

  • For a random graph of arbitrary degree distribution, the size distribution of the clusters follows

    Given degree exponent , we have that

Links