PerspectiveComputer Science

Networking—Smoothly Does It

See allHide authors and affiliations

Science  15 Jul 2011:
Vol. 333, Issue 6040, pp. 298-299
DOI: 10.1126/science.1208712

You are currently viewing the summary.

View Full Text

Log in to view the full text

Log in through your institution

Log in through your institution


A network, or graph, is a collection of nodes together with a collection of links joining some pairs of nodes. Networks are often used to describe and model many different types of structure in the real world—the spread of infectious diseases, for example, where nodes are people and links represent contacts that may spread the disease (1). It is often useful to model such structures by random networks, constructed by adding links to the nodes by some well-defined random procedure. Many different models of random networks have been studied. An important feature of many such models is that if there are only a few links, then the network consists of a large number of small, isolated components, but increasing the number of links beyond a critical density leads to a phase transition and the sudden emergence of one “giant” component. For disease modeling, the latter case indicates the possibility of a large epidemic. There was substantial interest when Achlioptas et al. (2) announced, based on numerical simulations, that a specific random network model seemed to exhibit a behavior at the phase transition that was different from all others known, with a much more abrupt or “explosive” behavior. On page 322 of this issue, Riordan and Warnke (3) show that the numerical simulations in (2) were misleading, and that the phase transition for this model is continuous, thus confirming the results of da Costa et al. (4).