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 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
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
produces random graphs based on
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 and connectivity in generated graphs
Both models create graphs with similar for large n
Expected number of edges in Gilbert model E[∣E∣]=(2n)p
Probability distribution of edge count in Gilbert model follows binomial distribution
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
applies to various graph properties (clique formation, )
Graph Components and Properties
Giant Component and Connectivity
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
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
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
grows logarithmically with network size
In G(n,p) model, average path length ≈ log n / log(np) for p > log n / n
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