Growth dominates choice in network percolation

Phys Rev E Stat Nonlin Soft Matter Phys. 2013 Sep;88(3):032141. doi: 10.1103/PhysRevE.88.032141. Epub 2013 Sep 30.

Abstract

The onset of large-scale connectivity in a network (i.e., percolation) often has a major impact on the function of the system. Traditionally, graph percolation is analyzed by adding edges to a fixed set of initially isolated nodes. Several years ago, it was shown that adding nodes as well as edges to the graph can yield an infinite order transition, which is much smoother than the traditional second-order transition. More recently, it was shown that adding edges via a competitive process to a fixed set of initially isolated nodes can lead to a delayed, extremely abrupt percolation transition with a significant jump in large but finite systems. Here we analyze a process that combines both node arrival and edge competition. If started from a small collection of seed nodes, we show that the impact of node arrival dominates: although we can significantly delay percolation, the transition is of infinite order. Thus, node arrival can mitigate the trade-off between delay and abruptness that is characteristic of explosive percolation transitions. This realization may inspire new design rules where network growth can temper the effects of delay, creating opportunities for network intervention and control.

Publication types

  • Research Support, Non-U.S. Gov't
  • Research Support, U.S. Gov't, Non-P.H.S.