More Like this

1. A trust model for bootstrap percolation

   Bhansali, Rinni; Schaposnik, Laura P (March 2020, Proceedings)

   This paper is dedicated to the study of the interaction between dynamical systems and percolation models, with views towards the study of viral infections whose virus mutate with time. Recall that r-bootstrap percolation describes a deterministic process where vertices of a graph are infected once r neighbors of it are infected. We generalize this by introducing F(t)-bootstrap percolation, a time-dependent process where the number of neighbouring vertices which need to be infected for a disease to be transmitted is determined by a percolation function F(t) at each time t. After studying some of the basic properties of the model, we consider smallest percolating sets and construct a polynomial-timed algorithm to nd one smallest minimal percolating set on nite trees for certain F(t)-bootstrap percolation models. 

   more » « less
2. A trust model for spreading gossip in social networks: a multi-type bootstrap percolation model

   https://doi.org/10.1098/rspa.2019.0826  

   Bhansali, Rinni; Schaposnik, Laura P. (March 2020, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences)

   null (Ed.)

   We introduce here a multi-type bootstrap percolation model, which we call T -Bootstrap Percolation ( T -BP), and apply it to study information propagation in social networks. In this model, a social network is represented by a graph G whose vertices have different labels corresponding to the type of role the person plays in the network (e.g. a student, an educator etc.). Once an initial set of vertices of G is randomly selected to be carrying a gossip (e.g. to be infected), the gossip propagates to a new vertex provided it is transmitted by a minimum threshold of vertices with different labels. By considering random graphs, which have been shown to closely represent social networks, we study different properties of the T -BP model through numerical simulations, and describe its implications when applied to rumour spread, fake news and marketing strategies. 

   more » « less
3. Local limits of spatial inhomogeneous random graphs

   https://doi.org/10.1017/apr.2022.61  

   van der Hofstad, Remco; van der Hoorn, Pim; Maitra, Neeladri (September 2023, Advances in Applied Probability)

   Abstract Consider a set of n vertices, where each vertex has a location in $$\mathbb{R}^d$$ that is sampled uniformly from the unit cube in $$\mathbb{R}^d$$ , and a weight associated to it. Construct a random graph by placing edges independently for each vertex pair with a probability that is a function of the distance between the locations and the vertex weights. Under appropriate integrability assumptions on the edge probabilities that imply sparseness of the model, after appropriately blowing up the locations, we prove that the local limit of this random graph sequence is the (countably) infinite random graph on $$\mathbb{R}^d$$ with vertex locations given by a homogeneous Poisson point process, having weights which are independent and identically distributed copies of limiting vertex weights. Our set-up covers many sparse geometric random graph models from the literature, including geometric inhomogeneous random graphs (GIRGs), hyperbolic random graphs, continuum scale-free percolation, and weight-dependent random connection models. We prove that the limiting degree distribution is mixed Poisson and the typical degree sequence is uniformly integrable, and we obtain convergence results on various measures of clustering in our graphs as a consequence of local convergence. Finally, as a byproduct of our argument, we prove a doubly logarithmic lower bound on typical distances in this general setting. 

   more » « less
4. Nucleation and growth in two dimensions

   https://doi.org/10.1002/rsa.20888  

   Bollobás, Béla; Griffiths, Simon; Morris, Robert; T Rolla, Leonardo; Smith, Paul (October 2019, Random Structures & Algorithms)

   We consider a dynamical process on a graphG, in which vertices are infected (randomly) at a rate which depends on the number of their neighbors that are already infected. This model includes bootstrap percolation and first‐passage percolation as its extreme points. We give a precise description of the evolution of this process on the graph, significantly sharpening results of Dehghanpour and Schonmann. In particular, we determine the typical infection time up to a constant factor for almost all natural values of the parameters, and in a large range we obtain a stronger, sharp threshold. 

   more » « less
5. $$K_{r,s}$$ Graph Bootstrap Percolation

   https://doi.org/10.37236/8997  

   Bayraktar, Erhan; Chakraborty, Suman (January 2022, The Electronic Journal of Combinatorics)

   A graph $$G$$ percolates in the $$K_{r,s}$$-bootstrap process if we can add all missing edges of $$G$$ in some order such that each edge creates a new copy of $$K_{r,s}$$, where $$K_{r,s}$$ is the complete bipartite graph. We study $$K_{r,s}$$-bootstrap percolation on the Erdős-Rényi random graph, and determine the percolation threshold for balanced $$K_{r,s}$$ up to a logarithmic factor. This partially answers a question raised by Balogh, Bollobás, and Morris. We also establish a general lower bound of the percolation threshold for all $$K_{r,s}$$, with $$r\geq s \geq 3$$. 

   more » « less