High-Visibility Math: Sudden Phase Transitions in Random Networks
May 18, 2009
William Kolata
Articles on mathematics are relatively rare in Science magazine. Even more rare is a mathematical article highlighted by a "perspective," a short overview of the article and its significance written by an expert who is not an author. Such a pair can be found in the March 13, 2009, issue of Science: "Explosive Percolation in Random Networks," by Dimitris Achlioptas, Raissa D'Souza, and Joel Spencer, is accompanied by a perspective, "Emergence of Connectivity in Networks," by Tom Bohman.
Starting with a (large) set of n nodes, one well-known way to generate a random network is to select two nodes at random and add an edge between them. The networks in the resulting sequence are known as Erd�s�R�nyi random graphs. With the continued addition of random edges, the structural features of the network evolve; at some point, after m edges have been added, a structural feature can change abruptly. The structural feature examined by Achlioptas and co-authors is the size of the largest connected component, a measure of the clumping of the graph. When m = r n and the parameter r is slightly less than 1/2, the largest component is likely to be very small, with size C of the order log(n). But once r slightly exceeds 1/2, the largest component is likely to be a giant component of size C ~ (4r � 2)n. At r = 1/2, the fraction of nodes in the largest component (C/n) undergoes a continuous phase change. Often called second-order phase changes, such changes are characteristic of real-world phenomena like magnetization.
The authors ask: Are there processes for randomly adding edges that produce discontinuous phase changes---like the first-order phase change in entropy that occurs at 0� C as liquid water turns to ice? Their answer is yes. The process involves choosing, independently, at each step two random pairs of nodes and selecting an appropriate rule for discarding one of the two. Random selection of the pair to be discarded is ruled out--it is equivalent to the Erd�s�R�nyi process. But the authors show that selecting the edge that minimizes the product of the sizes of the components it connects, and discarding the other, breaking ties arbitrarily, results in a sudden explosion in the size of the giant component. A plot of the fraction of nodes in the giant component has a jump discontinuity in the neighborhood of r = 0.8.
Research in networks has blossomed, driven in part by developments in technology and science. The Internet, social networks, and nanotechnology are only some of the applications. This may account for the visibility accorded the mathematics of networks in high-profile general science journals like Science. The perspective by Tom Bohman, for example, references two other such articles: A. Barab�si and R. Albert, "Emergence of Scaling in Random Networks" (Science, Vol. 286, 1999, page 509) and D. Watts and S. Strogatz, "Collective Dynamics of Small-world Networks" (Nature, Vol. 393, 1998, pages 440�42). Another intriguing aspect of the article is its use of numerical evidence alongside formal mathematics. This approach is representative of a trend in the mathematical sciences with tremendous potential for generating conjectures for mathematics and insights in-to applications, and its impact is likely to be magnified by advances in computational science.
William Kolata is SIAM's Technical Director.
