Equivalence of several generalized percolation models on networks

September 19, 2016

Abstract: 

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, k-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 k-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.

FIG. 5.

Activated clusters found using depth-first (left) and breadth-first (right) searching using the WTM with a threshold of τ occurring with probability p(1−p)τ−1 (independently of d ) and p=0.51 for a 9×9 lattice. The number at each node is its threshold. The circled nodes are the initial nodes chosen for each cluster. The bottom left node is chosen first, and its cluster traced out. The next cluster is initialized by the bottommost of the leftmost remaining nodes. Thick colored edges formed the final interaction that caused activation. Nonexistent edges failed to cause activation (but moved the node closer to its threshold). Dashed black edges were not tested because both nodes were already active when the edge was considered. The clusters remain the same for both search orders (but edges change).