Equivalence of several generalized percolation models on networks

Joel C. Miller

Research output: Contribution to journalArticleResearchpeer-review

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.

Original languageEnglish
Article number032313
Number of pages7
JournalPhysical Review E - Covering Statistical, Nonlinear, Biological, and Soft Matter Physics
Volume94
Issue number3
DOIs
Publication statusPublished - 19 Sep 2016

Cite this

@article{838b3392f3fd479abb6d7bba3ffbbda9,
title = "Equivalence of several generalized percolation models on networks",
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.",
author = "Miller, {Joel C.}",
year = "2016",
month = "9",
day = "19",
doi = "10.1103/PhysRevE.94.032313",
language = "English",
volume = "94",
journal = "Physical Review E - Covering Statistical, Nonlinear, Biological, and Soft Matter Physics",
issn = "2470-0045",
publisher = "American Physical Society",
number = "3",

}

Equivalence of several generalized percolation models on networks. / Miller, Joel C.

In: Physical Review E - Covering Statistical, Nonlinear, Biological, and Soft Matter Physics, Vol. 94, No. 3, 032313, 19.09.2016.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Equivalence of several generalized percolation models on networks

AU - Miller, Joel C.

PY - 2016/9/19

Y1 - 2016/9/19

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84990238352&partnerID=8YFLogxK

U2 - 10.1103/PhysRevE.94.032313

DO - 10.1103/PhysRevE.94.032313

M3 - Article

VL - 94

JO - Physical Review E - Covering Statistical, Nonlinear, Biological, and Soft Matter Physics

JF - Physical Review E - Covering Statistical, Nonlinear, Biological, and Soft Matter Physics

SN - 2470-0045

IS - 3

M1 - 032313

ER -