Research Research Projects

Random graphs

There is a large body of research in random graphs and networks, and many models of random graphs, some more and some less relevant to real-world networks. 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 Lovasz and Szegedy 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 into 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.

Research Leads: 

Richard Kenyon