We study a simple model of how social behaviors, like trends and opinions, propagate in networks where individuals adopt the trend when they are informed by threshold T neighbors who are adopters. Using a dynamic message-passing algorithm, we develop a tractable and computationally efficient method that provides complete time evolution of each individual's probability of adopting the trend or of the frequency of adopters and nonadopters in any arbitrary networks. We validate the method by comparing it with Monte Carlo-based agent simulation in real and synthetic networks and provide an exact analytic scheme for large random networks, where simulation results match well. Our approach is general enough to incorporate non-Markovian processes and to include heterogeneous thresholds and thus can be applied to explore rich sets of complex heterogeneous agent-based models.
By deleting each edge with probability @math independently, we can ask whether the resulting diluted network in the thermodynamic limit contains an extensive @math -core in the ensemble of similarly prepared networks. Interestingly for @math , the emergence of a @math -core in random networks is a first-order (discontinuous) phase transition in the sense that when it first appears it covers a finite fraction of the network @cite_13 . An early work on @math -core percolation was on the Bethe lattice in the context of magnetic systems @cite_18 . Recently, it has been used in studies of the Ising model and nucleation @cite_29 @cite_32 , analysis of zero temperature jamming transitions @cite_19 , and in a bootstrap percolation model in square lattices and random graphs @cite_20 @cite_2 @cite_9 @cite_14 @cite_16 .
@cite_18 @cite_14 @cite_29 @cite_9 @cite_32 @cite_19 @cite_2 @cite_16 @cite_13 @cite_20
2166942778 2027508917 2523448217 2903855202
We consider bootstrap percolation on uncorrelated complex networks. We obtain the phase diagram for this process with respect to two parameters: @math , the fraction of vertices initially activated, and @math , the fraction of undamaged vertices in the graph. We observe two transitions: the giant active component appears continuously at a first threshold. There may also be a second, discontinuous, hybrid transition at a higher threshold. Avalanches of activations increase in size as this second critical point is approached, finally diverging at this threshold. We describe the existence of a special critical point at which this second transition first appears. In networks with degree distributions whose second moment diverges (but whose first moment does not), we find a qualitatively different behavior. In this case the giant active component appears for any @math and @math , and the discontinuous transition is absent. This means that the giant active component is robust to damage, and also is very easily activated. We also formulate a generalized bootstrap process in which each vertex can have an arbitrary threshold. A new percolation problem is posed which can exhibit a first-order transition. In bootstrap percolation, sites on an empty lattice are first randomly occupied, and then all occupied sites with less than a given number m of occupied neighbours are successively removed until a stable configuration is reached. On any lattice for sufficiently large m, the ensuing clusters can only be infinite. On a Bethe lattice for m>or=3, the fraction of the lattice occupied by infinite clusters discontinuously jumps from zero at the percolation threshold. From an analysis of stable and metastable ground states of the dilute Blume-Capel model (1966), it is concluded that effects like bootstrap percolation may occur in some real magnets. We generalize the standard site percolation model on the @math -dimensional lattice to a model on random tessellations of @math . We prove the uniqueness of the infinite cluster by adapting the Burton-Keane argument burton1989density , develop two frameworks that imply the non-triviality of the phase transition and show that large classes of random tessellations fit into one of these frameworks. Our focus is on a very general approach that goes well beyond the typical Poisson driven models. The most interesting examples might be Voronoi tessellations induced by determinantal processes or certain classes of Gibbs processes introduced in schreiber2013 . In a second paper we will investigate first passage percolation on random tessellations. Abstract In this paper a random graph model G Z N 2 , p d is introduced, which is a combination of fixed torus grid edges in ( Z ∕ N Z ) 2 and some additional random ones. The random edges are called long, and the probability of having a long edge between vertices u , v ∈ ( Z ∕ N Z ) 2 with graph distance d on the torus grid is p d = c ∕ N d , where c is some constant. We show that, whp, the diameter D ( G Z N 2 , p d ) = Θ ( log N ) . Moreover, we consider a modified non-monotonous bootstrap percolation on G Z N 2 , p d . We prove the presence of phase transitions in mean-field approximation and provide fairly sharp bounds on the error of the critical parameters.