12.2 Random graphs and their properties

Random graphs are mathematical models that generate networks with specific properties. They help us understand complex systems in the real world, from social networks to biological structures. These models provide insights into how network structures emerge and evolve.

This section explores two key random graph models: Erdős–Rényi and Gilbert. We'll dive into their characteristics, connectivity thresholds, and the emergence of giant components. We'll also look at graph coloring, cliques, and the small-world phenomenon in networks.

Random Graph Models

Erdős–Rényi and Gilbert Models

Top images from around the web for Erdős–Rényi and Gilbert Models

• 

  Survey on graph embeddings and their applications to machine learning problems on graphs [PeerJ] View original

  Is this image relevant?

• 

  What is the relationship between shortest path and density for undirected graph? - Mathematics ... View original

  Is this image relevant?

• 

  Survey on graph embeddings and their applications to machine learning problems on graphs [PeerJ] View original

  Is this image relevant?

• 

  What is the relationship between shortest path and density for undirected graph? - Mathematics ... View original

  Is this image relevant?

1 of 2

Top images from around the web for Erdős–Rényi and Gilbert Models

• 

  Survey on graph embeddings and their applications to machine learning problems on graphs [PeerJ] View original

  Is this image relevant?

• 

  What is the relationship between shortest path and density for undirected graph? - Mathematics ... View original

  Is this image relevant?

• 

  Survey on graph embeddings and their applications to machine learning problems on graphs [PeerJ] View original

  Is this image relevant?

• 

  What is the relationship between shortest path and density for undirected graph? - Mathematics ... View original

  Is this image relevant?

1 of 2

• Erdős–Rényi model generates random graphs with fixed number of vertices and edges
  • Denoted as G(n,m) where n is number of vertices and m is number of edges
  • Selects graph uniformly at random from all possible graphs with n vertices and m edges
  • Useful for studying average-case behavior of graph algorithms
• Gilbert model produces random graphs based on edge probability
  • Represented as G(n,p) where n is number of vertices and p is probability of edge existence
  • Each potential edge exists independently with probability p
  • Allows for varying edge density and connectivity in generated graphs
• Both models create graphs with similar statistical properties for large n
  • Expected number of edges in Gilbert model $E[|E|] = \binom{n}{2}p$
  • Probability distribution of edge count in Gilbert model follows binomial distribution

Connectivity Threshold

• Connectivity threshold determines probability at which random graph becomes connected
• For Erdős–Rényi model G(n,m), threshold occurs when m ≈ ½n log n
• In Gilbert model G(n,p), threshold happens when p ≈ log n / n
• Below threshold, graph likely consists of multiple disconnected components
• Above threshold, graph becomes increasingly likely to be fully connected
• Threshold behavior applies to various graph properties (clique formation, Hamiltonian cycles)

Graph Components and Properties

Giant Component and Connectivity

• Giant component emerges in random graphs as size and edge density increase
  • Largest connected subgraph containing a significant fraction of all vertices
  • Appears suddenly at a critical threshold in edge probability or density
  • In G(n,p) model, giant component emerges when np > 1
• Connectivity of random graphs influenced by edge probability
  • Low p results in many small, disconnected components
  • As p increases, components merge and giant component forms
  • Further increase in p leads to fully connected graph

Graph Coloring and Cliques

• Clique number represents size of largest complete subgraph in a graph
  • Increases with edge probability in random graphs
  • For G(n,p), expected clique number ≈ 2 log n / log(1/p) for large n
• Chromatic number indicates minimum number of colors needed to color graph vertices
  • No adjacent vertices share same color
  • In random graphs, chromatic number grows with edge density
  • For G(n,1/2), chromatic number ≈ n / (2 log n) with high probability

Graph Diameter

• Diameter measures maximum shortest path length between any two vertices
• In random graphs, diameter tends to be small relative to graph size
  • For G(n,p) with p > (1 + ε) log n / n, diameter ≈ log n / log(np) with high probability
• Diameter shrinks as edge probability increases
  • Dense random graphs have smaller diameters than sparse ones
• Studying diameter helps understand information spread and network efficiency

Network Phenomena

Small-World Phenomenon

• Small-world phenomenon describes short average path lengths in large networks
  • Popularized by "six degrees of separation" concept in social networks
  • Observed in various real-world networks (social, biological, technological)
• Random graphs often exhibit small-world properties
  • Average path length grows logarithmically with network size
  • In G(n,p) model, average path length ≈ log n / log(np) for p > log n / n
• Clustering coefficient measures local connectivity in networks
  • Random graphs typically have low clustering coefficients
  • Real-world networks often combine short path lengths with high clustering
• Watts-Strogatz model generates graphs with small-world properties
  • Interpolates between regular lattices and random graphs
  • Produces networks with high clustering and short average path lengths