Algorithms for generating uniformly random graphs

Speaker: 

Michela Castagnone

Affiliation: 

University of New South Wales

Date: 

Fri, 13/10/2017 - 12:00pm to 1:00pm

Venue: 

OMB 150 (Old Main Building 150)

Abstract: 

 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.

School Seminar Series: