Max Planck Institute for Dynamics and Self-Organization -- Department for Nonlinear Dynamics and Network Dynamics Group
Personal tools
Log in

Continuous Percolation with Discontinuities

here/Title
Date: 13.08.2012

The spread of an infectious disease in a human population can be modeled by an evolving network of human contacts: Individuals are represented by “nodes,” and infectious contacts by “links” between the nodes. The spread of the infection then becomes a process of adding links between nodes. One fundamental and important question that follows from this picture immediately is: Does the scale of the infection, or in the network-based language, the scale of the network connectivity, grow gradually or in a jumpy or discontinuous fashion as links are added?

The conventional wisdom among statistical physicists has it that, when links are added randomly, the growth rate of the connectivity scale jumps up suddenly at a threshold value for the number of links made, but the connectivity scale itself still increases continuously. Such a change is called “continuous percolation transition.” Excitement about new possibilities came, therefore, when Achlioptas and co-workers recently found strong numerical evidence for “explosive percolation” in network-growth models where links are not added randomly, but based on certain rules of competition among them. Whether the connectivity “explosion” is truly discontinuous or actually continuous has since been hotly debated. A majority of research results supports the discontinuous-percolation picture, but a mathematical proof supporting the minority view that the percolation is actually continuous seems to have settled the debate. In this paper, however, we show that the current understanding still needs to be expanded qualitatively: Network percolation can appear via a new, discontinuous route similar to a Devil’s staircase.

In fact, the new route we have revealed is arguably a richer one. In our model, connected parts merge not purely at random but preferentially when they are of similar size. This mimics the tendency of social groups to bond with similar others, a mechanism often found in social networks. As a result, the connectivity of the network in our model grows in a fashion like a Devil’s staircase: It displays an infinite hierarchy of discontinuous jumps after and close to the first jump.

We believe that our network-percolation model establishes a new paradigmatic class of percolation transitions in statistical physics and look forward to seeing the interest and new explorations that our work should generate.

 

Press release (in German)

Original publication: Continuous Percolation with Discontinuities, J. Nagler, T. Tiessen and H. W. Gutch, Phys. Rev. X. 2, 031009 (2012), DOI: 10.1103/PhysRevX.2.031009; Link to original publication