Bootstrap Percolation on Random Geometric Graphs

Bootstrap percolation has been used effectively to model phenomena as diverse as emergence of magnetism in materials, spread of infection, diffusion of software viruses in computer networks, adoption of new technologies, and emergence of collective action and cultural fads in human societies. It is defined on an (arbitrary) network of interacting agents whose state is determined by the state of their neighbors according to a threshold rule. In a typical setting, bootstrap percolation starts by random and independent "activation" of nodes with a fixed probability p, followed by a deterministic process for additional activations based on the density of active nodes in each neighborhood. Here, we study bootstrap percolation on random geometric graphs in the regime when the latter is (almost surely) connected. Random geometric graphs are appropriate models in settings where the neighborhood structure of each node is determined by geographical distance, as in wireless ad hoc and sensor networks as well as in contagion. We derive tight bounds on the critical threshold, p_c, such that for all p > p_c full percolation takes place. We conclude with simulations that compare numerical thresholds with those obtained analytically.