Description

The simplest and historically the first approach to random graphs was developed by Erdös and Rényi in the late 1950s. In a series of papers they considered graphs on n vertices whose edges are generated by independently flipping a (biased) coin with success probability p (or by selecting a graph uniformly at random from the set of all graphs on n vertices having a fixed number of edges). The Erdös-Rényi random graph (ERRG) has many interesting properties, the most famous of which is the phenomenon of emergence of a giant component. Roughly speaking, if np<1, all connected components of a typical ERRG are small (in fact, of order log(n)), whereas a typical ERRG with np>1 contains a single connected component containing a positive fraction of all vertices (ie., of order n) whereas all remaining components are still logarithmically small.

In the late 1990s it has been realised that the Erdös-Rényi approach is not adequate for modelling properties of various networks, many of which are of the so-called small-world type. The latter usually means that a typical distance between two nodes in such networks is small: eg., it is claimed that by following the links connecting the webpages, one can explore most of the Internet in just 19 clicks on average (an analogous statement about human network connectivity is that any two human beings are separated by "six handshakes" on average, see this Wiki page). Similar properties have been discovered for many other networks, including Hollywood actors, scientific citations and chemical reactions in our bodies.

With additional motivation, one could explore various dynamical problems on random graphs (eg., rumour or infection spreading), or numerically simulate particular subgraphs of a random graph (such as Minimal Spanning Trees).

Prerequisites

Resources

There is plenty of information on small-world networks available online (just Google or Wiki!). The pioneering papers on small-world networks are:

• D. Watts and S. Strogatz, Collective dynamics of small-world networks, Nature 363:202-204, 1998;
• A.-L. Barabási and R. Albert, Emergence of scaling in random networks, Science 286:509-512, 1999.

For a classical approach (with or without dynamical aspects) you might wish to consult:

• Introduction to Probability Models by SM Ross (look for random graph in the index),
• Random graph dynamics by R.Durrett (also available online when accessed from the Durham Network),
• Random Graphs by Janson, Luczak & Rucinski (a more advanced book).

Get in touch, if you would be interested in doing some simulations and/or have any questions!