Feature Column from the AMS

Complex Networks

3. Random networks

One approach to understanding how to recognize networks that have evolved ina structured fashion is to first understand how networks evolve at random.How might a "random graph" (or digraph) evolve or grow? The pioneersof the study of random graphs were the two Hungarian mathematicians Paul Erdős (1913-1996) and Alfred Rényi (1921 -1970).

Paul Erdős

Alfred Rényi

More recently, important contributions have been made by Bela Bollobás, Fan Chung, and Joel Spencer.

In the simplest case one starts with n isolated vertices of a graph, where n is fixed. Now add edges to this graph "at random." Exactly how should one interpret this phrase? One way to do so would be to assume that for all _nC₂ = n(n-1)/2 edges that are possible in a (simple) graph with n vertices, there is an equal chance that a particular edge will be independently added to the graph. One has a list of potential edges and for each of these one mentally tosses a coin which has a fixed probability of p for coming up heads. If the coin comes up heads for a particular edge one adds that edge to build up a subgraph. It turns out that the mathematics of random graphs has been actively pursued and many "facts" are known about the behavior of such graphs. (There are, in fact, several different but interesting approaches to developing a theory of random graphs.)

One unexpected finding from the study of random graphs is that certain phenomena associated with random graphs show behavior reminiscent of a phase transition, a sudden change from one physical state of matter to another. If the probability p used in adding an edge to a random graph is a function of the number of vertices n, a "phase transition" appears when p reaches a critical value. A simple example is the number of components (largest connected pieces) for a random graph. As p increases, suddenly there is a jump between having many components to having one large component. This graph-theoretical change parallels phase transitions in states of matter, like the jump from water to ice or water to steam. Physics is studded with dramatic ways that mathematics has been used to explain physical phenomena. This fact caused the Nobel Prize winning physicist Eugene Wigner to coin his famous remark concerning the "unreasonable effectiveness of mathematics in the physical sciences." Wigner was putting dramatically his sense of wonder that a subject which is widely viewed as "invented" by human ingenuity could so often provide exactly the right set of tools to understand issues in physical science.

As fascinating as the results about random graphs are, empirically observed results about complex networks show that additional ideas are needed. In particular, random graphs do not provide a way to deal with networks that grow with time.