Generating graphs randomly

Understand

Graphs are used in many disciplines to model the relationships that exist between objects in a complex discrete system.

• Researchers may wish to compare a network of interest to a "typical" graph from a family (or ensemble) of graphs which are similar in some way.
• One way to do this is to take a sample of several random graphs from the family, to gather information about what is "typical".
• Hence there is a need for algorithms which can generate graphs uniformly (or approximately uniformly) at random from the given family.