Complexity Explorer Santa Fe Institute


random network

A graph where all the nodes, initially unconnected, are linked to other nodes at random with a set probability – usually denoted k. For example, a random network specified with k=0.5 gives all pairs of nodes in the network a 50% chance of being connected.  Among the many notable outcomes is that of an approximate Poisson degree distribution. With this distribution, the graph quickly forms a cohesive giant component as the average degree per node surpasses 1.    Also known as an Erdös-Rényi graph.


Topics
Graph Theory, Networks
Difficulty
1