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.
- Graph Theory, Networks