Bootstrap percolation in inhomogeneous random graphs

被引:1
作者
Amini, Hamed [1 ]
Fountoulakis, Nikolaos [2 ]
Panagiotou, Konstantinos [3 ]
机构
[1] Univ Florida, Dept Ind & Syst Engn, 468 Weil Hall, Gainesville, FL 32611 USA
[2] Univ Birmingham, Sch Math, Birmingham B15 2TT, England
[3] Univ Munich, Math Inst, Theresienstr 39, D-80333 Munich, Germany
基金
英国工程与自然科学研究理事会;
关键词
Bootstrap percolation; random graphs; sharp threshold; THRESHOLD; TREES;
D O I
10.1017/apr.2023.21
中图分类号
O21 [概率论与数理统计]; C8 [统计学];
学科分类号
020208 ; 070103 ; 0714 ;
摘要
A bootstrap percolation process on a graph with n vertices is an 'infection' process evolving in rounds. Let $r \ge 2$ be fixed. Initially, there is a subset of infected vertices. In each subsequent round, every uninfected vertex that has at least r infected neighbors becomes infected as well and remains so forever.We consider this process in the case where the underlying graph is an inhomogeneous random graph whose kernel is of rank one. Assuming that initially every vertex is infected independently with probability $p \in (0,1]$ , we provide a law of large numbers for the size of the set of vertices that are infected by the end of the process. Moreover, we investigate the case $p = p(n) = o(1)$ , and we focus on the important case of inhomogeneous random graphs exhibiting a power-law degree distribution with exponent $\beta \in (2,3)$ . The first two authors have shown in this setting the existence of a critical $p_c =o(1)$ such that, with high probability, if $p =o(p_c)$ , then the process does not evolve at all, whereas if $p = \omega(p_c)$ , then the final set of infected vertices has size $\Omega(n)$ . In this work we determine the asymptotic fraction of vertices that will eventually be infected and show that it also satisfies a law of large numbers.
引用
收藏
页码:156 / 204
页数:49
相关论文
共 39 条
[1]   Bootstrap percolation: Visualizations and applications [J].
Adler, J ;
Lev, U .
BRAZILIAN JOURNAL OF PHYSICS, 2003, 33 (03) :641-644
[2]   Statistical mechanics of complex networks [J].
Albert, R ;
Barabási, AL .
REVIEWS OF MODERN PHYSICS, 2002, 74 (01) :47-97
[3]   Inhomogeneous Financial Networks and Contagious Links [J].
Amini, Hamed ;
Minca, Andreea .
OPERATIONS RESEARCH, 2016, 64 (05) :1109-1120
[4]   RESILIENCE TO CONTAGION IN FINANCIAL NETWORKS [J].
Amini, Hamed ;
Cont, Rama ;
Minca, Andreea .
MATHEMATICAL FINANCE, 2016, 26 (02) :329-365
[5]   Bootstrap Percolation in Power-Law Random Graphs [J].
Amini, Hamed ;
Fountoulakis, Nikolaos .
JOURNAL OF STATISTICAL PHYSICS, 2014, 155 (01) :72-92
[6]   Bootstrap Percolation in Living Neural Networks [J].
Amini, Hamed .
JOURNAL OF STATISTICAL PHYSICS, 2010, 141 (03) :459-475
[7]  
Amini H, 2010, ELECTRON J COMB, V17
[8]  
Athreya K. B., 1972, Branching processes
[9]   Bootstrap percolation on the hypercube [J].
Balogh, J ;
Bollobás, B .
PROBABILITY THEORY AND RELATED FIELDS, 2006, 134 (04) :624-648
[10]   Bootstrap percolation on the random regular graph [J].
Balogh, Jozsef ;
Pittel, Boris G. .
RANDOM STRUCTURES & ALGORITHMS, 2007, 30 (1-2) :257-286