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.