Spread of infection over P.A. random graphs with edge insertion

MaRDI QIDQ5043558zbMATH OpenFDO

Authors Caio Alves, Rodrigo Ribeiro

Publication date 6 October 2022

Full work available at URL https://arxiv.org/abs/2103.16708, https://alea.impa.br/articles/v19/19-50.pdf

zbMATH Keywords

random graphspreferential attachmentbootstrap percolationregular varying functionKaramata's theory

Mathematics Subject Classification ID

Epidemiology (92D30) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Combinatorial probability (60C05) Other physical applications of random processes (60K40)

Abstract: In this work we investigate a bootstrap percolation process on random graphs generated by a random graph model which combines preferential attachment and edge insertion between previously existing vertices. The probabilities of adding either a new vertex or a new connection between previously added vertices are time dependent and given by a function $f$ called the edge-step function. We show that under integrability conditions over the edge-step function the graphs are highly susceptible to the spread of infections, which requires only $3$ steps to infect a positive fraction of the whole graph. To prove this result, we rely on a quantitative lower bound for the maximum degree that might be of independent interest.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 4000257 (Why is no real title available?)
• scientific article; zbMATH DE number 1875439 (Why is no real title available?)
• A phase transition in the evolution of bootstrap percolation processes on preferential attachment graphs
• Bootstrap Percolation on Infinite Trees and Non-Amenable Groups
• Bootstrap percolation in high dimensions
• Collective dynamics of `small-world' networks
• Complex graphs and networks
• Diameter of P.A. random graphs with edge-step functions
• Dynamic monopolies in tori.
• Emergence of Scaling in Random Networks
• Large communities in a scale-free network
• Metastability of the contact process on fast evolving scale-free networks
• On the behavior of some cellular automata related to bootstrap percolation
• On the spread of viruses on the Internet
• Preferential attachment random graphs with edge-step functions
• Quantum information theory
• Random graph dynamics
• The degree sequence of a scale-free random graph process
• The diameter of a scale-free random graph
• The sharp threshold for bootstrap percolation in all dimensions

Cited in

(7)

• Spread of information and diseases via random walks in sparse graphs
• Clustering and cliques in preferential attachment random graphs with edge insertion
• Permutation Tests for Infection Graphs
• A phase transition in the evolution of bootstrap percolation processes on preferential attachment graphs
• The infection time of graphs
• Infection in hypergraphs
• Containing viral spread on sparse random graphs: bounds, algorithms, and experiments

This page was built for publication: Spread of infection over P.A. random graphs with edge insertion

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