14.1 Erdős-Rényi random graph model

Random graphs are mathematical models that simulate complex networks. The Erdős-Rényi model, introduced in 1959, is a foundational approach for generating these graphs with specific properties.

This model comes in two variants: G(n,p) and G(n,M). Both create graphs with n vertices, but differ in how edges are assigned. Understanding these models is crucial for analyzing real-world networks in various fields.

Erdős-Rényi Random Graph Model Fundamentals

Erdős-Rényi random graph model

• Erdős-Rényi model generates random graphs with specific properties
• Named after mathematicians Paul Erdős and Alfréd Rényi who introduced it in 1959
• Two main variants G(n,p) and G(n,M) differ in how edges are assigned
• G(n,p) model uses n vertices and probability p for edge formation
• G(n,M) model uses n vertices and fixed number M of edges
• Widely used in network science to study complex systems (social networks, biological networks)

Generation of random graphs

• G(n,p) model generation process creates graphs with varying edge counts:
  1. Begin with n isolated vertices
  2. Examine each vertex pair
  3. Add edge between pair with probability p
  4. Repeat for all $\binom{n}{2}$ possible edges
• G(n,M) model generation process ensures exact edge count:
  1. Start with n isolated vertices
  2. Randomly choose M pairs of vertices
  3. Connect each selected pair with an edge
• G(n,p) uses probabilistic approach while G(n,M) guarantees fixed edge count
• Both models produce graphs with uniform distribution within their constraints

Probability of graph structures

• Probability of specific graph G with m edges in G(n,p) model calculated as $P(G) = p^m (1-p)^{\binom{n}{2} - m}$
• Expected number of edges in G(n,p) model given by $E(|E|) = \binom{n}{2}p$
• Connectivity probability increases with n and p, sharp threshold at $p = \frac{\ln n}{n}$
• Giant component emerges when $np > 1$, crucial for network connectivity
• k-clique formation probability: $\binom{n}{k}p^{\binom{k}{2}}$, important for community detection
• Threshold phenomena occur in both models as n approaches infinity

G(n,p) vs G(n,M) model properties

• Both produce n-vertex random graphs with uniform distribution
• G(n,p) allows variable edge count, G(n,M) fixes edge count at M
• G(n,M) equivalent to G(n,p) conditioned on exactly M edges
• Similar asymptotic behavior as n approaches infinity
• G(n,p) often easier for theoretical analysis
• G(n,M) useful when specific edge count required (sparse graph analysis)
• Computational trade-offs: G(n,p) faster for large n, G(n,M) more controlled