Equivalence of several generalized percolation models on networks

Miller, Joel C.

In recent years, many variants of percolation have been used to study network structure and the behavior of processes spreading on networks. These include bond percolation, site percolation, [Formula: see text]-core percolation, bootstrap percolation, the generalized epidemic process, and the Watts threshold model (WTM). We show that—except for bond percolation—each of these processes arises as a special case of the WTM, and bond percolation arises from a small modification. In fact “heterogeneous [Formula: see text]-core percolation,” a corresponding “heterogeneous bootstrap percolation” model, and the generalized epidemic process are completely equivalent to one another and the WTM. We further show that a natural generalization of the WTM in which individuals “transmit” or “send a message” to their neighbors with some probability less than 1 can be reformulated in terms of the WTM, and so this apparent generalization is in fact not more general. Finally, we show that in bond percolation, finding the set of nodes in the component containing a given node is equivalent to finding the set of nodes activated if that node is initially activated and the node thresholds are chosen from the appropriate distribution. A consequence of these results is that mathematical techniques developed for the WTM apply to these other models as well, and techniques that were developed for some particular case may in fact apply much more generally.