{'fraction_non_alphanumeric': 0.07620035506971734, 'fraction_numerical': 0.016596517125132153, 'mean_word_length': 3.6699580810433163, 'pattern_counts': {'":': 0, '<': 22, '<?xml version=': 0, '>': 42, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Bootstrap percolation on the stochastic block model

We analyze the bootstrap percolation process on the stochastic block model (SBM), a natural extension of the Erd\"{o}s--R\'{e}nyi random graph that allows representing the"community structure"observed in many real systems. In the SBM, nodes are partitioned into subsets, which represent different communities, and pairs of nodes are independently connected with a probability that depends on the communities they belong to. Under mild assumptions on system parameters, we prove the existence of a sharp phase transition for the final number of active nodes and characterize sub-critical and super-critical regimes in terms of the number of initially active nodes, which are selected uniformly at random in each community.


Introduction
Bootstrap percolation on a graph is a simple activation process that starts with a given number of initially active nodes (called seeds) and evolves as follows. Every inactive node that has at least r ≥ 2 active neighbors is activated, and remains so forever. The process stops when no more nodes can be activated. There are two main cases of interest: one in which the seeds are selected uniformly at random among the nodes, and one in which the seeds are arbitrarily chosen. In both cases, the main question concerns the final size of the set of active nodes.
Bootstrap percolation was introduced in [16] on a Bethe lattice, and successively investigated on regular grids and trees [9,10]. More recently, bootstrap percolation has been studied on random graphs and random trees [3,5,6,7,11,12,14,20,24,25,34], motivated by the increasing interest in large-scale complex systems such as technological, biological and social networks. For example, in the case of social networks, bootstrap percolation may serve as a primitive model for the spread of ideas, rumors and trends among individuals. Indeed, in this context one can assume that a person will adopt an idea after receiving sufficient influence by friends who have already adopted it [27,32,35].
More in detail, bootstrap percolation has been studied on random regular graphs [11], on random graphs with given vertex degrees [5], on Galton-Watson random trees [12], on random geometric graphs [14], on Chung-Lu random graphs [6,20], on small-world random graphs [25,34] and on Barabasi-Albert random graphs [3]. Particularly relevant to our work is reference [24], where the authors have provided a detailed analysis of the bootstrap percolation process on the Erdös-Rényi random graph. We emphasize that in [24] seeds are chosen uniformly at random among the nodes. However, the critical number of seeds triggering percolation can be significantly reduced if seed selection procedure is optimized [18].
Over the years, several variants of classical bootstrap percolation on a graph have been considered. In majority bootstrap percolation, a node becomes active if at least half of its neighbors are active. In jigsaw percolation, introduced in [15], there are two types of edges among nodes, one representing "social links" and one representing "compatibility of ideas". Two clusters of nodes merge each other if there exists at least one edge of each type between them. Majority and jigsaw bootstrap percolation have been analyzed on the Erdös-Rényi random graph in [23] and [13], respectively.
An important characteristic of real graphs that is not captured by random graphs models on which bootstrap percolation (and its variants) has been studied so far, is the "community structure". Informally, one says that a graph has a "community structure" if nodes are partitioned into clusters in such a way that many edges join nodes of the same cluster and comparatively few edges join nodes of different clusters [21]. Many methods have been proposed for community detection in real networks (see review article [19]). In the development of theoretical foundations of community detection, it has recently attracted considerable attention the so-called stochastic block model (SBM), which is basically defined as the superposition of different Erdös-Rényi random graphs. In particular, detection of two symmetric communities has been studied in [29], while partial or exact recovery of the community membership has been investigated in [1] and [2].
In this paper we study classical bootstrap percolation on the SBM, assuming that seeds are selected uniformly at random within each community and allowing a different number of seeds for different communities. We prove the existence of a sharp phase transition for the final size of the set of active nodes, identifying a sub-critical regime, in which the bootstrap percolation process essentially does not evolve, and a super-critical regime, in which the activation process essentially percolates the whole graph. Our results generalize and strengthen the main achievements in [24]. We emphasize that our techniques significantly differ from those employed in [24]. In particular, we devise a suitable extension of the classical "binomial chain" construction originally proposed in [31] (which was successively applied in [24] to Erdös-Rényi graphs), adapting it to the SBM. Furthermore, differently from [24] where martingales concentration inequalities are exploited, we resort on concentration inequalities for the binomial distribution to prove that bootstrap percolation on the SBM concentrates around its average. Our approach provides exponential bounds on the related tail probabilities, which allow us, under a mild additional assumption, to strengthen convergence in "probability" for the final size of active nodes (as obtained in [24]) to the level of "almost sure" convergence. To better understand the main difficulties in the analysis of bootstrap percolation on the SBM, we recall that in the classical "binomial chain" construction a (virtual) discrete time is introduced and at each time step a single active node is "explored" by revealing its neighbors. Nodes become active as soon as the number of their "explored" neighbors reaches percolation threshold r. In the SBM stochastic properties of the set of active nodes at time step t heavily depend on the number of nodes that have been "explored" in each community up to time t, and this makes the analysis of the bootstrap percolation process on the SBM significantly more complex. In particular, it requires the identification of an appropriate "strategy" to select the community in which a new node is "explored" at every time step.
We acknowledge that the SBM, in spite of its flexibility to represent a wide variety of communitybased systems and its mathematical tractability, does not accurately describe most real-world graphs. Indeed, it does not model the possible heterogeneity among nodes belonging to the same community. Different variants of the SBM have been proposed to better fit real network data, such as making nodes to follow a given degree sequence [17,26] or considering overlapping communities and mixed membership models [4,22]. The investigation of bootstrap percolation on the SBM is certainly a first step towards the analysis of this process on more sophisticated community-based models.
The paper is organized as follows. In Section 2 we introduce the model, we describe the extension to the SBM of the classical "binomial chain" representation of bootstrap percolation, and we state the model assumptions. The main results of the paper are stated in Section 3 where, to better convey the ideas which lead us to identify critical conditions for the bootstrap percolation process on the SBM, we briefly recall also the main achievements in [24], and the intuition behind them. In Section 4 we discuss some consequences of our results with the help of numerical illustrations. All proofs are presented in Section 5.
2 The stochastic block model 2

.1 Model's description
The SBM G = G({n i } 1≤i≤k , {q ij } 1≤i,j≤k ), k, n i ∈ N := {1, 2, . . .}, k i=1 n i = n, q ij ∈ [0, 1), q ij = q ji , is a random graph formed by the superposition of k Erdös-Rényi's random graphs G i = G(n i , p i ), p i := q ii , called hereafter communities, where edges joining nodes of communities G i and G j , i = j, are independently added with probability q ij .
The bootstrap percolation process on the SBM is a nodes' activation process which obeys to the following rules: • Nodes can be active or inactive.
• At the beginning, an arbitrary number a i (0 ≤ a i ≤ n i ) of nodes, called seeds, are chosen uniformly at random among the nodes of G i . Seeds are declared to be active.
• Nodes not belonging to the set of seeds are initially inactive.
• An inactive node becomes active as soon as at least r ≥ 2 of its neighbors are active.
• Active nodes never become inactive and so the set of active nodes grows monotonically.
• The process stops when no more nodes can be activated.
Bootstrap percolation naturally evolves through generations of nodes that are sequentially activated. Zeroth generation G 0 is the set of seeds; first generation G 1 is composed by all the nodes which are activated by seeds; second generation G 2 is composed by all the nodes that are activated by both seeds and nodes of the first generation, and so on. Bootstrap percolation stops when either an empty generation is obtained or all the nodes are active. The final set of active nodes is clearly given by We propose an extension of the classical "binomial chain" representation of the system dynamics, which makes easier the analysis of the final size of active nodes |G|. We introduce a (virtual) discrete time t ∈ N ∪ {0} and we assign a marks counter M v (t), M v (0) := 0, to every node v which is not a seed. Seeds are activated at time t = 0. At every time step t a single active node from one of the k communities is "used", i.e., "explored" by revealing its neighbors and by adding a mark to each of them. Nodes, which are not seeds, become active as soon as they collect r marks. For i = 1, . . . , k, we denote by A i (t) and U i (t) the set of active nodes at time t in community G i and the set of "used" nodes up to time time t in community G i , respectively. We set U i (0) := ∅ and denote by A i (0) the set of seeds in community G i .
The process evolves according to the following recursive procedure. At time t ∈ N: • We select arbitrarily a community, in which active and not yet "explored" nodes are available, i.e., we select arbitrarily a community G j such that A j (t − 1) \ U j (t − 1) = ∅. More formally, we select a community G j according to probability where {C i (t)} 1≤i≤k are arbitrary non-negative random variables such that: • We choose uniformly at random a node v i.e., we "explore" the node by revealing its neighbors and by adding a mark to each of them.
is the set of nodes in community G i that become active exactly at time t, i.e., the set of nodes in community G i that collected the rth mark exactly at time t. Note that, by construction, • The process terminates as soon as A i (t) = U i (t), ∀ i = 1, . . . , k, i.e., at time Throughout this paper random variables {C i (t)} 1≤i≤k, t<T specify the "strategy" (or "policy") followed by the bootstrap percolation process. We emphasize that random variables C i (t) are introduced to formalize in mathematical terms the selection mechanism of the community in which a new node is "used" at a given time step. The very weak assumptions that we impose on such random variables allow us to represent essentially any possible way to select communities. Note that, by construction, for any t ≤ T , Indeed, at every time t ≤ T , the process "explores" a node belonging only to one of the k communities. Let A(t) := k i=1 A i (t) denote the set of active nodes at time t ≤ T and consider a node v ∈ A(0). We clearly have We also have where U i (t) := |U i (t)| and random variables {I when v is a node of community G j . Here Be(p) denotes a Bernoulli distributed random variable with mean p ∈ [0, 1]. The following proposition, whose proof is given in Subsection 5.5, holds.
We have defined random marks I (i) v (s) for v / ∈ A(t), 1 ≤ i ≤ k and 1 ≤ s ≤ T , but, similarly to [24], it is possible to introduce additional, redundant random marks, which are independent and Bernoulli distributed with mean q ij if v is a node of community G j , in such a way that I is defined for all v ∈ G, 1 ≤ i ≤ k and s ∈ N. Such additional random marks are added, for any 1 ≤ s ≤ T , to already active nodes and so they have no effect on the underlying bootstrap percolation process. Throughout this paper, we denote by Bin(u, p), u ∈ N, p ∈ [0, 1], a random variable following the binomial distribution with parameters (u, p). For fixed i ∈ {1, . . . , k} and t ∈ N, we have where U(t) := (U 1 (t), . . . , U k (t)), u(t) := (u 1 (t), . . . , u k (t)), symbol L = denotes equality in law and random variables Bin(u j (t), q ij ), j = 1, . . . , k, are independent. The number of active nodes in community G i at time t ∈ N ∪ {0} is given by where Since random variables are independent and identically distributed with law specified by (4), we have where b(u(t), and q i := (q ij ) 1≤j≤k . Hereafter, we denote by A(t) := |A(t)| = k i=1 A i (t), the number of active nodes in the SBM at time t, and by A * := A(T ) = T the final number of active nodes.

Remark 2.2
The analysis of the bootstrap percolation process is significantly more complex on the SBM than on the Erdös-Rényi random graph due to the following two reasons. (i) On the SBM, at each time step t ≤ T , we select, according to the chosen "strategy", a community in which "exploring" an active node. In particular, note that, for any 1 ≤ i ≤ k and t < T , random variables A i (t) heavily depend on quantities {U i (t)} 1≤i≤k , which are themselves constrained by the availability of "usable" nodes in communities, and therefore on the adopted "strategy". In contrast, to analyze the bootstrap percolation process on the Erdös-Rényi random graph there is clearly no need to introduce any "policy". (ii) As a consequence of (i), for any i = 1, . . . , k and t < T , the law of random variables S i (t) is binomial only given event {U(t) = u(t)}. Therefore, for any 1 ≤ i ≤ k and t < T , the probabilistic structure of random variables S i (t) is significantly more complex on the SBM than on the Erdös-Rényi random graph, i.e., for k = 1. On the latter graph, indeed, U 1 (t) = t and the law of S 1 (t) is binomial with parameters (n 1 − a 1 , b(t, p 1 )), where b(t, p 1 ) := P (Bin(t, p 1 ) ≥ r).
Finally, we remark that thanks to Proposition 2.1, differently from quantities A i and U i , the final number of active nodes A * does not depend on the chosen "strategy". Remark 2.3 A possible alternative way to extend the classical "binomial chain" construction to the SBM could be the following. At each time step t ≤ T , a node is "used" in each community G i in which at least one "usable" node can be found, i.e., in each community Although this alternative extension of the classical "binomial chain" construction on the SBM makes the system dynamics independent on the "strategy", it appears pretty difficult to analyze due to the complex probabilistic structure of random variables {A i (t)} 1≤i≤k, t<T and {U i (t)} 1≤i≤k,t<T . It will appear from our investigation that the opportunity to "arbitrarily" define the "policy", according to which communities are selected, provides a degree of flexibility that comes in handy to analyze the process (see the proofs of Theorems 3.2 and 3.3).

Model assumptions
Hereafter, given two functions f 1 and f 2 we write f 1 (n) ≪ f 2 (n) (or equivalently f 1 (n) = o(f 2 (n))), In the following we consider a sequence of SBMs with a growing number of nodes n and we explicit the dependence on n of the related variables. We warn the reader that, unless explicitly written, all the limits in this paper are taken as n → ∞.
Condition (11) means that the SBM is "weakly assortative", indeed, for any community G i , the "intra-community" edge probability p (i) n is required to be not smaller than each "extra-community" edge probability q (ij) n (i = j). Condition (12) guarantees that, asymptotically, the "intra-community" edge probabilities are comparable with each other (i.e. are of the same order). Note that, although two different communities G i and G j (i = j) may be completely disconnected (in the sense that no edges are established between them, which occurs when q (ij) n = 0), thanks to condition (16) there are no isolated communities. Indeed, condition (16) guarantees that graph G = G(k, χ), whose k nodes represent communities and an edge is established between node i and node j if χ ij > 0, is connected. We remark once again that the number of seeds in each community can be arbitrarily chosen (i.e., quantities a (i) n , i = 1, . . . , k, are arbitrary) while seeds within each community must be selected uniformly at random. We also remark that, although throughout this paper it is assumed α := (α 1 , . . . , α k ) = 0, it is easily checked that for α ≡ 0 the system is in sub-critical conditions.
From now on, we explicit the dependence of n , A n and A * n , respectively. For reader's convenience, we summarize the main notation of the paper in Tables 1 and 2. With a few exceptions, in our notation we have adopted the following general rules. (i) System's parameters are denoted by small latin letters; (ii) dynamical variables are denoted by capital latin letters; (iii) sets (including curves) are denoted by calligraphic letters; (iv) asymptotic limits (as n → ∞) are denoted by small greek letters. Moreover, we have used the following rule when adding indexes to symbols: index n is always put as pedex; other indexes are preferably put as pedex, unless they conflict with n, in which case they are put as apex (in round brackets in order to avoid confusion with exponentiation).

Bootstrap percolation on the Erdös-Rényi random graph: a quick review
To better understand the ideas which led us to identify sub-critical and super-critical conditions for the bootstrap percolation process on the SBM, we briefly recall the main results in [24]. Note that the Erdös-Rényi random graph corresponds to a special case of the the SBM, (i.e., when k = 1).
(ii) If (10) and (14) hold (with k = 1) and α 1 > 1, then A * n /n → 1, in probability (see Theorem 3.1(ii) in [24]). In words, below the critical number of seeds g (1) n , the bootstrap percolation process essentially does not evolve, reaching, as n → ∞, a final size of active nodes which is of the same order as a (1) n (sub-critical case); above critical number of seeds, g (1) n , the process percolates through the entire graph, reaching, as n → ∞, a final size of active nodes which is of the same order as n (super-critical case).
We briefly and informally describe the intuition behind these results. First of all note that, since k = 1, we have U      n (t) − t} t∈N is "concentrated" around its mean, as n → ∞, and (see [24] for details), where and ⌊x⌋ denotes the greatest integer less than or equal to x ∈ R. A simple computation shows that function ρ 1 has a unique point of minimum at x = r/(r − 1) and ρ 1 (r/(r − 1)) = α 1 − 1. Therefore, since bootstrap percolation stops the first time at which the number of "active and not yet used" nodes equals zero we have that (i) if α 1 < 1, then bootstrap percolation stops at a time which is, asymptotically in n, of the same order as g (1) n , (ii) if α 1 > 1, then bootstrap percolation does not stop at times which are, asymptotically in n, of the same order as g (1) n . In the super-critical case, further analysis of function t → R n ) at times bigger than g (1) n reveals that R n ) decreases linearly and hits zero at time t n ∼ e n. As a consequence, for α 1 > 1, bootstrap percolation terminates at a time which is of the same order as n.

Phase transition of the bootstrap percolation process on the SBM
As recalled in the previous section, bootstrap percolation on the Erdös-Rényi random graph exhibits a sharp phase transition; the reader may be wondering whether more complex phenomena, such as selective percolation of communities, can be observed on the SBM. We shall show that this is not the case. Indeed, under the assumptions described in Subsection 2.2, in analogy with the case k = 1, the bootstrap percolation process either stops at time scales g (1) n (sub-critical case), or it percolates the whole graph (super-critical case).
To present our results, we start introducing the asymptotic normalized mean number of "active and not yet used" nodes (i.e., function corresponding to ρ 1 ). For n, t ∈ N and i ∈ {1, . . . , k}, we set Hereon, for x : The following lemma holds.

Theorem 3.3 Assume
These results can be roughly summarized as follows: (i) under (Sub), the bootstrap percolation process on the SBM basically does not evolve as n → ∞ (note that, due to conditions (14), (16) and (17) n as n → ∞), (ii) under (Sup), the bootstrap percolation process on the SBM basically percolates the whole graph as n → ∞.

An informal description of some basic ideas of the proofs
In broad terms, proofs of Theorems 3.2 and 3.3 adopt the following scheme: first, we analyze the average dynamics of the number of "active and not yet used" nodes; second, we show that the "true" random processes are sufficiently concentrated around their averages. As already noticed in Remark 2.2, the following issue makes the analysis of the bootstrap percolation process significantly more complex on the SBM than on the Erdös-Rényi random graph: for any 1 ≤ i ≤ k and t < T n , random variables A i (t) heavily depend on quantities {U i (t)} 1≤i≤k , and therefore on the considered "strategy". In turn, the chosen "strategy" {C (i) n (t)} 1≤i≤k,t<Tn , according to which the nodes are selected and "used" in different communities, is constrained by the availability of "active and not yet used" nodes in the different communities, indeed A (i) In this discussion, we refer to such constraints as "feasibility"constraints, and to "strategies" satisfying such constraints as "feasible strategies".
We remark once again that, due to Proposition 2.1, A * n does not depend on the considered "feasible" strategy. Therefore, in order to study A * n we have the freedom to arbitrarily select the "feasible strategy" according to our convenience. A first crucial step in the proofs of our main results consists in the identification of a suitable "feasible strategy", which allows us to analyze the bootstrap percolation process. A first natural candidate is the "strategy" defined, for 1 ≤ t ≤ T n , by: which corresponds to select (and then to "use") a node uniformly at random, among all the "active and not yet used" nodes. The main drawback of this "strategy" is that the analysis of corresponding process U n (t), t ≤ T n , appears prohibitive due to its complex correlation structure. To circumvent these difficulties we introduce a "fluid" version of "strategy" (25), under which U n (t) is deterministic. The construction of such "fluid strategy" is related to the solution of a Cauchy problem that will be introduced in Subsection 5.1.3. Unfortunately, since process U n (t) is deterministic, regardless of the evolution of process A n (t), one can not guarantee that such "fluid policy" is "feasible" up to time T n . Therefore, we limit the application of such a "fluid strategy" up to a certain random time T ′ n , where its "feasibility" is guaranteed, and we switch to "policy" described by (25) in the time interval (T ′ n , T n ]. The asymptotic analysis of the average dynamics of the above "fluid strategy" permits us to identify three regimes, which are shown to be equivalent to (Sub), (Sup) and (Crit). Then we prove that the number of "active and not yet used" nodes concentrates around its average. To accomplish this step, differently from [24], where martigales' theory has been employed, we exploit classical concentration inequalities for the binomial distribution.
4 Analytical description of the critical regions in terms of the parameter α By Theorems 3.2 and 3.3 we immediately determine the sub-critical and the super-critical regions, i.e., set of α for which the sub-critical and the super-critical behavior is experienced. Indeed, by expliciting the dependence of ρ i on α i and the dependence of D ρ on α, we can associate to conditions (Sub), (Crit) and (Sup) the regions: respectively. Since R Sub , R Crit and R Sup are disjoint and exhaustive, and R Crit contains only those points which are in the boundary of R Sup and in the boundary of R Sub , our description of regions R Sup and R Sub is tight.
We have already noticed that in the case of one community (i.e., for the Erdös-Rényi random graph) R Sub ≡ [0, 1), R Crit ≡ {1} and R Sup ≡ (1, ∞). Unfortunately, in the more general case of k ≥ 2 communities, sub-critical and super-critical regions can not be always described in terms of parameter α through simple closed form expressions. However, as we shall see in the next subsection, when matrix χ is invertible critical region can be determined by a simple computational procedure.

General results
The following propositions hold.

The case of k "identical" communities: numerical illustrations and informal discussion
We illustrate Proposition 4.2 in the special case of k ≥ 2 "identical" communities, i.e., n n , q (ij) n = q n , for i = j, and p (i) n = p n for any i. We assume: k/n ≪ p n ≪ (k/n) 1/r , q n < p n , q n /p n → ψ ∈ (0, 1), (14) and (17). Then χ ii = 1, χ ij = χ ji = ψ for i = j and the corresponding assumptions (9), (10), (11), (12) and (16) are satisfied. A straightforward computation shows that In Figure 1, for fixed k = r = 2, we plotted curve R Crit for different values of parameter ψ. Note that, as ψ ↓ 0, sub-critical region approaches the whole square. Indeed, this can be formally verified letting ψ tend to zero in the corresponding expression of R Crit .
In Figure 2 for fixed k = 2 and ψ = 1/3, we plotted curve R Crit for different values of parameter r. Note that, as r ↑ ∞, the sub-critical region approaches the domain The above numerical illustrations show that the best way to trigger percolation of the whole graph is to maximize the value of either α 1 or α 2 , i.e., to put all the seeds in the same community; instead, the worst manner to trigger percolation of the whole graph is to jointly minimize the values of α 1 and α 2 , i.e., to equally partition seeds between the communities.
These properties of the bootstrap percolation process on the SBM may be proved formally (for the general case of k identical communities) by exploiting the convexity of the sub-critical region and the symmetry among communities. We remark that, while for the worst way to trigger percolation, critical value α can be computed analytically, for the best way to trigger percolation one can only numerically estimate α.
More precisely, consider firstly the worst way to trigger percolation, i.e., assume (14) with A straightforward computation shows that (α, . . . , α) ∈ R Crit if and only if Since each community has n/k nodes, for each community we have . Therefore, putting the same number of seeds in each community, asymptotically, the total number of seeds is: . As expected, as ψ → 1, quantity kαg n tends to g n /k 1/(r−1) , i.e., the total number of seeds in the case of one community. Note that for ψ < 1, as k grows large, kαg n tends to and this quantity is asymptotically equivalent (as n → ∞) to i.e, the total number of seeds in the case of one community with connection probability q n . The intuition behind this fact is the following. As k grows large, most of the neighbors of any given node belong to communities which are different from the community to which the node belongs. So the impact of neighbors belonging to the same community of the node becomes negligible. Now consider the best way to trigger percolation, i.e., assume α = (α, 0, . . . , 0). In this case, applying Proposition 4.2 one has that, in general, α can only be numerically estimated. Indeed, α can be defined as the unique zero in (0, 1) of an algebraic equation of order r 2 − 1. In the special case of r = 2, a closed form expression for α can be obtained by using Cardano's formulas.
In Figure 3 we have plotted the total critical number of seeds in the SBM normalized to the critical number of seeds in G(n, p n ), as a function of k, for fixed ψ = 1/10, and either r = 2 or r = 4. The curves related to the extreme cases are labeled "equal-split" (when the seeds are equally divided among the communities) and "all-in-one" (when all the seeds are put in the same community), respectively. We note that, although both seeds' allocations strategies tend to perform the same as k grows large, they require a quite different number of seeds for small number of communities. The performance of any seeds' allocation strategy lies between the two extreme cases.

Preliminaries
We start with some preliminaries. In Subsection 5.1.1 we highlight some properties of the Jacobian of ρ which will be used in the proofs. In Subsection 5.1.2 we introduce some additional notation. In Subsection 5.1.3 we describe the Cauchy problem whose solution allows us to define the asymptotic "fluid strategy" previously mentioned. Finally, in Subsection 5.1.4 we present equivalent formulations of conditions (Sub), (Crit) and (Sup), which will be exploited in the proof of the main theorems. Throughout this section we assume model assumptions (9), (10), (11), (12), (14), (16) and (17).

The Jacobian of ρ
In the following, we denote by • B and ∂B the interior and the boundary of a Borel set B ⊆ R k , respectively, and refer the reader to [28] for standard notions and results of matrix theory. Moreover, we shall not specify, when this is clear from the context, if a vector is meant as column or row vector.
We have: be the Jacobian matrix of vectorial function ρ and definẽ We remark that (i) diagonal terms of J ρ (x) are such that (J ρ (x)) ii ≤ 0, i = 1, . . . , k, and the equality holds if and only if x ∈D, (ii) terms outside the diagonal of J ρ (x) are such that (J ρ (x)) ij ≥ 0, i, j = 1, . . . , k, i = j, and the equality holds if and only if x = 0 and/or χ ij = 0.
is the non-negative matrix defined by (P(x)) ii := ℓ(x) + (J ρ (x)) ii , i = 1, . . . , k, (P(x)) ij := (J ρ (x)) ij , i, j = 1, . . . , k, i = j, and I is the identity matrix. Note that by the irreducibility of χ (i.e., condition (16)) we immediately have that P(x) is irreducible as well. Combining this with the fact that all diagonal terms of P(x) are strictly positive we deduce that P(x) is primitive. Therefore, by Perron-Fröbenius theorem there exists a positive eigenvalueλ P F (x) > 0 of P(x) to which it corresponds a unique positive (component-wise) eigenvectorφ P F (x). A straightforward computation shows that is an eigenvalue of J ρ (x) to which it corresponds (positive) eigenvector φ P F (x) :=φ P F (x). Since P(x) and J ρ (x) have the same eigenvectors, it turns out that φ P F (x) is the unique positive eigenvector of J ρ (x).

Some more notation
We denote by K h the set of all communities at distance h ≥ 1 from community G 1 on connected graph G, and by d the maximum distance from community G 1 , i.e., where χ h is the hth power of matrix χ, and For later purposes (see e.g. Lemma 5.5) we note that, by the irreducibility of χ, for any i ∈ {1, . . . , k}, there exists a unique d i ∈ {0, . . . , d} such that i ∈ K d i . Quantity d i is nothing but that the distance, on the connected graph G, between communities G i and G 1 .
We put where Finally, we define vectors x (0) and

A related Cauchy problem
Hereon, we denote by B δ (x) the closed ball of R k centered at x ∈ R k with radius δ > 0 and set From now on, we suppose ρ i : By the regularity properties of functions ρ i there exists a unique solution x(y), y ∈ [y 0 , y + ), of (35) (see [8]), where y + := sup{y > y 0 : We remark that, in general, y + can be either finite or infinite. Consider the subset of D defined by Throughout this paper, we denote by E the closure of the largest connected component of E ′ containing x 0 (as we shall explain later on, we have 0 ∈ E) and by y E the first exit time of the solution x(y), y ∈ [y 0 , y + ), of (35) from • E, i.e., We anticipate that by Lemma 5.5 it holds x 0 ∈ • E. Hereafter, we shall consider point x(y E ) := lim (note that limit exists since x(·) is strictly increasing (component-wise) on E).

Remark 5.1
The following intuitive interpretation can be given to the solution of the Cauchy problem (35). Since can be interpreted as the (normalized) rate at which the active nodes are "explored" in community G i . By Lemma 3.1 Therefore, the solution of Cauchy problem (35) corresponds (asymptotically) to (normalized) trajectory t → U n (t) described by a "policy" according to which, given U n (t − 1), nodes to be "explored" at time step t are chosen in community G i with probability .

Equivalent formulations of (Sub), (Crit) and (Sup)
The proofs of Theorems 3. Note that S ⊂ E, indeed x 0 ∈ S, S is clearly connected and it can be checked that functions ρ i are non-negative on S (as a straightforward consequence of Lemma 5.5, to be stated in the next subsection). Let C E be the trace of curve x : [y 0 , y E ] → R k (where x(·) denotes the solution of (35)), defineS and let Z denote the set of distinct zeros of ρ within D. We shall consider conditions: (Sub): There exists x ∈ D such that ρ(x) < 0.
and min (Crit) ′ : y E = +∞, x(y E ) ∈ Z ∩ • D, the curve with trace C := S∪ C E ∪S is continuous, non-decreasing and satisfies (38) and min (Sup) ′ : y E < +∞, x(y E ) ∈D, ρ(x(y E )) > 0, the curve with trace C := S ∪ C E is continuous, non-decreasing and satisfies (38) and The following theorem (whose proof is given in Subsection 5.4) holds.

Proof of Theorem 3.2
In this subsection we show that (23) holds with where x(y) = (x 1 (y), . . . , x k (y)) is the solution of Cauchy problem (35) and y E is defined by (36). Our proof uses Lemmas 5.3, 5.4 and 5.5 below, which are proved in Subsection 5.6.
Step 1: chosing a suitable "strategy". Let ζ : [0, 1] → R k be a parametrization of the curve with trace C defined in (Sub) ′ (recall that by Theorem 5.2 (Sub) is equivalent to (Sub) ′ ) and set v n (γ) : n , . . . , t (m+1) n }. Without loss of generality we assume t (0) and Now we extend the definition of w . . , k. Then we define recursively indexes Finally, for any t ∈ (0, v n (1)) ∩ N) \ v n ([0, 1]), there exist t where J We define random variables For 0 ≤ t ≤ T ′ n , we consider the "policy" defined by Note that C  n (t) = 0 for each j = i. For T ′ n < t ≤ T n , we use an arbitrary "(feasible) strategy", for concreteness we chose the "strategy" defined by (25). In words, the chosen "strategy" is deterministic and equal to (48) as long as it is possible. Indeed, T ′′ n is the first time at which the deterministic "strategy" (48) can not be employed because of the lack of "usable" active nodes in the selected community at time T ′′ n . Note that defining w n (t) := (w (1) n (t), . . . , w (k) n (t)), we have U n (t) = w n (t), ∀t ≤ T ′ n and U n (T ′′ n ) = w n (T ′′ n ).
From which, one can easily check the consistency of our construction, given that T n = A * n ≥ T ′ n .
Now we check that, fort This in turn follows if we check that, for any j ∈ h−1 ℓ=0 K ℓ , we have Indeed this implies that quantity w n ], and therefore (reasoning as for the derivation of relation (59)), for any j ∈ h−1 ℓ=0 K ℓ , where the latter equality follows by monotonicity of A (j) n (·). Now we check (65). Let θx and therefore, for any j ∈ h−1 ℓ=0 K ℓ , i.e., for any j such that d j ≤ h − 1 (where d j is defined in Subsection 5.1.2), Consequently, and (65) is checked. Then, exploiting (63) and (64), we rewrite (60) as Inequality (52) follows noticing that, for all n large enough, and Here in (67) and (69) we used (7), and in (68) we used that, for all n large enough and all 0 ≤ s ≤t Step 3.2: proof of (56). Let h ∈ {1, . . . , d} and j ∈ K h be fixed. By Lemma 3.1, Lemma 5.5(iii), (61) and (62), for any ε > 0 there exists n ε (j, h) such that for all n > n ε (j, h) n .
We note that, for anyt ) and so, for anyt By (66) Combining (70), (71) and (30), for any fixed h ∈ {1, . . . , d}, j ∈ K h andt n , for any ε > 0 there exists n ε (j, h) such that for all n > n ε (j, h) Therefore by the definition of R (j) n and the fact that w (j) n , for any ε > 0 there exists n ε (j, h) such that for all n > n ε (j, h) we have Therefore, for all n large enough, for some positive constant c 1 > 0. By this inequality easily follows that, for all n large enough, which, for all n large enough, yields for some positive constant c 2 > 0, and therefore (56).
Step 3.3: proof of (57). Recall that ζ(γ For ε > 0, letC ε be the ε-thickening ofC, i.e., and · is the Euclidean norm. By the regularity properties of ρ, we have that there exists ε 0 > 0 small enough such thatC ε 0 ⊂ n ) ∈C ε 0 for any n >n andt n ≤ s ≤ v n (γ E −δ)−1; therefore we can selectn such that ŵ n (s)−ζ(γ s ) ≤ ε 0 , and soŵ n (s) ∈C ε 0 , for any n >n andt Consequently, for any ε > 0 and all n sufficiently large, where c 4 > 0 is a positive constant and Note that (57) easily follows by (73) if we prove that, for some positive constant c 3 > 0, For this it suffices to prove that, for any j ∈ {1, . . . , k}, for all n large enough it holds We shall show this relation for j = 1 as the other relations can be proved similarly. Note that ǫ := min z∈Cε 0 ρ 1 (z) > 0. From now on, we choose ε < ǫ. By Lemma 5.3 we have that for any 0 < ε ′ < ǫ − ε, for all n large enough (n Therefore, by a classical concentration inequality for the binomial distribution (see e.g. Eq. (1.6) of Lemma 1.1. p. 16 in [30]), for all n large enough, we have where in (75) we used (74) and that H decreases on (0, 1).
Step 4: proof of (51). Define random variable Q n (δ) := sup{t : As usual, we denote by ⌊ζ(γ E + δ)g n ⌋ the vector with components ⌊ζ i (γ E + δ)g (i) n ⌋, i = 1, . . . , k. By construction, vector U n (Q n (δ)) (whose components are U (i) n (Q n (δ)), i = 1, . . . , k) satisfies U n (Q n (δ)) ∈ F ⌊ζ(γ E +δ)gn⌋ . We have Here, in the derivation of the inequality (76) we exploited relations Note that, for fixed j ∈ {1, . . . , k} and u ∈ F , where the latter inequality follows by the stochastic ordering property of the binomial distribution. Combining this inequality with (77) we have the claim then follows if we prove that, for an arbitrarily fixed i ∈ {1, . . . , k}, quantity P (Bin(n n ) goes to zero exponentially fast with respect to g (1) n . For this we exploit the same idea and similar computations as in the proof of (50), and so we omit many details. By Lemma 5.4 and the definition of χ we have Therefore . (79) otherwise we would get a contradiction with (39), since the directional derivative of each function ρ i alongS is increasing. Therefore, by a classical concentration inequality for the binomial distribution (see e.g. Eq. (1.5) of Lemma 1.1 p. 16 in [30]), for all n large enough, we have where function H is defined by (72). The claim (i.e. the exponential decreasing rate with respect to g n ) easily follows combining this inequality with (78) and (79), and using that H increases on (1, ∞).

Proof of Theorem 3.3
Let ζ : [0, ∞) → R k be a parametrization of the curve with trace C ∪S ext , where C is defined in (Sup) ′ (recall that by Theorem 5.2 (Sup) is equivalent to (Sup) ′ ) and is the extension ofS outside D. Let v n (γ) be defined by (43)   n (·) to any t ∈ N \ v n ([0, ∞)) as in (46). We define the random variables T ′ n as in (47) (with n in place of v n (1)). As in the proof of Theorem 3.2, for t ≤ T ′ n , we consider the "policy" C (i) n defined by (48). We proceed dividing the proof in three main steps.
Step 1: outline of the proof. For ε ≥ 1, we have P (n − A * n > εn) = 0, and the claim is obvious. Since A * n ≥ T ′ n , for ε ∈ (0, 1), we have and therefore it suffices to show that For a suitable positive constant c 1 > 0 and all n large enough, we have is defined by (53), arguing as in the proof of Theorem 3.2 one has T 1,n (d) n ). In the next two steps we shall show that and concluding the proof.
Step 2: proof of (80). For all n large enough, we have The claim clearly follows if we prove and We divide the proof of this step in two parts. In the Step 2.1 we prove (82) and in the Step 2.2 we prove (83).
The following inequalities are proved in Step 4 of the proof of Proposition 4.1 in [33] and hold for any i and all n large enough: n , for some constant c 8 > 0.
For all n large enough, we have The claim follows if we prove that T 2,n (d) . This can be verified along the same lines as in the proof of relation T 2,n (d) ≥ 1 − O(e −c(ε)g (1) n ), provided within the proof of Theorem 3.2. Hereon, we skip many details and highlight the main differences. For ε > 0, letC ε be the ε-thickening of compact setC := ζ([γ d 0 , γ ′ ]). As in the proof of Theorem 3.2, one has that there exists ε 0 > 0 small enough so thatC ε 0 ⊂ • E and it can be shown that there existsn such that w n (s) ∈C ε 0 for any n >n and anyt Then, for any ε > 0 and all n large enough we get T 2,n (d) ≥ (1 − sup n ) c 9 g (1) n , where sup n is defined as in the proof of Theorem 3.2 and c 9 > 0 is a positive constant. By assumption (Sup) (which is equivalent to (Sup) ′ ) we have min z∈Cε 0 ρ 1 (z) > 0. Then one can show that sup n = O(e −c 10 g (1) n ), for some constant c 10 > 0, exactly as in the proof of Theorem 3.2, and the proof is completed.

Proof of Theorem 5.2
First, we introduce the following additional conditions: For reader's convenience, we summarized in Table 4 all the different "critical" conditions that have been introduced in this paper. The proof of Theorem 5.2 is based on the following lemmas, which will be proved later on.   Proof of Theorem 5.2. Proof of (i). Due to Lemma 5.9 we only have to show (Sub) ′ ⇒ (Sub) ⇒ (Sub). We start proving (Sub) ′ ⇒ (Sub). We reason by contradiction and suppose that the claim is false. Then by Lemma 5.11 we have that (Sub) ′′ does not hold. So either (I) or (Crit) holds (indeed (Sup) can not hold by Lemma 5.6 since we are assuming (Sub) ′ ). If (I) holds, then x(y E ) ∈D by Lemma 5.7, and this contradicts (Sub) ′ . If (Crit) holds, then, by Lemma 5.10, (Crit) ′ holds, and this again contradicts (Sub) ′ . We now prove (Sub) ⇒ (Sub). We reason again by contradiction and suppose that either (Sup) or (Crit) holds. By Lemma 5.8 we have Z = ∅ and so min x∈Dρ ρ 1 (x) ≤ 0. This excludes (Sup). We shall show in part (iii) of this proof that (Crit) ⇒ (Crit). We get a contradiction noticing that conditions (Crit) and (Sub) ′′ are not compatible and by Lemma 5.11 we have that (Sub) ′′ holds. Proof of (ii). Due to Lemma 5.6 it suffices to show that (Sup) and (Sup) are equivalent. We start proving (Sup) ⇒ (Sup). By assumption min x∈Dρ ρ 1 (x) > 0, so there are no zeros of ρ in D ρ , and therefore, there are no zeros of ρ in D. We now prove (Sup) ⇒ (Sup). Reasoning by contradiction assume that (Sup) does not hold. Then either (Sub) or (Crit) holds. If (Sub) holds, then by Lemma 5.9 (Sub) holds. By Lemma 5.11 we then get (Sub) ′′ , which clearly contradicts (Sup). If (Crit) holds, then ρ has zeros on D. Therefore, either (Sub) ′′ or (Crit) or (I) holds. Due to Lemmas 5.11 and 5.12 and the fact that (Sub) ′′ contradicts (Sup), neither (Sub) ′′ nor (I) can hold. The claim follows noticing that also (Crit) contradicts (Sup).
Proof of Lemma 5.6. We start proving (Sup) ⇒ (Sup) ′ . We shall check later on that y E < ∞, x(y E ) ∈D and ρ(x(y E )) > 0. Then, consider the curve with trace C := S ∪ C E . It is easily realized that it is continuous, non-decreasing and C satisfies (38). Curve C satisfies also (41). Indeed, since Proof of y E < ∞. Since by assumption ρ = 0 over compact D, we have m (ρ) Therefore y E < ∞. P roof of x(y E ) ∈D and ρ(x(y E )) > 0. We have either x(y E ) ∈ ∂E ∩D c or x(y E ) ∈ ∂E ∩D, wherẽ D c stands for the complement ofD. Reasoning by contradiction, suppose x(y E ) ∈ ∂E ∩D c . Define I := {i : ρ i (x(y E )) = 0} and J := {j : ρ j (x(y E )) > 0}, and note that I = ∅ (since in particular x(y E ) ∈ ∂E \ k i=1 {x : x i = 0}, and so there exists i ∈ {1, . . . , k} such that ρ i (x(y E )) = 0) and J = ∅ (since x(y E ) ∈ E \ Z). By the irreducibility of χ There exist i 0 ∈ I and j 0 ∈ J such that Since ρ i 0 (x(y)) > 0 for any y ∈ (y 0 , y E ) and ρ i 0 (x(y E )) = 0, we have On the other hand, for any y ∈ (y 0 , y + ), Computing this quantity at y = y E , by (94), the definition of the set of indexes I and J and the fact that all non-diagonal terms of J ρ (x) are non-negative, we have which contradicts (95). Therefore x(y E ) ∈D. To check ρ(x(y E )) > 0, we start noticing that we clearly have ρ(x(y E )) ≥ 0. Reasoning by contradiction, assume that ρ i 0 (x(y E )) = 0 for some i 0 ∈ {1, . . . , k}. Then, arguing as above we get both (95) and (96), and the claim follows. Finally we prove (Sup) ′ ⇒ (Sup). Reasoning by contradiction, suppose Z = ∅ and consider setF z , z ∈ Z, defined byF whereF (j) z := {w ∈ D : w j = z j and w h ≤ z h , ∀h = j}. Since z is a zero of ρ i for any i, we have z = 0 with all components z i = 0. By the monotonicity properties of the ρ i 's, for any j ∈ {1, . . . , k} and any x ∈F (j) z , it holds ρ j (x) ≤ ρ j (z) = 0, and so min 1≤i≤k By the continuity and the monotonicity of curve C and condition (38), we necessarily have As immediate consequence of Lemma 5.5, we have S ∩F z = ∅, and so C E ∩F z = ∅. Taking w ∈ C E ∩F z , we have min which contradicts (41).
Proof of Lemma 5.7. Firstly, we show x(y E ) ∈ Z ∩ ∂E if and only if y E = +∞, secondly, we prove x(y E ) ∈ Z ∩ ∂E. The implication x(y E ) ∈ Z ∩ ∂E ⇒ y E = +∞ follows by the uniqueness of the solution of Cauchy problem (35).We now prove y E = +∞ ⇒ x(y E ) ∈ Z ∩ ∂E. We reason by contradiction. For ε > 0 arbitrarily small, let D (ε) denote the closed subset of D obtained by erasing from D the open balls with radius ε > 0 centered at zeros of b in D. We have and, since x(y E ) / ∈ Z ∩ ∂E, curve ζ E (y) := x(y), y 0 ≤ y ≤ y E , is contained in D (ε) . So arguing as for (93), we have m (ρ) D (ε) (y E − y 0 ) < ∞, which proves the finiteness of y E and therefore yields a contradiction. We finally prove We shall show that x(y E ) / ∈ ∂E ∩D and x(y E ) / ∈ ∂E ∩D c ∩ Z c . Reasoning by contradiction, assume x(y E ) ∈ ∂E ∩D. For an arbitrarily fixed z ∈ Z, there exists x ∈F z ∩ C E ∩ • D, whereF z is defined by (97). So by the monotonicity properties of the ρ i 's we have ρ j (x) ≤ ρ j (z) = 0, for some j. Therefore x / ∈ E, which is impossible. Reasoning again by contradiction, assume x(y E ) ∈ ∂E∩D c ∩Z c . Arguing as in the proof of Lemma 5.6 we deduce both (95) and (96), getting in this way a contradiction.
It is easily seen that Therefore, condition (Sub) implies E ∩D = ∅. On the other hand, we have that condition (Sup) ′ implies E ∩D = ∅ (indeed x(y E ) ∈ E ∩D). Consequently, (Sub) implies that (Sup) ′ does not hold, and so, by Lemma 5.6 condition (Sub) implies Z = ∅.
Proof of Lemma 5.9. Since the implication (Sub) ⇒ (Sub) is obvious, we only need to prove (Sub) ⇒ (Sub ′ ). By Lemma 5.8 we have Z = ∅ and so by Lemma 5.7 it holds y E = +∞ and x(y E ) ∈ Z. Let x ∈ • D be such that ρ(x) < 0 and consider setsF x andĜ x defined by (97) (with x in place of z) and (98). By (99) we have x(y E ) ∈ • D, and so x(y E ) ∈ Z ∩ • D. Note that the curve with trace C := S ∪ C E ∪S is continuous, non-decreasing, satisfies (38) and it is such that C ∩F x = ∅. Therefore there exists an i such that C ∩F x . As an immediate consequence of Lemma 5.5, we have S ∩F x = ∅, and therefore x * ∈ C E ∪S ∩F (i) x . Finally, since ρ i is non-decreasing with respect to the jth variable, j = i, we have which yields (39) and completes the proof. Indeed, each ρ i is non-negative on S ∪ C E , strictly positive onS \ {x(y E )} and ρ i (x(y E )) = 0, for any i = 1, . . . , k. In particular, the strict positivity of ρ i 's onS \ {x(y E )} follows by the fact that x(y E ) is the unique point of minimum of each ρ i onS and ρ i (x(y E )) = 0 (indeed, this is a consequence of the convexity ofS, the convexity of the ρ i 's and the fact that x(y E ) is the unique critical point of ρ i 's onS since λ P F (x(y E )) = 0).

Proof of Proposition 2.1
In this proof we simply write A, U and T in place of A n , U n and T n . We first prove This is equivalent to prove H h=0 G h ⊆ A(T ), for any H ∈ N ∪ {0}. We show this claim by induction over H. We clearly have The inclusion (104) follows if we check G H+1 ⊆ A(T ). Take v ∈ G H+1 and, reasoning by contradiction, suppose v / ∈ A(T ). By the definition of the bootstrap percolation process v ∈ G H+1 has at least r neighbors in H h=0 G h . This set of active nodes is contained in U(T ) due to the inductive hypothesis and relation A(T ) = U(T ). Consequently, by (3), M v (T ) ≥ r and so, by (2), v ∈ A(T ), which is a contradiction. We now prove G ⊇ A(T ).
For this it suffices to prove that A(t) ⊆ G for any 0 ≤ t ≤ T . We denote by ∆A(t) the set of nodes that become active exactly at time t. Reasoning by contradiction, assume that there exists at least a v ∈ ∆A(t), r ≤ t ≤ T , such that v / ∈ G h , for any h ∈ N ∪ {0}. Then there must exist a minimum time t 0 with r ≤ t 0 ≤ T such that ∆A(t 0 ) ⊆ G. Since v ∈ ∆A(t 0 ), it has at least r neighbors in U(t 0 ). By construction we have U(t 0 ) ⊆ A(t 0 − 1) and A(t 0 − 1) ⊆ G. So v has r neighbors in G. Therefore v ∈ G, which is a contradiction. Bin(⌊x j g (j) n ⌋, q (ij) n ) ≥ r   .
The case h = 1 is an immediate consequence of (105). Now, assume h ≥ 2 and suppose that the claim holds for h − 1. By the independence of binomial random variables and (105) Bin(⌊x j g (j) n ⌋, q (ij) n ) ≥ r − r h   P Bin(⌊x h g (h) n ⌋, q (ih) n ) = r h + P Bin(⌊x h g (h) n ⌋, q (ih) n ) ≥ r + 1 .
The proof of Proposition 4.2 exploits the following lemma which will be proved later on.
In the second step we use this equivalence to determine region R Crit (and consequently, R Sub and R Sup ).