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

zbMATH Open1498.05236arXiv2103.16708MaRDI QIDQ5043558FDOQ5043558

Authors: Caio Alves, Rodrigo Ribeiro 

Publication date: 6 October 2022

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.

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

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

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)

Cites Work

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

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)