Repository logo
 

Accelerated Information Dissemination on Networks with Local and Global Edges

Accepted version
Peer-reviewed

Type

Conference Object

Change log

Authors

Fischbeck, P 
Sauerwald, T 

Abstract

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.

Description

Keywords

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

0302-9743
1611-3349

Volume Title

13298 LNCS

Publisher

Springer International Publishing
Sponsorship
European Research Council (679660)