WOLFRAM|DEMONSTRATIONS PROJECT

Giant Component in Random Graph

​
nodes
100
edge probability × nodes
1
random seed
A random graph
G(n,p)
is a graph with
n
nodes where the probability of finding an edge between two nodes is
p
. When
n×p
tends to a constant
c>1
(as
n
grows), the graph will almost surely contain a "giant" connected component, absorbing a considerably large fraction of the nodes. This phenomenon is often mentioned as an example of emergence in random graph behavior.