Bootstrap percolation in power-law random graphs

DOI10.1007/S10955-014-0946-6MaRDI QIDQ2250981zbMATH OpenOpenAlexFDO

Authors Hamed Amini, Nikolaos Fountoulakis

Publication date 10 July 2014

Published in Journal of Statistical Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.1339

zbMATH Keywords

bootstrap percolationpower-law random graphsharp threshold

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Percolation (82B43)

Abstract: A bootstrap percolation process on a graph $G$ is an "infection" process which evolves in rounds. Initially, there is a subset of infected nodes and in each subsequent round each uninfected node which has at least $r$ infected neighbours becomes infected and remains so forever. The parameter $rgeq2$ is fixed. Such processes have been used as models for the spread of ideas or trends within a network of individuals. We analyse bootstrap percolation process in the case where the underlying graph is an inhomogeneous random graph, which exhibits a power-law degree distribution, and initially there are $a(n)$ randomly infected nodes. The main focus of this paper is the number of vertices that will have been infected by the end of the process. The main result of this work is that if the degree sequence of the random graph follows a power law with exponent $$, where $$, then a sublinear number of initially infected vertices is enough to spread the infection over a linear fraction of the nodes of the random graph, with high probability. More specifically, we determine explicitly a critical function $a_c(n)$ such that $a_c(n)=o(n)$ with the following property. Assuming that $n$ is the number of vertices of the underlying random graph, if $a(n)ll{a}_c(n)$, then the process does not evolve at all, with high probability as $n$ grows, whereas if $a(n)gg{a}_c(n)$, then there is a constant $eps>0$ such that, with high probability, the final set of infected vertices has size at least $epsn$. It turns out that when the maximum degree is $$, then $a_c(n)$ depends also on $r$. But when the maximum degree is $$, then $$.

Recommendations

• Discontinuous bootstrap percolation in power-law random graphs
• Bootstrap percolation in directed inhomogeneous random graphs
• A phase transition in the evolution of bootstrap percolation processes on preferential attachment graphs
• A phase transition regarding the evolution of bootstrap processes in inhomogeneous random graphs
• Bootstrap percolation on \(G(n,p)\) revisited

Cites work

• A note on the micromechanics of plastic yield of porous solids
• Bootstrap percolation and diffusion in random graphs with given vertex degrees
• Bootstrap percolation and kinetically constrained models on hyperbolic lattices
• Bootstrap percolation in living neural networks
• Bootstrap percolation in three dimensions
• Bootstrap percolation on homogeneous trees has 2 phase transitions
• Bootstrap Percolation on Infinite Trees and Non-Amenable Groups
• Bootstrap percolation on the hypercube
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Bootstrap percolation on the random regular graph
• Connected components in random graphs with given expected degree sequences
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Random Graphs
• Random graphs and complex networks. Volume 1
• Remarks on bootstrap percolation in metric networks
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Statistical mechanics of complex networks
• Stretched exponential fixation in stochastic Ising models at zero temperature
• The Average Distance in a Random Graph with Given Expected Degrees
• The phase transition in inhomogeneous random graphs
• The sharp threshold for bootstrap percolation in all dimensions
• The Spectra of Random Graphs with Given Expected Degrees
• The threshold regime of finite volume bootstrap percolation.

Cited in

(38)

• A phase transition regarding the evolution of bootstrap processes in inhomogeneous random graphs
• A sharp threshold for bootstrap percolation in a random hypergraph
• On the spread of influence in graphs
• Penalising transmission to hubs in scale-free spatial random graphs
• Accelerated information dissemination on networks with local and global edges
• Bootstrap percolation on the stochastic block model
• On the impact of treewidth in the computational complexity of freezing dynamics
• \(K_{r,s}\) graph bootstrap percolation
• Bootstrap percolation in directed inhomogeneous random graphs
• Bootstrap percolation and diffusion in random graphs with given vertex degrees
• Strong-majority bootstrap percolation on regular graphs with low dissemination threshold
• Think globally, act locally: on the optimal seeding for nonsubmodular influence maximization
• A central limit theorem for diffusion in sparse random graphs
• Complex contagions on configuration model graphs with a power-law degree distribution
• Bootstrap percolation in random k-uniform hypergraphs
• Bootstrap percolation on the random regular graph
• Normalization phenomena in asynchronous networks
• Remarks on bootstrap percolation in metric networks
• Bootstrap percolation on geometric inhomogeneous random graphs
• Bootstrap percolation on \(G(n,p)\) revisited
• A phase transition in the evolution of bootstrap percolation processes on preferential attachment graphs
• Bootstrap Percolation on Degenerate Graphs
• Spread of infection over P.A. random graphs with edge insertion
• A Dynamic Contagion Risk Model with Recovery Features
• Rumor spreading: A trigger for proliferation or fading away
• A trust model for spreading gossip in social networks: a multi-type bootstrap percolation model
• Recent advances in percolation theory and its applications
• An asynchronous linear-threshold innovation diffusion model
• BOOTSTRAP PERCOLATION ON RANDOM GEOMETRIC GRAPHS
• Discontinuous bootstrap percolation in power-law random graphs
• Strict Majority Bootstrap Percolation on Augmented Tori and Random Regular Graphs: Experimental Results
• Degree-ordered-percolation on uncorrelated networks
• Contagion risks and security investment in directed networks
• Bootstrap percolation in inhomogeneous random graphs
• Bootstrap percolation in random geometric graphs
• On the parameterized complexity of freezing dynamics
• Opinion diffusion in graphs: an adversarial approach
• Bootstrap percolation and the geometry of complex networks

This page was built for publication: Bootstrap percolation in power-law random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2250981)