Special Seminar - Pu (Jane) Gao

Title: Random Networks: Enumeration, Generation, and Universality

Abstract:

Large networks appear in almost all branches of the sciences and in everyday life, and they are often modeled by random graphs. Among the various random graph models, random graphs with specified degrees are particularly important in modelling and analyzing real-world networks. I will discuss recent work in three important inter-related research directions for this random graph model: the enumeration of graphs with specified degrees, their generation, and universality. The enumeration results serve as fundamental probabilistic tools for analyzing these random graphs. The universality concerns relations between these random graphs and the classical Erdos-Renyi random graphs. The generation considers algorithms that sample such random graphs uniformly, or approximately uniformly. Efficient generators are useful to test properties and algorithms for real-world networks that are modeled by such random graphs. Since many real-world networks possess a power-law degree sequence, part of my talk will discuss random graphs with specified degrees that follow a power law.