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.

Speaker

Michela Castagnone

Research Area
Affiliation

University of New South Wales

Date

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

Venue

OMB 150 (Old Main Building 150)