ABSTRACT
Random graph theory originated with seminal work by Erdös and Rényi in the 1950s. Until then, graph theory analyzed either speci¢c graph instances or deterministically de¢ned graph classes. Erdös and Rényi considered graph classes where the existence of edges between nodes was determined probabilistically. Ÿeir results were theoretically interesting and found applications in many practical domains [Barabási 02].
