One of the first and most famous models, the Erdös-Renyi random graph model, selects edges independently at random. While real-world networks do not typically resemble ER random graphs, because of its simplicity the ER model is widely studied as a model for phase transitions and other behavior in more sophisticated random graphs.

A beautiful result of Borgs, Chayes, Lovasz, Sos, Szegedy, and Vestergombi is the construction of a graph limit, or graphon, for dense random graphs. A graphon is an analytic object describing the limit of a sequence of random graphs as the number of vertices grows. The graphon formalism allows one to turn questions about large graphs into analysis (or even calculus) problems. Again, while real-world networks are rarely dense, the graphon formalism does shed light on the type of behavior one might expect; for example, it can be useful for detecting community structures in large graphs. In joint work with Radin, Ren, and Sadun, Kenyon showed how a large dense graph spontaneously develops a community structure (with two communities) under a very simple “external" constraint: increasing the density of a fixed subgraph.