The ability to generate uniformly random graphs is useful in many real world applications. For example, we may model a given social network as a graph, and determine its key properties. In order to decide whether these properties are somehow "typical'' of similar graphs, or arise particularly from the function of this social network, we may test uniformly generated graphs from a family of "similar'' graphs, such as graphs with the same degree sequence as the social network.
This presentation will compare different methods of generating uniformly random graphs, with a focus on the algorithms of McKay and Wormald (1990) and Gao and Wormald (2015). Other approaches, such as Markov chain algorithms, are also discussed.
University of New South Wales
Fri, 13/10/2017 - 12:00pm to 1:00pm
OMB 150 (Old Main Building 150)