[Percolation par regroupements cumulatifs et transition de phase du processus de contact sur des graphes aléatoires]
Étant donné un graphe pondéré, nous introduisons une partition de l'ensemble de ses sommets vérifiant la propriété suivante : la distance entre deux parties est inférieure au minimum du poids total de chaque partie élevé à une certaine puissance. Cette partition s'obtient en regroupant successivement des ensembles de sommets et en cumulant leur poids. Pour plusieurs modèles de graphes pondérés aléatoires, nous montrons que l'existence d'une partie infinie présente une transition de phase.
Notre motivation pour l'étude de cette partition provient d'un lien avec le processus de contact et nous donnons une condition suffisante pour la survie du processus en termes d'existence d'une partie infinie. Nous appliquons cette condition pour prouver que le processus de contact sur des graphes géométriques et des triangulations de Delaunay aléatoires admet une transition de phase non triviale.
Given a weighted graph, we introduce a partition of its vertex set such that the distance between any two clusters is bounded from below by a power of the minimum weight of both clusters. This partition is obtained by recursively merging smaller clusters and cumulating their weights. For several classical random weighted graphs, we show that there exists a phase transition regarding the existence of an infinite cluster.
The motivation for introducing this partition arises from a connection with the contact process as it roughly describes the geometry of the sets where the process survives for a long time. We give a sufficient condition on a graph to ensure that the contact process has a non trivial phase transition in terms of the existence of an infinite cluster. As an application, we prove that the contact process admits a sub-critical phase on random geometric graphs and random Delaunay triangulations.
Keywords: Cumulative merging, interacting particle system, contact process, random graphs, percolation, multiscale analysis.
Mot clés : Regroupement cumulatif, systèmes de particules en interaction, processus de contact, graphes aléatoires, percolation, analyse multi-échelle.
@article{ASENS_2016__49_5_1189_0,
author = {M\'enard, Laurent and Singh, Arvind},
title = {Percolation by cumulative merging and phase transition for the contact process on random graphs},
journal = {Annales scientifiques de l'\'Ecole Normale Sup\'erieure},
pages = {1189--1238},
publisher = {Soci\'et\'e Math\'ematique de France. Tous droits r\'eserv\'es},
volume = {Ser. 4, 49},
number = {5},
year = {2016},
doi = {10.24033/asens.2307},
mrnumber = {3581814},
zbl = {1364.60137},
language = {en},
url = {http://www.numdam.org/articles/10.24033/asens.2307/}
}
TY - JOUR AU - Ménard, Laurent AU - Singh, Arvind TI - Percolation by cumulative merging and phase transition for the contact process on random graphs JO - Annales scientifiques de l'École Normale Supérieure PY - 2016 SP - 1189 EP - 1238 VL - 49 IS - 5 PB - Société Mathématique de France. Tous droits réservés UR - http://www.numdam.org/articles/10.24033/asens.2307/ DO - 10.24033/asens.2307 LA - en ID - ASENS_2016__49_5_1189_0 ER -
%0 Journal Article %A Ménard, Laurent %A Singh, Arvind %T Percolation by cumulative merging and phase transition for the contact process on random graphs %J Annales scientifiques de l'École Normale Supérieure %D 2016 %P 1189-1238 %V 49 %N 5 %I Société Mathématique de France. Tous droits réservés %U http://www.numdam.org/articles/10.24033/asens.2307/ %R 10.24033/asens.2307 %G en %F ASENS_2016__49_5_1189_0
Ménard, Laurent; Singh, Arvind. Percolation by cumulative merging and phase transition for the contact process on random graphs. Annales scientifiques de l'École Normale Supérieure, Série 4, Tome 49 (2016) no. 5, pp. 1189-1238. doi : 10.24033/asens.2307. http://www.numdam.org/articles/10.24033/asens.2307/
On the spread of viruses on the internet, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computer Machinery (2005), pp. 301-310 | MR | Zbl
Metastability for the Contact Process on the Preferential Attachment Graph (preprint arXiv:1502.05633 ) | MR
Contact processes on random graphs with power law degree distributions have critical value 0, Ann. Probab., Volume 37 (2009), pp. 2332-2356 (ISSN: 0091-1798) | DOI | MR | Zbl
Metastability for the contact process on the configuration model with infinite mean degree (preprint arXiv:1410.3061 ) | MR
, Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge Univ. Press, 2010, 210 pages (ISBN: 978-0-521-15016-3) | MR | Zbl
Contact interactions on a lattice, Ann. Probability, Volume 2 (1974), pp. 969-988 | DOI | MR | Zbl
, Classics in Mathematics, Springer, 2005, 496 pages (reprint of the 1985 original) (ISBN: 3-540-22617-6) | MR | Zbl
, Grundl. math. Wiss., 324, Springer, 1999, 332 pages (ISBN: 3-540-65995-1) | DOI | MR | Zbl
Exponential extinction time of the contact process on finite graphs (preprint arXiv:1203.2972 ) | MR
, Cambridge Tracts in Mathematics, 119, Cambridge Univ. Press, Cambridge, 1996, 238 pages (ISBN: 0-521-47504-X) | DOI | MR | Zbl
Metastable densities for the contact process on power law random graphs, Electron. J. Probab., Volume 18 (2013), pp. art. 103, 1-36 (ISSN: 1083-6489) | DOI | MR | Zbl
The contact process on trees, Ann. Probab., Volume 20 (1992), pp. 2089-2116 (ISSN: 0091-1798) | DOI | MR | Zbl
The branching random walk and contact process on Galton-Watson and nonhomogeneous trees, Ann. Probab., Volume 29 (2001), pp. 1563-1590 (ISSN: 0091-1798) | DOI | MR | Zbl
The existence of an intermediate phase for the contact process on trees, Ann. Probab., Volume 24 (1996), pp. 1711-1726 (ISSN: 0091-1798) | DOI | MR | Zbl
Estimates for distributions of the Voronoĭ polygon's geometric characteristics, Random Structures Algorithms, Volume 3 (1992), pp. 149-162 (ISSN: 1042-9832) | DOI | MR | Zbl
Cité par Sources :
