Emergence of Connectivity in Networks

摘要

A network consists of a collection of nodes and a collection of connections that join pairs of nodes. In the language of mathematics, such an object is called a graph. Real-world objects such as the Internet (1), social networks (2), disease modeling (3), and bibliometric data harvesting are increasingly being modeled using graphs. When these objects do not have useful computer-based realizations, randomly generated graphs play a central role in their modeling (4). All of the models that have been rigorously analyzed thus far follow a common pattern in the emergence of the connectivity structure. On page 1453 of this issue, Achlioptas et al. (5) describe a simple, randomized network formation process that does not follow this pattern-it exhibits an extremely abrupt phase transition in its connectivity structure. Termed "explosive percolation" the transition is considerably more severe than the analogous phase transitions in related models, and may have important implications for network evolution in general.