Repository logo

Accelerated Information Dissemination on Networks with Local and Global Edges

Accepted version


Conference Object

Change log


Fischbeck, P 
Sauerwald, T 


Bootstrap percolation is a classical model for the spread of information in a network. In the round-based version, nodes of an undirected graph become active once at least r neighbors were active in the previous round. We propose the perturbed percolation process: a superposition of two percolation processes on the same node set. One process acts on a local graph with activation threshold 1, the other acts on a global graph with threshold r – representing local and global edges, respectively. We consider grid-like local graphs and expanders as global graphs on n nodes. For the extreme case r= 1, all nodes are active after O(log n) rounds, while the process spreads only polynomially fast for the other extreme case r≥ n. For a range of suitable values of r, we prove that the process exhibits both phases of the above extremes: It starts with a polynomial growth and eventually transitions from at most cn to n active nodes, for some constant c∈ (0, 1 ), in O(log n) rounds. We observe this behavior also empirically, considering additional global-graph models.



Bootstrap percolation, Random graphs, Expanders, Rumor spreading

Journal Title

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Conference Name

Journal ISSN


Volume Title

13298 LNCS


Springer International Publishing
European Research Council (679660)