# Bootstrap percolation on geometric inhomogeneous random graphs

Christoph Koch  Institute of Discrete Mathematics
Graz University of Technology, 8010 Graz, Austria<EMAIL_ADDRESS>and
Johannes Lengler  Institute of Theoretical Computer Science
ETH Zürich, 8092 Zürich, Switzerland<EMAIL_ADDRESS>
###### Abstract.

Geometric inhomogeneous random graphs (GIRGs) are a model for scale-free
networks with underlying geometry. We study bootstrap percolation on these
graphs, which is a process modelling the spread of an infection of vertices
starting within a (small) local region. We show that the process exhibits a
phase transition in terms of the initial infection rate in this region. We
determine the speed of the process in the supercritical case, up to lower
order terms, and show that its evolution is fundamentally influenced by the
underlying geometry. For vertices with given position and expected degree, we
determine the infection time up to lower order terms. Finally, we show how
this knowledge can be used to contain the infection locally by removing
relatively few edges from the graph. This is the first time that the role of
geometry on bootstrap percolation is analysed mathematically for geometric
scale-free networks.

Most of the research was conducted during the first author’s stay at ETH
Zürich. The first author is supported by Austrian Science Fund (FWF): P26826
and W1230.

Keywords: _geometric inhomogeneous random graphs, scale-free network,
bootstrap percolation, localized infection process, metastability threshold_
Mathematics Subject Classification: 05C80, 05C82, 60C05, 60K35, 91D25.

##  1\. Introduction

One of the most challenging and intriguing questions about large real-world
networks is how activity spreads through the network. “Activity” in this
context can mean many things, including infections in a population network,
opinions and rumours in social networks, viruses in computer networks, action
potentials in neural networks, and many more. While all these networks seem
very different, in the last two decades there was growing evidence that most
of them share fundamental properties [4, 24]. The most famous property is that
the networks are _scale-free_ , i.e. the degrees follow a power-law
distribution $\Pr[\deg(v)\geq d]\approx d^{1-\beta}$, typically for some
$2<\beta<3$. Other properties include a large connected component which is a
small world (poly-logarithmic diameter) and an ultra-small world (constant or
poly-loglog average distance), that the networks have small separators and a
large clustering coefficient. We refer the reader to [15] for more detailed
discussions.

Classical models for random graphs fail to have these common properties. For
example, Erdős-Rényi graphs or Watts-Strogatz graphs do not have power-law
degrees, while Chung-Lu graphs and preferential attachment (PA) graphs fail to
have large clustering coefficients or small separators. The latter properties
typically arise in real-world network from an underlying geometry, either
spatial or more abstract, e.g., two nodes in a social networks might be
considered “close” if they share similar professions or hobbies. It is well-
known that in real-world networks the spread of activity (of the flu, of viral
marketing, …) is crucially governed by the underlying spatial or abstract
geometry [41]. For this reason, the explanatory power of classical models is
limited in this context.

In recent years models have been developed which overcome the previously
mentioned limitations, most notably _hyperbolic random graphs_ (HypRGs) [13,
12, 10, 44] and their generalization _geometric inhomogeneous random graphs_
(GIRGs) [15], and _spatial preferential attachment_ (SPA) models [2, 22, 35].
Apart from the power-law exponent $\beta$, these models come with a second
parameter $\alpha>1$, which models how strongly the edges are predicted by
their distance. Due to their novelty, there are only very few theoretical
results on how the geometry impacts the spreading of activity through these
networks.

In this paper we make a first step by analysing a specific process, _bootstrap
percolation_ [20], on the recent and very general GIRG model. In this process,
an initial set of _infected_ or _active_ vertices (the bootstrap) iteratively
recruits all vertices which have at least $k$ infected neighbours, where
$k\geq 2$ is a parameter. It was originally developed to model various
physical phenomena (see [1] for a short review), but has by now also become an
established model for the spreading of activity in networks, for example for
the spreading of beliefs [32, 25, 48, 45], behaviour [30, 31], or viral
marketing [38] in social networks (see also [19]), of contagion in economic
networks [6], of failures in physical networks of infrastructure [52] or
compute architecture [39, 28], of action potentials in neuronal networks (e.g,
[47, 49, 5, 21, 50, 43, 26, 27], see also [40] for a review), and of
infections in life networks [25].

###  1.1. Our contribution

We investigate bootstrap percolation on GIRGs with an expected number of $n$
vertices. We fix a ball $B$ in the underlying geometric space, and we form the
bootstrap by infecting each vertex in $B$ independently with probability
$\rho$. In this way, we model that an infection (a rumour, an opinion, …)
often starts in some local region, and from there spreads to larger parts of
the network. In Theorem 1 we determine a threshold $\rho_{c}$ such that in the
_supercritical case_ $\rho\gg\rho_{c}$ whp111with high probability, i.e. with
probability tending to $1$ as $n\to\infty$ a linear fraction of the graph is
infected eventually, and in the _subcritical case_ $\rho\ll\rho_{c}$ infection
ceases immediately. In the _critical case_ $\rho=\Theta(\rho_{c})$ both
options occur with non-vanishing probability: if there are enough (at least
$k$) “local hubs” in the starting region, i.e. vertices of relatively large
expected degree, then they become infected and facilitate the process. Without
such local hubs the initial infection is not dense enough, and comes to a
halt.

For the supercritical case, we show that it only takes $O(\log\log n)$ rounds
until a constant fraction of all vertices is active, and we determine the
number of rounds until this happens up to a factor $1\pm o(1)$ in Theorem 2.
For the matching lower bound in this result, we need the technical condition
$\alpha>\beta-1$, i.e. edge-formation may not depend too weakly on the
geometry. Notably, if the starting region $B$ is sufficiently small then the
number of rounds agrees (up to minor terms) with the average distance in the
network. In particular, it does not depend on the infection rate $\rho$, as
long as $\rho$ is supercritical.

Finally we demonstrate that the way activity spreads is strongly governed by
the geometry of the process, again under the assumption $\alpha>\beta-1$.
Starting from $B$, the activity is carried most quickly by local hubs. Once
the local hubs in a region are infected, they pass on their infection _(i)_ to
other hubs that are even further away, and _(ii)_ locally to nodes of
increasingly lower degree, until a constant fraction of all vertices the
region is infected. Indeed, given a vertex $v$ (i.e. given its expected degree
and its distance from $B$), and assuming that $v$ is not too close to $B$, we
can predict whp (Theorem 4) in which round it will turn active, again up to a
factor $1\pm o(1)$. In real applications such knowledge is invaluable: for
example, assume that a policy-maker only knows initial time and place of the
infection, i.e. she knows the region $B$ and the current round $i$. In
particular, she does not know $\rho$, she does not know the graph, and she has
no detailed knowledge about who is infected. Then we show that she is able to
identify a region $B^{\prime}$ in which the infection can be quarantined. In
other words, by removing (from round $i$ onwards) all edges crossing the
boundary of $B^{\prime}$ whp the infection remains contained in $B^{\prime}$.
The number of edges to be deleted is relatively small: it can be much smaller
than $n$ (in fact, any function $f(n)=\omega(1)$ can be an upper bound, if $i$
and ${\operatorname{Vol}\\!\left(B\right)}$ are sufficiently small), and it is
even much smaller than the number of edges _inside_ of $B^{\prime}$, as was
already noted in [15].

###  1.2. Related work

The GIRG model was introduced in [15], and we rely on many results from this
paper. The average distance of a GIRG (which, as we show, agrees with the time
until the bootstrap percolation process has infected a constant portion of all
vertices) was determined in [16] in a much more general setup.

Bootstrap percolation has been intensively studied theoretically and
experimentally on a multitude of networks, including trees [20, 9], lattices
[3, 8], Erdős-Rényi graphs [36], various geometric graphs [49, 42, 14, 29],
and scale-free networks [23, 11, 7, 38]. On geometric scale-free networks
there are some experimental results [18], but little is known theoretically.
Recently, Candellero and Fountoulakis [17] determined the threshold for
bootstrap percolation on HypRGs (in the threshold case $\alpha=\infty$, cf.
below), but they assumed that the bootstrap is uniformly sampled from all
vertices, and not from a geometric region as in our paper. In particular, in
this case the bootstrap needs to be polynomial in $n$ to start an infection,
while in our setting every ball which contains an expected number of
$\omega(1)$ vertices can initiate a large infection whp. Also, due to their
setup the authors did not investigate how activity spreads along the geometry
of the ground space.

While there is plenty of experimental literature and also some mean-field
heuristics on other activity spreading processes on geometric scale-free
networks (e.g., [51, 53, 34, 54, 33, 46]), rigorous mathematical treatments
are non-existent with the notable exception of [37], where rumour spreading is
analysed in an SPA model with a push and a push&pull protocol.

##  2\. Model and notation

###  2.1. Graph model

A GIRG is a graph $G=(V,E)$ where both the vertex set $V$ and the edge set $E$
are random. Each vertex $v$ is represented by a pair $(x_{v},w_{v})$
consisting of a _position_ $x_{v}$ (in some _ground space_) and a _weight_
$w_{v}\in\mathbb{R}_{>0}$.

####  2.1.1. Ground space and positions

We fix a (constant) dimension $d\geq 1$ and consider the $d$-dimensional torus
$\mathbb{T}^{d}=\mathbb{R}^{d}/\mathbb{Z}^{d}$ as the ground space. We usually
think of it as the $d$-dimensional cube $[0,1]^{d}$ where opposite boundaries
are identified and measure distances by the $\infty$-norm on $\mathbb{T}^{d}$,
i.e. for $x,y\in[0,1]^{d}$ we define

$\|x-y\|:=\max_{1\leq i\leq d}\min\\{|x_{i}-y_{i}|,1-|x_{i}-y_{i}|\\}.$

The set of vertices and their positions are given by a homogeneous Poisson
point process on $\mathbb{T}^{d}$ with intensity
$n\in\mathbb{N}$.222Throughout the paper, all Landau notation will be used
with respect to $n$. For example, the notation $x=O(1)$ means that there is
$n_{0}>0$ and an absolute constant $C>0$ that depends only the constant
parameters of the GIRG model, such that $x\leq C$ for all $n\geq n_{0}$. More
formally, for any (Lebesgue-)measurable set $B\subseteq\mathbb{T}^{d}$, let
${V}{}{{\cap\,B}}$ denote (with slight abuse of notation) the set of vertices
with positions in $B$. Then $|{V}{}{{\cap\,B}}|$ is Poisson distributed with
mean $n{\operatorname{Vol}\\!\left(B\right)}$, i.e. for any integer $m\geq 0$
we have

$\Pr\left[|{V}{}{{\cap\,B}}|=m\right]=\Pr[\mathrm{Po}\left(n{\operatorname{Vol}\\!\left(B\right)}\right)=m]=\frac{\left(n{\operatorname{Vol}\\!\left(B\right)}\right)^{m}\exp(-n{\operatorname{Vol}\\!\left(B\right)})}{m!},$

and if $B$ and $B^{\prime}$ are disjoint measurable subsets of
$\mathbb{T}^{d}$ then $|{V}{}{{\cap\,B}}|$ and $|{V}{}{{\cap\,B^{\prime}}}|$
are independent. Note in particular that the total number of vertices $|V|$ is
Poisson distributed with mean $n$, i.e. it is also random. An important
property of this process is the following: Given a vertex $v=(x_{v},w_{v})$,
if we condition on $x_{v}\in B$, where $B$ is some measurable subset of
$[0,1]^{d}$, then the position $x_{v}$ is uniformly distributed in $B$.

####  2.1.2. Weights

For each vertex, we draw independently a weight from some distribution
$\mathcal{D}$ on $\mathbb{R}_{>0}$. We say that the weights follow a _weak
power-law_ for some exponent $\beta\in(2,3)$ if a $\mathcal{D}$-distributed
random variable $D$ satisfies the following two conditions: There is a
constant $w_{\text{min}}\in\mathbb{R}_{>0}$ such that $\Pr\left[D\geq
w_{\text{min}}\right]=1$, and for every constant $\gamma>0$ there are
constants $0<c_{1}\leq c_{2}$ such that

$c_{1}w^{1-\beta-\gamma}\leq\Pr\left[D\geq w\right]\leq
c_{2}w^{1-\beta+\gamma}$ (1)

for all $w\geq w_{\text{min}}$. If this condition is also satisfied for
$\gamma=0$, then we say that the weights follow a _strong power-law_.

####  2.1.3. Edges

Next we fix an $\alpha\in\mathbb{R}_{>1}\cup\\{\infty\\}$. Then two distinct
vertices $u=(x_{u},w_{u})$ and $v=(x_{v},w_{v})$ form an edge independently of
all other pairs with probability $p(x_{u},x_{v},w_{u},w_{v})$, where the
function $p$ satisfies

$p(x_{u},x_{v},w_{u},w_{v})=\Theta(1)\min\left\\{\left(\frac{w_{u}w_{v}}{\|x_{u}-x_{v}\|^{d}n}\right)^{\alpha},1\right\\},$
(2)

if $\alpha<\infty$. In the _threshold model_ $\alpha=\infty$ we instead
require that $p$ satisfies

$p(x_{u},x_{v},w_{u},w_{v})=\begin{cases}\Omega(1)&\text{ if
}\|x_{u}-x_{v}\|\leq C_{1}\left(\frac{w_{u}w_{v}}{n}\right)^{1/d}\\\ 0&\text{
if }\|x_{u}-x_{v}\|>C_{2}\left(\frac{w_{u}w_{v}}{n}\right)^{1/d}\end{cases}$
(3)

for some constants $0<C_{1}\leq C_{2}$ . Note that for $C_{1}\neq C_{2}$ the
edge probability may be arbitrary in the interval
$\left(C_{1}\left(\frac{w_{u}w_{v}}{n}\right)^{1/d},C_{2}\left(\frac{w_{u}w_{v}}{n}\right)^{1/d}\right)$.

###  2.2. Bootstrap percolation

Let $k\geq 2$ be a constant, let $B_{0}\subseteq\mathbb{T}^{d}$ be measurable,
and let $0\leq\rho\leq 1$. Then the bootstrap percolation process with
_threshold $k$_, _starting region $B_{0}$_, and _initial infection rate
$\rho$_ is the following process. For every integer $i\geq 0$ there is a set
${V}^{{\leq i}}{}{}\subseteq V$ of vertices which are _infected_ (or _active_)
at time $i$. The process starts with a random set ${V}^{{\leq 0}}{}{}\subseteq
V$ which contains each vertex in ${V}{}{{\cap\,B_{0}}}$ independently with
probability $\rho$, and which contains no other vertices. Then we define
iteratively

${V}^{{\leq i+1}}{}{}:={V}^{{\leq i}}{}{}\cup\left\\{v\in V\;\middle|\;\text{
$v$ has at least $k$ neighbours in ${V}^{{\leq i}}{}{}$}\right\\}$

for all $i\geq 0$. Moreover, we set
${V}^{{\leq\infty}}{}{}:=\bigcup_{i\in\mathbb{N}}{V}^{{\leq i}}{}{}$.

We denote by $\nu:=n{\operatorname{Vol}\\!\left(B_{0}\right)}$ the expected
number of vertices in $B_{0}$. Throughout the paper we will assume that
$B_{0}$ is a ball, which is – without loss of generality due to symmetry of
$\mathbb{T}^{d}$ – centred at $0$. Moreover, we will assume that
$\nu=\omega(1)$.

###  2.3. Further notation

We often consider subsets of the vertex sets which satisfy some restrictions
on their weights, positions, or activity. We use the following notation
throughout the paper: For a weight $w\in\mathbb{R}_{>0}$, a measurable set
$B\subseteq\mathbb{T}^{d}$, and a time $i\geq 0$ we set

${V}_{\geq w}^{{\leq i}}{}{{\cap\,B}}:=\left\\{u=(x_{u},w_{u})\in
V\;\middle|\;w_{u}\geq w,x_{u}\in B,u\in{V}^{{\leq i}}{}{}\right\\}.$

All three types of restrictions are optional. Moreover, we use the superscript
“$(=i)$” to describe vertices which are infected in round $i$, i.e.
${V}^{{=i}}{}{}:={V}^{{\leq i}}{}{}\setminus{V}^{{\leq i-1}}{}{}$ and
${V}^{{=0}}{}{}:={V}^{{\leq 0}}{}{}$ etc. Furthermore, the index “$\geq w$”
may be replaced by “$<w$” or “$\in[w,w^{\prime})$”, with the obvious meaning.
Additionally, we denote the neighbourhood of a vertex $v\in V$ by
${N}{(v)}{}:=\left\\{u\in V\;\middle|\;\\{u,v\\}\in E\right\\}$ and this
notation may be modified by the same three types of restrictions, i.e.

${N}_{\geq w}^{{\leq i}}{(v)}{{\cap\,B}}:=N(v)\cap{V}_{\geq w}^{{\leq
i}}{}{{\cap\,B}}.$

For any two sets of vertices $U_{1}$ and $U_{2}$, we denote the set of edges
between them by
$E\left(U_{1},U_{2}\right):=\left\\{e=\\{u_{1},u_{2}\\}\;\middle|\;u_{1}\in
U_{1},u_{2}\in U_{2}\right\\}$. For a vertex $v\in V$, we define its
_infection time_ as $L_{v}:=\inf\left\\{i\geq 0\;\middle|\;v\in{V}^{{\leq
i}}{}{}\right\\}$ and $L_{v}:=\infty$ if the infimum does not exist.

For any $\lambda\geq 0$ and any closed ball $B\subseteq\mathbb{T}^{d}$ of
radius $r\geq 0$ centred at $0$ we denote by $\lambda B$ the closed ball of
radius $\lambda r$ around $0$.

Since it occurs frequently in our proofs, we abbreviate
$\zeta:=1/(\beta-2)>1$. For all $0<\varepsilon<\zeta$ and all $i\geq 0$, we
set

$\displaystyle{\nu}_{0}$ $\displaystyle:=\nu$ and
$\displaystyle{\nu}_{i}:={\nu}_{i}(\varepsilon)$
$\displaystyle:={\nu}_{0}^{(\zeta-\varepsilon)^{i}},$
$\displaystyle\widetilde{\nu}_{0}:=\widetilde{\nu}_{0}(\varepsilon)$
$\displaystyle:=\nu^{(\beta-1)/(\beta-2)+\varepsilon}$ and
$\displaystyle\widetilde{\nu}_{i}:=\widetilde{\nu}_{i}(\varepsilon)$
$\displaystyle:=\widetilde{\nu}_{0}^{(\zeta+\varepsilon)^{i}}$

We define ${B}_{i}:={B}_{i}(\varepsilon)$ and
$\widetilde{B}_{i}:=\widetilde{B}_{i}(\varepsilon)$ to be the closed ball
centred around $0$ of volume $\min\\{{\nu}_{i}(\varepsilon)/n,1\\}$ and
$\min\\{\widetilde{\nu}_{i}(\varepsilon)/n,1\\}$, respectively. Note that
${B}_{i}(\varepsilon)\subseteq\widetilde{B}_{i}(\varepsilon^{\prime})$ for all
$i\geq 0$ and all $0<\varepsilon,\varepsilon^{\prime}<\zeta$. The balls
${B}_{i}$ and $\widetilde{B}_{i}$ will play a crucial role in describing how
fast the infection spreads, cf. Theorem 17 and Theorem 19.

Given any constant $\eta>0$, we define the functions
$\hat{w}_{-}^{(\eta)},\hat{w}_{+}^{(\eta)}:\mathbb{R}_{\geq
0}\to\mathbb{R}_{\geq 0}$ by

$\displaystyle\hat{w}_{-}(\mu):=\hat{w}_{-}^{(\eta)}(\mu):=\mu^{1/(\beta-1+\eta)}$
and
$\displaystyle\hat{w}_{+}(\mu):=\hat{w}_{+}^{(\eta)}(\mu):=\mu^{1/(\beta-1-\eta)}.$

As we will see in Lemma 15, in a region with an expected number of
$\mu=\omega(1)$ vertices, whp the largest weight that occurs in this region is
in $[\hat{w}_{-}(\mu),\hat{w}_{+}(\mu)]$.

In general we will be interested in results for large values of $n$, and in
particular we use the phrase _with high probability_ (whp) to mean with
probability tending to $1$ as $n\to\infty$. Moreover, any unspecified limits
and asymptotics will be with respect to $n\to\infty$. In the proofs, for the
sake of readability, we will not state each time when we use inequalities that
only hold for sufficiently large $n$. For example, we will use inequalities
like $\nu>2$ without further comment although they are only true for
sufficiently large $n$.

Furthermore, all constants hidden by Landau-notation are positive. We often
use statements that depend on parameters $\varepsilon,\eta>0$. In this case,
by the notation $O(\varepsilon),O(\eta)$ etc. we implicitly mean that the
hidden constants only depend on the parameters
$d,\alpha,\beta,w_{\text{min}},\mathcal{D},\rho$, and $k$ of the model, but
not on $\varepsilon$ or $\eta$. To enhance readability, in all proofs we stick
to the convention that if $\varepsilon$ and $\eta$ occur together, then
$\eta=\eta(\varepsilon)>0$ is chosen so small that $C\eta<c\varepsilon$ for
all concrete constants $C$ and $c$ in our proofs that depend only on the model
parameters. In particular, the expression $\Omega(\varepsilon)-O(\eta)$ will
be positive for all hidden constants that appear in our proofs.

Throughout the paper we will ignore all events of probability $0$. For
example, we will always assume that $V$ is a finite set, and that all vertices
in $V$ have different positions. Furthermore, whenever it does not affect the
argument, we omit floors and ceilings.

##  3\. Main results

First of all we show that bootstrap percolation on a $GIRG$ has at threshold
with respect to the initial infection rate $\rho$. Since hyperbolic random
graphs are a special instance of GIRGs, this contains in particular the result
of [17] on (threshold) hyperbolic random graphs, where the case $\nu=n$ was
studied.

######  Theorem 1.

Consider a bootstrap percolation process on a GIRG $G=(V,E)$ with initial
infection rate $\rho=\rho(n)\in[0,1]$. We set

$\rho_{c}=\rho_{c}(n):=\nu^{-\frac{1}{\beta-1}}.$

If the weights follow a strong power-law, then:

  1. (i)

If $\rho=\omega(\rho_{c})$, then $|{V}^{{\leq\infty}}{}{}|=\Theta(n)$ whp.

  2. (ii)

If $\rho=\Theta(\rho_{c})$, then $|{V}^{{\leq\infty}}{}{}|=\Theta(n)$ with
probability $\Omega(1)$, but also ${V}^{{\leq\infty}}{}{}={V}^{{\leq 0}}{}{}$
with probability $\Omega(1)$.

  3. (iii)

If $\rho=o(\rho_{c})$, then ${V}^{{\leq\infty}}{}{}={V}^{{\leq 0}}{}{}$ whp.

If the weights follow a weak power-law, then:

  1. (iv)

If there is a constant $\delta>0$ such that $\rho\geq\rho_{c}^{1+\delta}$,
then $|{V}^{{\leq\infty}}{}{}|=\Theta(n)$ whp.

  2. (v)

If there is a constant $\delta>0$ such that $\rho\leq\rho_{c}^{1-\delta}$,
then ${V}^{{\leq\infty}}{}{}={V}^{{\leq 0}}{}{}$ whp.

Whenever we refer to the _supercritical_ regime we mean case (i) and (iv).
Similarly, (iii) and (v) form the _subcritical_ regime and (ii) is the
_critical_ regime. Note in particular that there is a supercritical regime
regardless of how small the expected number $\nu$ of vertices in the starting
region is, provided that $\nu=\omega(1)$. This is in sharp contrast to non-
geometric graphs like Chung-Lu graphs, where the expected size of the
bootstrap must be polynomial in $n$ (if the bootstrap is chosen at random).

Indeed the proof of Theorem 1 will grant a deeper insight into the evolution
of the process. Since the process whp stops immediately in the subcritical
regime, we may restrict ourselves to the other cases. We show a doubly
logarithmic upper bound on the number of rounds until a constant fraction of
all vertices are infected. Furthermore, we prove that this bound is tight up
to minor order terms if the influence of the underlying geometry on the random
graphs is sufficiently strong ($\alpha>\beta-1$). Remarkably, the bounds do
not depend on the initial infection rate $\rho$, as long as $\rho$ is
supercritical. Moreover, if the expected number $\nu$ of vertices in the
starting region is sufficiently small (if $\log\log\nu=o(\log\log n)$), then
the bound coincides with the average distance in the graph, again up to minor
order terms.

######  Theorem 2.

In the situation of Theorem 1, let $\varepsilon>0$ be constant and set

$i_{\infty}:=\frac{\log\log_{\nu}n+\log\log n}{|\log(\beta-2)|}.$

Then in the supercritical regime whp, and in the critical regime with
probability $\Omega(1)$ we have
$|{V}^{{\leq(1+\varepsilon)i_{\infty}}}{}{}|=\Theta(n)$.
If furthermore $\alpha>\beta-1$ and $\nu=n^{o(1)}$ then in all regimes we have
whp $|{V}^{{\leq(1-\varepsilon)i_{\infty}}}{}{}|=o(n)$.

The proof of Theorem 1 and Theorem 2 can be found in Section 8.

In fact, we can still refine the statement of Theorem 2 tremendously, at least
in the case $\alpha>\beta-1$. In the following, we determine for every fixed
vertex $v$ its infection time $L_{v}$, up to minor order terms (with the
restriction that $v$ may not be too close to the starting region). We will
show that it is given by the following expression (see also Remark 6 below).

######  Definition 3.

For any $x\in\mathbb{T}^{d}\setminus B_{0}$ and $w\in\mathbb{R}_{>0}$ we
define

$\Lambda{(x,w)}:=\begin{cases}\max\left\\{0,\
\frac{\log\log_{\nu}\left(\|x\|^{d}n/w\right)}{|\log(\beta-2)|}\right\\},&\text{
if }w>(\|x\|^{d}n)^{1/(\beta-1)},\\\ \\\
\frac{2\log\log_{\nu}(\|x\|^{d}n)-\log\log_{\nu}w}{|\log(\beta-2)|},&\text{ if
}w\leq(\|x\|^{d}n)^{1/(\beta-1)}.\end{cases}$ (4)

In the first case we use the convention that the second term is $-\infty$ if
$\|x\|^{d}n/w<1$, and thus does not contribute to the maximum.

Note that in the second case, the sign of $\log\log_{\nu}w$ may be either
positive or negative. However, then we have the lower bound
$\Lambda{(x,w)}\geq\log\log_{\nu}(\|x\|^{d}n)/|\log(\beta-2)|+O(1)$ due to the
upper bound of $w$ and thus, in particular $\Lambda{(x,w)}\geq 0$, since
$x\in\mathbb{T}^{d}\setminus B_{0}$.

######  Theorem 4.

Assume we are in the situation of Theorem 1 in the supercritical regime (i) or
(iv). Let $v=(x_{v},w_{v})$ be any fixed vertex such that
$x_{v}\in\mathbb{T}^{d}\setminus B_{0}$, $w_{v}=\omega(1)$ and
$\Lambda{(x_{v},w_{v})}\leq\log_{2}(\|x_{v}\|^{d}n/\widetilde{\nu}_{0})$. Then
whp

$L_{v}\leq(1+o(1))\Lambda{(x_{v},w_{v})}+O(1).$ (5)

If additionally $\alpha>\beta-1$ then we also have whp

$L_{v}\geq(1-o(1))\Lambda{(x_{v},w_{v})}-O(1).$ (6)

As in Theorem 2, the bounds do not depend on the initial infection rate
$\rho$, as long as it is supercritical. Before we come to applications, we
give two explanatory remarks on Theorem 4.

######  Remark 5.

The technical restrictions in Theorem 4 are necessary: if a vertex has weight
$w_{v}=O(1)$ then the number of neighbours is Poisson distributed with mean
$\Theta(w_{v})$ (see Lemma 12), so $v$ is even isolated with probability
$\Omega(1)$. In particular, we cannot expected that whp $v$ is ever infected.

The restriction
$\Lambda{(x_{v},w_{v})}\leq\log_{2}(\|x_{v}\|^{d}n/\widetilde{\nu}_{0})$
ensures that $v$ is not too close to the starting region. If $v$ is too close,
then it may have neighbours inside of $B_{0}$, and in this case it does depend
on $\rho$ when they are infected. (And of course, this process iterates.) The
term $\log_{2}(\|x_{v}\|^{d}n/\widetilde{\nu}_{0})$ is not tight and could be
improved at the cost of more technical proofs. However, there are already
rather few vertices that violate the condition
$\Lambda{(x_{v},w_{v})}\leq\log_{2}(\|x_{v}\|^{d}n/\widetilde{\nu}_{0})$. For
example, recall that it only takes $O(\log\log n)$ steps until a constant
fraction of all vertices are infected. At this time, we only exclude vertices
which satisfy $\|x_{v}\|^{d}n\leq\widetilde{\nu}_{0}\cdot(\log n)^{O(1)}$, so
the expected number of affected vertices is also at most
$\widetilde{\nu}_{0}\cdot(\log n)^{O(1)}$. Even this is a gross overestimate,
since the vertices close to the origin have much smaller infection times
$L_{v}$, and thus only very few of them are affected by the condition.

######  Remark 6.

The first case in Definition 3 is not needed if we restrict ourselves to
vertices as they typically appear in GIRGs. More precisely, as we will show in
Lemma 15, Section 5, whp all vertices in
$v=(x_{v},w_{v})\in{V}{}{{\cap\,(\mathbb{T}^{d}\setminus B_{0})}}$ satisfy
$w_{v}\leq(\|x_{v}\|^{d}n)^{1/(\beta-1-\eta)}$ where $\eta>0$ is an arbitrary
constant. In the border case $(\|x_{v}\|^{d}n)^{1/(\beta-1)}\leq
w_{v}\leq(\|x_{v}\|^{d}n)^{1/(\beta-1-\eta)}$ both expressions in (4) agree up
to additive constants, i.e.

$\Lambda{(x_{v},w_{v})}=\frac{2\log\log_{\nu}(\|x_{v}\|^{d}n)-\log\log_{\nu}w_{v}}{|\log(\beta-2)|}\pm
O(1).$ (7)

Therefore, we could also use (7) as definition for $\Lambda{}$ if we would
exclude vertices which are unlikely to exist in Theorem 4 .

Finally, we give a strategy how to contain the infection within a certain
region when only the starting set and the current round a known, but not the
set of infected vertices. Note that the number of edges that need to be
removed is substantially smaller than the expected number of vertices
$\widetilde{\nu}_{i}$ in the containment area $\widetilde{B}_{i}$. The proof
can be found in Section 6.2.

######  Corollary 7.

Assume that we are in the situation of Theorem 1, and that $\alpha>\beta-1$.
If the starting region $B_{0}$ is known, then by removing all edges crossing
the boundary of $\widetilde{B}_{i}$ before round $i+1$, whp the infection is
contained in $\widetilde{B}_{i}$. The expected number of edges crossing the
boundary of $\widetilde{B}_{i}$ is
$\widetilde{\nu}_{i}^{\max\\{3-\beta,1-1/d\\}+o(1)}$.

##  4\. Tools

In this section we collect basic tools and observations that we use throughout
the paper. We start with a fact which often allows us to treat the case
$\alpha=\infty$ along with the case of finite $\alpha$ without case
distinction.

######  Observation 8.

For every function $p$ satisfying (3) and every $\alpha\in\mathbb{R}_{>1}$,
there is a function $\bar{p}$ satisfying (2) such that
$\bar{p}(x_{1},x_{2},w_{1},w_{2})\geq p(x_{1},x_{2},w_{1},w_{2})$ for all
$x_{1},x_{2}\in\mathbb{T}^{d}$ and all $w_{1},w_{2}\geq w_{\text{min}}$.

In other words, GIRGs in the threshold case $\alpha=\infty$ are dominated by
GIRGs with finite $\alpha$. In particular, whenever we prove an upper bound on
the number of active vertices that holds for all GIRGs with finite $\alpha$,
the same upper bound also holds for threshold GIRGs.

In [15], GIRGs were defined with a fixed number of vertices, while we assume
the set of vertices to be given by a homogeneous Poisson point process. Our
choice allows for slightly less technical proofs. In particular, one of the
benefits of the Poisson point process is the following elementary fact.

######  Fact 9.

Let $\lambda\in\mathbb{R}_{\geq 0}$ and let $X$ be a Poisson distributed
random variable with mean $\lambda$. Furthermore, given some $0\leq q\leq 1$,
let $Y$ be a random variable which conditioned on $\\{X=x\\}$, for any
$x\in\mathbb{N}_{0}$, is the sum of $x$ independent Bernoulli random variables
with mean $q$. Then $Y$ is Poisson distributed with mean $q\lambda$.

This means that for instance $|{N}_{\geq w}{(v)}{{\cap\,B}}|$ is Poisson
distributed with mean $nq$, where $q$ denotes the probability that a vertex
$u$ with random position $x_{u}$ and random weight $w_{u}$ satisfies
$w_{u}\geq w$ and $x_{u}\in B$, and is a neighbours of $v$. We will apply this
observation throughout the paper without giving explicit reference.

An easy way to bound the expectation

######  Lemma 10 (Lemma 4.1 in [16]).

Let $0\leq w_{0}<w_{1}$, and let $f:\mathbb{R}_{\geq 0}\to\mathbb{R}_{\geq 0}$
be a piecewise continuously differentiable function. Then in any finite set
$V$ of weighted vertices, we have

$\sum_{v\in V,w_{0}\leq w_{v}<w_{1}}f(w_{v})\;=\;f(w_{0})|V_{\geq
w_{0}}|\;-\;f(w_{1})|V_{\geq w_{1}}|\;+\;\int_{w_{0}}^{w_{1}}|V_{\geq
w}|\frac{d}{dw}f(w)dw.$

Note in particular that if $f(0)=0$, then, by using $w_{0}=0$ and
$w_{1}>\max\\{w_{v}\mid v\in V\\}$, we have

$\sum_{v\in V}f(w_{v})=\int_{0}^{w_{1}}|V_{\geq
w}|\frac{d}{dw}f(w)dw=\int_{0}^{\infty}|V_{\geq w}|\frac{d}{dw}f(w)dw.$

The lemma is actually formulated slightly more general than Lemma 4.1 in [16].
First, in [16] the lemma was only formulated if $V$ is the vertex set of a
GIRG, but their proof does not use this restriction. Second, $f$ was assumed
to be everywhere continuously differentiable. However, our version follows
immediately by applying Lemma 4.1 in [16] to every continuously differentiable
piece, and by noting that all the intermediate terms cancel out.333Formally
speaking, the term $\frac{d}{dw}f(w)$ is a distribution and not a function if
$f$ is not differentiable everywhere, and the integral is then to be
understood as evaluation of the distribution. However, in our simple
applications we may just ignore the values where $f$ is not differentiable.

The next lemma spells out an almost trivial calculation, but since it is
ubiquitous in our proofs, we state it as a lemma nevertheless. In our
applications, $g(w)$ is typically the number of vertices of weight at least
$w$ (possibly with additional restrictions), and $f$ is the probability that
such a vertex has a certain property (e.g., that it forms an edge with some
fixed $v$). After application of Lemma 10, this almost always leads to an
integral as given in (8) below.

######  Lemma 11.

Let $g:\mathbb{R}_{\geq 0}\to\mathbb{R}_{\geq 0}$ be a non-zero monomial, and
let $f:\mathbb{R}_{\geq 0}\to\mathbb{R}_{\geq 0}$ be continuous and piecewise
a non-zero monomial with non-negative exponent, for a finite number of pieces.
Moreover, assume that there is $\tilde{w}$ such that the exponent of $w$ in
$f(w)g(w)$ is strictly larger than $0$ for $w<\tilde{w}$, and strictly smaller
than $0$ for $w>\tilde{w}$. Then for every $w_{0}\leq\tilde{w}\leq w_{1}$,

$\int_{w_{0}}^{w_{1}}g(w)\frac{d}{dw}f(w)dw=O(f(\tilde{w})g(\tilde{w})).$ (8)

Moreover, assume that _(i)_ the exponent of $f$ is non-zero in an interval
$[(1-\Omega(1))\tilde{w},\tilde{w}]\subseteq[w_{0},\tilde{w}]$, _or_ _(ii)_
the exponent of $f$ is non-zero in an interval
$[\tilde{w},(1+\Omega(1))\tilde{w}]\subseteq[\tilde{w},w_{1}]$. Then the
$O(\cdot)$ in (8) may be replaced by $\Theta(\cdot)$.

###### Proof.

Let $g(w)=Cw^{r}$. Let us first assume that, by continuity, $f$ satisfies
$f(w)=C_{0}w^{s_{0}}$ for $w\leq\tilde{w}$ and $f(w)=C_{1}w^{s_{1}}$ for
$w\geq\tilde{w}$, i.e. that $f$ consists of only two pieces. Then by
assumption $r+s_{0}>0>r+s_{1}$. We first consider the lower part of the
integral. If $s_{0}=0$ then $(df/dw)(w)=0$ for $w\leq\tilde{w}$, and the
integral from $w_{0}$ to $\tilde{w}$ vanishes. So assume that $s_{0}>0$. Then
$(df/dw)(w)=C_{0}s_{0}w^{s_{0}-1}$, and the antiderivative of $g(df/dw)$ is
$CC_{0}s_{0}/(r+s_{0})w^{r+s_{0}}$. Since $r+s_{0}>0$, this function is
increasing in $w$, and

$\int_{w_{0}}^{\tilde{w}}g(w)\frac{d}{dw}f(w)dw=\frac{CC_{0}s_{0}}{r+s_{0}}\left(\tilde{w}^{r+s_{0}}-w_{0}^{r+s_{0}}\right)=\Theta(f(\tilde{w})g(\tilde{w})-f(w_{0})g(w_{0})).$
(9)

Note that if $w_{0}\leq(1-\Omega(1))\tilde{w}$, then
$f(\tilde{w})g(\tilde{w})-f(w_{0})g(w_{0})=\Omega(f(\tilde{w})g(\tilde{w}))$
since $fg$ is a polynomial with positive exponent $r+s_{0}$ in
$[w_{0},\tilde{w}]$, which proves the additional statement (i).

For the upper part of the integral, we may assume $s_{1}>0$, since otherwise
this part of the integral vanishes. Then $(df/dw)(w)=C_{1}s_{1}w^{s_{1}-1}$,
and the antiderivative of $g(df/dw)$ is $CC_{1}s_{1}/(r+s_{1})w^{r+s_{1}}$.
Note crucially that the sign of this function is negative since $r+s_{1}<0$.
Hence,

$\int_{\tilde{w}}^{w_{1}}g(w)\frac{d}{dw}f(w)dw=\frac{CC_{1}s_{1}}{-(r+s_{1})}\left(\tilde{w}^{r+s_{1}}-w_{1}^{r+s_{1}}\right)=\Theta(f(\tilde{w})g(\tilde{w})-f(w_{1})g(w_{1})).$
(10)

Similarly to the first part, if $w_{1}\geq(1+\Omega(1))\tilde{w}$, then
$f(\tilde{w})g(\tilde{w})-f(w_{1})g(w_{1})=\Omega(f(\tilde{w})g(\tilde{w}))$,
which proves the additional statement (ii). On the other hand, Equation (8)
follows immediately from (9) and (10) by leaving out the negative terms. This
proves the lemma in the case that $f$ consists of only two pieces.

For the case of several pieces, the additional statement follows by
restricting the integral to the two pieces bounded by $\tilde{w}$. For the
upper piece, assume that
$w_{0}=w_{0}^{(1)}<\ldots<w_{0}^{(\lambda)}=\tilde{w}$ are the endpoints of
the different pieces below $\tilde{w}$. Then in the same way as (9), we get

$\int_{w_{0}}^{\tilde{w}}g(w)\frac{d}{dw}f(w)dw=O(\sum_{i=1}^{\lambda}f(w_{0}^{(i)})g(w_{0}^{(i)}))\leq
O(\lambda f(\tilde{w})g(\tilde{w}))=O(f(\tilde{w})g(\tilde{w})),$

since $fg$ is an increasing function in $[w_{0},\tilde{w}]$. The part
$[\tilde{w},w_{1}]$ follows analogously. ∎

##  5\. Basic properties of GIRGs

In this section we collect some basic properties of GIRGs. The first lemma,
taken from [16], tells us that the expected degree of a vertex equals its
weight, up to constant factors. Moreover, it gives the marginal probability
that two vertices $u,v$ of fixed weights but random positions in
$\mathbb{T}^{d}$ are adjacent. This probability remains the same if the
position of one (but not both) of the vertices is fixed. An expert reader may
recognise that it is the same marginal probability as in Chung-Lu random
graphs, cf. [16] for a discussion in depth.

######  Lemma 12 (Lemma 4.4 and Theorem 7.3 in [16]).

Let $v=(x_{v},w_{v})$ be a vertex with fixed weight and position. Then

$\mathbb{E}[\deg(v)]=\Theta(w_{v}).$ (11)

Moreover, let $u=(x_{u},w_{u})$ be a vertex with fixed weight, but with random
position $x_{u}\in\mathbb{T}^{d}$. Then

$\Pr\left[\\{u,v\\}\in E\mid
w_{u},w_{v},x_{v}\right]=\Theta\left(\min\left\\{\frac{w_{u}w_{v}}{n},1\right\\}\right).$
(12)

Note in particular that the right hand side of (12) is independent of $x_{v}$,
so the same formula still applies if also the position $x_{v}$ of $v$ is
randomized.

The next lemma gives a bound on the expected number of neighbours of a fixed
vertex of large weight.

######  Lemma 13.

Let $\eta>0$ be a constant and consider a vertex $v=(x_{v},w_{v})$ with fixed
weight and position. Then for every $w\geq w_{\text{min}}$ we have

  1. (a)

$\mathbb{E}[|{N}_{\geq
w}{(v)}{}|]=O(\min\\{w_{v}w^{2-\beta+\eta},nw^{1-\beta+\eta}\\})$.
In particular, for a random vertex $u$ we have, independently of $x_{v}$ and
$w_{v}$,

$\Pr[w_{u}\geq w\mid\\{u,v\\}\in E]=O(w^{2-\beta+\eta});$

  2. (b)

$\mathbb{E}[|{N}_{\geq
w}{(v)}{}|]=\Omega(\min\\{w_{v}w^{2-\beta-\eta},nw^{1-\beta-\eta}\\})$.

###### Proof.

(a) By Lemma 12, the probability that a vertex $u$ with fixed weight $w_{u}$
and random position $x_{u}\in\mathbb{T}^{d}$ is adjacent to $v$ is
$\Theta(1)\min\\{w_{u}w_{v}/n,1\\}$. The expected number of vertices of weight
at least $w$ is at most $O(nw^{1-\beta+\eta})$ by the power-law condition (1).
We distinguish two cases. If $ww_{v}\geq n$ then the probability to connect to
any vertex of weight $w$ is $\Theta(1)$, so $\mathbb{E}[|{N}_{\geq
w}{(v)}{}|]=\Theta(\mathbb{E}[|{V}_{\geq w}{}{}|])$, and the claim follows. So
assume $ww_{v}\leq n$. Then by Lemma 10 we can compute the expectation as the
following integral, which we then evaluate using Lemma 11.

$\displaystyle\mathbb{E}[|{N}_{\geq w}{(v)}{}|]$ $\displaystyle\leq
O\left(nw^{1-\beta+\eta}\frac{ww_{v}}{n}+\int_{w}^{\infty}nw_{u}^{1-\beta+\eta}\frac{d}{dw_{u}}\min\left\\{\frac{w_{v}w_{u}}{n},1\right\\}dw_{u}\right)$
$\displaystyle\leq O\left(w_{v}w^{2-\beta+\eta}\right).$

We can write both cases uniformly as $\mathbb{E}[|{N}_{\geq w}{(v)}{}|]\leq
O(\min\\{w_{v}w^{2-\beta+\eta},nw^{1-\beta+\eta}\\})$.

The second statement follows because the expected total number of neighbours
of $v$ is $\Theta(w_{v})$. Therefore, the probability that a random neighbour
of $v$ has weight at least $w$ is $\Pr[\\{u,v\\}\in E\wedge w_{u}\geq
w]/\Pr[\\{u,v\\}\in E]=O(w^{2-\beta-\eta})$, as required.

(b) This follows completely analogously to (a), except that we use that the
expected number of vertices of weight at least $w$ is at least
$\Omega(nw^{1-\beta-\eta})$ by the lower bound in the power-law condition (1).
∎

We often need to bound the expected number of neighbours of a given vertex in
some geometric region, which we may do by the following lemma.

######  Lemma 14.

Let $\eta>0$ and $C>1$ be constants, define $m:=\min\\{\alpha,\beta-1-\eta\\}$
and consider a closed ball $B\subseteq\mathbb{T}^{d}$ of radius $r>0$ centred
at $0$. Let $v=(x_{v},w_{v})$ be a vertex with fixed weight and position. Then

$\mathbb{E}\left[|{N}{(v)}{{\cap\,B}}|\right]=O(n{\operatorname{Vol}\\!\left(B\right)})\cdot\begin{cases}\min\left\\{\frac{w_{v}}{n{\operatorname{Vol}\\!\left(B\right)}},1\right\\},&\text{if
}\|x_{v}\|\leq Cr,\\\
\min\left\\{\left(\frac{w_{v}}{\|x_{v}\|^{d}n}\right)^{m},1\right\\}&\text{if
}\|x_{v}\|\geq Cr.\end{cases}$

###### Proof.

In the first case $\|x_{v}\|\leq Cr$, the expected number of vertices in $B$
is $n{\operatorname{Vol}\\!\left(B\right)}$, so $\mu\leq
n{\operatorname{Vol}\\!\left(B\right)}$. On the other hand, the expected
number of neighbours of $v$ is $O(w_{v})$, so
$\mu=O(1)\min\\{w_{v},n{\operatorname{Vol}\\!\left(B\right)}\\}$.

For the second case, as before $\mu\leq
n{\operatorname{Vol}\\!\left(B\right)}$. This proves the claim in the case
$w_{v}\geq\|x_{v}\|^{d}n$, so assume otherwise. Observe that every vertex in
$B$ has distance $\Theta(\|x_{v}\|)$ from $v$, and that the expected number of
vertices in $B$ of weight at least $w$ is
$O(n{\operatorname{Vol}\\!\left(B\right)}w^{1-\beta+\eta})$.

Consider first the case $\alpha<\beta-1-\eta$. Then by Lemma 10,

$\displaystyle\mathbb{E}\left[|{N}{(v)}{{\cap\,B}}|\right]$ $\displaystyle\leq
O\left(n{\operatorname{Vol}\\!\left(B\right)}\min\left\\{\left(\frac{w_{v}}{\|x_{v}\|^{d}n}\right)^{\alpha},1\right\\}\right.$
$\displaystyle\qquad\qquad\left.+\int_{w_{\text{min}}}^{\infty}n{\operatorname{Vol}\\!\left(B\right)}w^{1-\beta+\eta}\frac{d}{dw}\min\left\\{\left(\frac{ww_{v}}{\|x_{v}\|^{d}n}\right)^{\alpha},1\right\\}dw\right).$

Note that the exponent of $w$ in the integrand is always negative, no matter
which value the minimum attains. Moreover, recall that we assumed
$w_{v}<\|x_{v}\|^{d}n$ and hence for $w=w_{\text{min}}$ the minimum is
$O((w_{v}/(\|x_{v}\|^{d}n))^{\alpha})$. Thus by Lemma 11 (with
$\tilde{w}=w_{\text{min}}=\Theta(1)$), the integral also evaluates to
$O(n{\operatorname{Vol}\\!\left(B\right)}\cdot\min\\{(w_{v}/(\|x_{v}\|^{d}n))^{\alpha},1\\})$,
as required.

On the other hand, if $\alpha+1-\beta+\eta\geq 0$, then by Observation 8 we
may restrict ourselves to $\alpha<\infty$, so we can estimate using Lemma 10
(with lower bound $0$)

$\displaystyle\mathbb{E}\left[|{N}{(v)}{{\cap\,B}}|\right]$
$\displaystyle=O\left(\int_{0}^{\infty}n{\operatorname{Vol}\\!\left(B\right)}w^{1-\beta+\eta}\frac{d}{dw}\min\left\\{\left(\frac{ww_{v}}{\|x_{v}\|^{d}n}\right)^{\alpha},1\right\\}dw\right).$

This integral evaluates to
$O(n{\operatorname{Vol}\\!\left(B\right)}\cdot(w_{v}/(\|x_{v}\|^{d}n))^{\beta-1-\eta})$,
by Lemma 11 (with $\tilde{w}=\|x_{v}\|^{d}n/w_{v}$). Since we have already
shown that $\mathbb{E}\left[|{N}{(v)}{{\cap\,B}}|\right]\leq
n{\operatorname{Vol}\\!\left(B\right)}$, this proves the claim. ∎

In the last lemma of this section we show that whp there are no vertices whose
weight is much larger than their distance from the origin.

######  Lemma 15.

Let $\eta>0$ be a constant and consider a closed ball
$B\subseteq\mathbb{T}^{d}$ of radius $r>0$ centred at $0$, satisfying
$n{\operatorname{Vol}\\!\left(B\right)}=\Theta(r^{d}n)=\omega(1)$. Then with
probability $1-(r^{d}n)^{-\Omega(\eta)}$ there is no vertex $v=(x_{v},w_{v})$
with $x_{v}\in\mathbb{T}^{d}\setminus B$ and
$w_{v}\geq\hat{w}_{+}(\|x_{v}\|^{d}n)$.

###### Proof.

Let $\hat{n}$ be the number of such vertices. Let $r^{\prime}>r$, then the
probability density to find a vertex $v=(x_{v},w_{v})$ with
$\|x_{v}\|=r^{\prime}$ is equal to the volume of an $r^{\prime}$-sphere around
$0$ that is intersected with $\mathbb{T}^{d}$. By ignoring the intersection,
we can only make the volume larger, so it is at most $O((r^{\prime})^{d-1}n)$.
Moreover, the probability that a vertex has weight at least $w$ is at most
$O(w^{1-\beta+\eta/2})$ by the power-law condition (1) (using
$\gamma=\eta/2$). Hence, by Lemma 10 and Lemma 11 we obtain

$\displaystyle\mathbb{E}\left[\hat{n}\right]$
$\displaystyle=O(1)\int_{r}^{\infty}(r^{\prime})^{d-1}n((r^{\prime})^{d}n)^{(1-\beta+\eta/2)/(\beta-1-\eta)}dr^{\prime}=(r^{d}n)^{-\Omega(\eta)},$

and the statement follows by Markov’s inequality. ∎

##  6\. Evolution of the process

In this section we will prove two theorems which describe the geometrical
evolution of the process in detail. First we show that certain regions cannot
be reached too early in the process, providing an _upper bound on its speed_.
From this we then derive Corollary 7 in Section 6.2. Afterwards, we show that
in the supercritical regime the process will reach certain regions whp in a
given time, yielding a _lower bound on its speed_. This lower bound also
applies in the critical regime if in the first step sufficiently many heavy
vertices were activated, an event which holds with at least constant
probability.

###  6.1. Upper bound on the speed

The key theorem will recursively assert that the process does not infect too
many vertices in certain regions in any round. We formalise this idea by
defining several families of events.

######  Definition 16.

Let $\varepsilon>0$ be a constant and let $\eta=\eta(\varepsilon)>0$ be a
constant which is sufficiently small compared to $\varepsilon$, cf. Section
2.3. Moreover, let $h=h(n)$ be a function satisfying $h(n)=\omega(1)$,
$h(n)=o(\log n)$, and $h(n)=\nu^{o(1)}$. Then we define the following families
of events:

  * •

For all $i\geq 0$

$\mathcal{E}(i):=\\{{V}^{{\leq
i}}{}{{\cap\,(\mathbb{T}^{d}\setminus\widetilde{B}_{i})}}=\emptyset\\},$

in other words, no vertex outside of $\widetilde{B}_{i}$ is activated by time
$i$;

  * •

For all $\ell\geq 0$ and $w\geq w_{\text{min}}$

$\mathcal{F}(\ell,w):=\mathcal{F}_{\varepsilon,\eta,h}(\ell,w):=\left\\{\left|{V}_{\geq
w}^{{\leq\ell}}{}{{\cap\,2^{\ell}\widetilde{B}_{0}}}\right|\leq
h^{\ell}w^{2-\beta+\eta}\widetilde{\nu}_{0}^{1-(\zeta+\varepsilon)^{-\ell}(\beta-1)^{-1}}\right\\},$

and

$\mathcal{F}(\ell):=\mathcal{F}_{\varepsilon,\eta,h}(\ell):=\bigcap_{w^{\prime}\geq
w_{\text{min}}}\mathcal{F}(\ell,w^{\prime}),$

i.e. the number of vertices in $2^{\ell}\widetilde{B}_{0}$ being activated by
time $\ell$ is not “too large”;

  * •

For all $j\geq 0$

$\mathcal{G}(j):=\mathcal{G}_{\varepsilon,\eta,h}(j):=\bigcap_{j^{\prime}=0}^{j}(\mathcal{E}(j^{\prime})\cap\mathcal{F}(j^{\prime})),$

in other words, it is all “good” events up to time $j$ hold.

######  Theorem 17.

Let $\varepsilon,\eta,h$ be given as in Definition 16 and assume
$\alpha>\beta-1$. Then, for sufficiently large $n$,

  1. (a)

$\mathcal{E}(0)$ is always satisfied;

  2. (b)

$\Pr[\mathcal{F}(0)]\geq 1-O(h^{-1})$;

  3. (c)

For all $i\geq 1$ we have

$\Pr\left[\mathcal{E}(i)\;\middle|\;\mathcal{G}(i-1)\right]\geq
1-h^{-\Omega(i)};$

  4. (d)

For all $\ell\geq 1$ we have

$\Pr\left[\mathcal{F}(\ell)\;\middle|\;\mathcal{G}(\ell-1)\right]\geq
1-h^{-\Omega(\ell)};$

  5. (e)

Whp, the events $\mathcal{G}(j)$ hold for all $j\geq 0$;

  6. (f)

For all $i\geq 1$ and $\ell\geq 0$, and for every fixed vertex
$v=(x_{v},w_{v})$ such that $x_{v}\in\mathbb{T}^{d}\setminus
2^{\ell+1}\widetilde{B}_{i-1}$ and $w_{v}\geq w_{\text{min}}$ we have

$\Pr\left[v\in{V}^{{\leq
i+\ell}}{}{}\;\middle|\;\mathcal{G}(i+\ell-1)\right]\leq w_{v}2^{\ell
d}\widetilde{\nu}_{i}^{-(\zeta+\varepsilon)^{-\ell-2}/(\beta-1)}.$

###### Proof.

First note that all statements only become easier if the edge probabilities
are decreased. Hence, by Observation 8 we may restrict ourselves to the case
$\alpha<\infty$, since this case dominates the case $\alpha=\infty$.

To prove (c), (d), and (f), we will use induction on $i+\ell$, where we set
$\ell=0$ and $i=0$ in (c) and (d), respectively. In particular, in order to
prove (c) and (d) for $i,\ell$, we will assume statement (f) for
$i^{\prime},\ell^{\prime}$ as long as $i^{\prime}+\ell^{\prime}\leq i+\ell-1$.
Throughout the proof, we will mutually assume that $n$ is sufficiently large;
for example, we will use that $h$ and $\widetilde{\nu}_{0}$ are larger than
any fixed constant without further comment.

(a) This statement is trivial since only vertices in
$B_{0}\subseteq\widetilde{B}_{0}$ are active at time $0$.

(b) Fix a weight $w\geq w_{\text{min}}$ and note that

$\left|{V}_{\geq w}^{{\leq
0}}{}{{\cap\,\widetilde{B}_{0}}}\right|\leq\left|{V}_{\geq
w}{}{{\cap\,B_{0}}}\right|$

since initially activation only occurs within $B_{0}$. Furthermore, the right-
hand side is a Poisson distributed random variable and we have

$\displaystyle\mathbb{E}[|{V}_{\geq w}{}{{\cap\,B_{0}}}|]$ $\displaystyle\leq
O(\nu
w^{1-\beta+\eta})=O(w^{2-\beta}\widetilde{\nu}_{0}^{\frac{\beta-2}{\beta-1}-\Omega(\varepsilon)}w^{-1+\eta})\leq
O(w^{2-\beta}\widetilde{\nu}_{0}^{\frac{\beta-2}{\beta-1}-\Omega(\varepsilon)}),$
(13)

where in the last step we used that $w^{-1+\eta}=O(1)$. Let $\bar{w}$ be the
weight that satisfies
$\bar{w}^{2-\beta}\widetilde{\nu}_{0}^{(\beta-2)/(\beta-1)}=h$. Then by
Markov’s inequality, $\left|{V}_{\geq\bar{w}}^{{\leq
0}}{}{{\cap\,\widetilde{B}_{0}}}\right|=0$ with probability
$1-O(\widetilde{\nu}_{0}^{-\Omega(\varepsilon)}h)=1-O(h^{-1})$ since
$h=\widetilde{\nu}_{0}^{o(1)}$. Note that this implies (b) for all
$w\geq\bar{w}$.

For smaller $w$, observe in (13) that
$\widetilde{\nu}_{0}^{-\Omega(\varepsilon)}$ dominates every $O(1)$-term for
sufficiently large $n$. Let $\mathcal{F}_{*}(0,w)$ be the event that
$\left|{V}_{\geq
w}{}{{\cap\,B_{0}}}\right|\leq(2w)^{2-\beta}\widetilde{\nu}_{0}^{(\beta-2)/(\beta-1)}$
and note that

$\displaystyle\Pr[\mathcal{F}_{*}(0,w)]\geq
1-\exp\left[-\Omega(1)(2w)^{2-\beta}\widetilde{\nu}_{0}^{(\beta-2)/(\beta-1)}\right]$
(14)

by (13) and a Chernoff bound. The exponent $(\beta-2)/(\beta-1)$ in (14)
equals the exponent $1-(\beta-1)^{-1}$ of $\widetilde{\nu}_{0}$ in
$\mathcal{F}(0,w)$. Hence, if $\mathcal{F}_{*}(0,w^{\prime})$ holds for some
$w^{\prime}\geq w_{\text{min}}$, then $\mathcal{F}(0,w)$ holds for all
$w\in[w^{\prime},2w^{\prime}]$. Therefore, it remains to prove
$\mathcal{F}_{*}(0,2^{s}w_{\text{min}})$ for all
$s\in\\{0,\dots,\log_{2}(\bar{w}/w_{\text{min}})-1\\}$. A union bound over all
such $s$ using (14) shows that all these events hold with probability
$1-\exp\\{-\Omega(h)\\}=1-O(h^{-1})$. This concludes the proof of (b).

(c) We will show that with sufficiently large probability, no vertex in
$\mathbb{T}^{d}\setminus\widetilde{B}_{i}$ has a neighbour in
$\widetilde{B}_{i-1}$. This will imply the statement, since we assumed
$\mathcal{G}(i-1)$, which means in particular that all active vertices in
round $i-1$ are in $\widetilde{B}_{i-1}$.

By Lemma 15, with probability $1-\widetilde{\nu}_{i}^{-\Omega(\eta)}\geq
1-h^{-\Omega(i)}$ there is no vertex $v=(x_{v},w_{v})$ such that
$x_{v}\in\mathbb{T}^{d}\setminus\widetilde{B}_{i}$ and
$w_{v}\geq\hat{w}_{+}(\|x_{v}\|^{d}n)$. So let $v=(x_{v},w_{v})$ be a vertex
satisfying $x_{v}\in\mathbb{T}^{d}\setminus\widetilde{B}_{i}$ and
$w_{v}\leq\hat{w}_{+}(\|x_{v}\|^{d}n)$, and note in particular that
$\|x_{v}\|\geq(\widetilde{\nu}_{i}/n)^{1/d}\geq
2(\widetilde{\nu}_{i-1}/n)^{1/d}$. Hence, due to Markov’s inequality, the
probability of $v$ having a neighbour in $\widetilde{B}_{i-1}$ is at most

$\mathbb{E}[{N}{(v)}{{\cap\,\widetilde{B}_{i-1}}}]=O(1)\widetilde{\nu}_{i-1}\left(\frac{w_{v}}{\|x_{v}\|^{d}n}\right)^{\beta-1-\eta}$

by Lemma 14. We call any such vertex $v=(x_{v},w_{v})$ _bad_ , i.e. $v$ is bad
if it satisfies $x_{v}\in\mathbb{T}^{d}\setminus\widetilde{B}_{i}$ and
$w_{v}\leq\hat{w}_{+}(\|x_{v}\|^{d}n)$, and if $v$ has at least one neighbour
in $\widetilde{B}_{i-1}$. Integrating over $r_{v}:=\|x_{v}\|$ and using Lemma
10, we can thus bound the expected number $n_{\text{bad}}$ of bad vertices by

$\displaystyle\mathbb{E}[n_{\text{bad}}]$
$\displaystyle=O(1)\int_{(\widetilde{\nu}_{i}/n)^{1/d}}^{\infty}r_{v}^{d-1}n\int_{w_{\text{min}}}^{\hat{w}_{+}(r_{v}^{d}n)}w_{v}^{1-\beta+2\eta}\frac{d}{dw_{v}}\widetilde{\nu}_{i-1}(r_{v}^{d}n)^{1-\beta+\eta}w_{v}^{\beta-1-\eta}dw_{v}dr_{v}.$

Thus, since
$(\hat{w}_{+}(r_{v}^{d}n))^{\eta}=(r_{v}^{d}n)^{\eta/(\beta-1-\eta)}\leq(r_{v}^{d}n)^{\eta}$,
we have

$\displaystyle\mathbb{E}[n_{\text{bad}}]$
$\displaystyle=O(1)\int_{(\widetilde{\nu}_{i}/n)^{1/d}}^{\infty}r_{v}^{-1}(r^{d}n)^{2-\beta+2\eta}\widetilde{\nu}_{i-1}dr_{v}=O(1)\widetilde{\nu}_{i}^{2-\beta+2\eta}\widetilde{\nu}_{i-1}=\widetilde{\nu}_{i}^{2\eta-\Omega(\varepsilon)}.$

Thus by Markov’s inequality, with probability at least
$1-\widetilde{\nu}_{i}^{2\eta-\Omega(\varepsilon)}\geq 1-h^{-\Omega(i)}$ there
is no such vertex. Statement (c) follows.

(d) We distinguish two cases. For
$w\geq\widetilde{\nu}_{0}^{(\zeta+\varepsilon)^{-\ell}(1+3\eta)/(\beta-1)}$,
we consider the upper bound

$\left|{V}_{\geq
w}^{{\leq\ell}}{}{{\cap\,2^{\ell}\widetilde{B}_{0}}}\right|\leq\left|{V}_{\geq
w}{}{{\cap\,2^{\ell}\widetilde{B}_{0}}}\right|.$

Since we have

$\mathbb{E}\left[\left|{V}_{\geq
w}{}{{\cap\,2^{\ell}\widetilde{B}_{0}}}\right|\right]=O(1)2^{\ell
d}\widetilde{\nu}_{0}w^{1-\beta+\eta}=O(1)w^{2-\beta}2^{\ell
d}\widetilde{\nu}_{0}^{1-(\zeta+\varepsilon)^{-\ell}(1+\eta)/(\beta-1)},$

and since this number is Poisson distributed, we obtain

$\displaystyle\Pr\left[\left|{V}_{\geq
w}{}{{\cap\,2^{\ell}\widetilde{B}_{0}}}\right|\leq 2(2w)^{2-\beta}2^{\ell
d}\widetilde{\nu}_{0}^{1-(\zeta+\varepsilon)^{-\ell}/(\beta-1)}\right]$ (15)
$\displaystyle\hskip 142.26378pt\geq 1-\exp\left[-\Omega(1)w^{2-\beta}2^{\ell
d}\widetilde{\nu}_{0}^{1-(\zeta+\varepsilon)^{-\ell}/(\beta-1)}\right]$

by a Chernoff bound. Similarly as in the proof of (b), it suffices to
establish the bound in (15) only for weights of the form $2^{s}w_{\text{min}}$
for $s\in\\{0,\dots,\log_{2}(\bar{w}_{\ell}/w_{\text{min}})-1\\}$, where
$\bar{w}_{\ell}$ is defined by $\bar{w}_{\ell}^{2-\beta}2^{\ell
d}\widetilde{\nu}_{0}^{1-(\zeta+\varepsilon)^{-\ell}/(\beta-1)}=h^{\ell}$. A
union bound over all such $s$ proves that (b) holds for all
$w\geq\widetilde{\nu}_{0}^{(\zeta+\varepsilon)^{-\ell}(1+3\eta)/(\beta-1)}$
with probability $1-\exp(-\Omega(h^{\ell}))=1-h^{-\Omega(\ell)}$.

For the second case assume that
$w\leq\widetilde{\nu}_{0}^{(\zeta+\varepsilon)^{-\ell}(1+3\eta)/(\beta-1)}$.
We claim that it suffices to restrict ourselves to vertices of weight at most
$\hat{w}:=\hat{w}_{+}^{0}(\widetilde{\nu}_{0})=\widetilde{\nu}_{0}^{1/(\beta-1)}$.
More precisely, we will show that with probability at least
$1-h^{-\Omega(\ell)}$, for all
$w\leq\widetilde{\nu}_{0}^{(\zeta+\varepsilon)^{-\ell}(1+3\eta)/(\beta-1)}$ we
have

$|U(w)|\leq
h^{\ell}w^{2-\beta+\eta}\widetilde{\nu}_{0}^{1-(\zeta+\varepsilon)^{-\ell}/(\beta-1)},$
(16)

where
$U(w):={V}_{\in[w,\hat{w}]}^{{\leq\ell}}{}{{\cap\,2^{\ell}\widetilde{B}_{0}}}$.
This suffices since by the first case there are sufficiently few other
vertices active: we have seen that with probability at least
$1-h^{-\Omega(\ell)}$ for any
$w\leq\widetilde{\nu}_{0}^{(\zeta+\varepsilon)^{-\ell}(\beta-1)^{-1}(1+3\eta)}=o(\hat{w})$
(for $\ell\geq 1$) we have

$\displaystyle\left|{V}_{\geq\hat{w}}^{{\leq\ell}}{}{{\cap\,2^{\ell}\widetilde{B}_{0}}}\right|\leq
h^{\ell}\hat{w}^{2-\beta+\eta}\widetilde{\nu}_{0}^{1-(\zeta+\varepsilon)^{-\ell}/(\beta-1)}\leq\frac{1}{2}h^{\ell}w^{2-\beta+\eta}\widetilde{\nu}_{0}^{1-(\zeta+\varepsilon)^{-\ell}/(\beta-1)}.$

Thus we want to bound $\mathbb{E}[|U|]$ by calculating the expected number of
edges having one endpoint in ${V}^{{\leq\ell-1}}{}{}$ and the other in
${V}_{\in[w,\hat{w}]}{}{{\cap\,2^{\ell}\widetilde{B}_{0}}}$, i.e. we set

$M(w):=E\left({V}^{{\leq\ell-1}}{}{},{V}_{\in[w,\hat{w}]}{}{{\cap\,2^{\ell}\widetilde{B}_{0}}}\right).$

Furthermore we observe that each edge in $M(w)$ is also contained in at least
one of the following two edge-sets: Let

$M_{*}(w):=E\left({V}^{{\leq\ell-1}}{}{{\cap\,2^{\ell+1}\widetilde{B}_{0}}},{V}_{\in[w,\hat{w}]}{}{}\right),$

and

$M^{*}(w):=E\left({V}{}{{\cap\,(\mathbb{T}^{d}\setminus
2^{\ell+1}\widetilde{B}_{0})}},{V}_{\in[w,\hat{w}]}{}{{\cap\,2^{\ell}\widetilde{B}_{0}}}\right),$

then we have $M(w)\subseteq M_{*}(w)\cup M^{*}(w)$. It will turn out that the
bound on $|U(w)|\leq|M_{*}(w)|+|M^{*}(w)|$ obtained this way strong enough to
prove (16).

We start by estimating $|M_{*}(w)|$. As a preparation, we first bound
$\left|{V}_{\geq
w^{\prime}}^{{\leq\ell-1}}{}{{\cap\,2^{\ell+1}\widetilde{B}_{0}}}\right|$,
i.e. the number of vertices in a slightly larger region that were already
active in the previous round. Since we assumed that $\mathcal{F}(\ell-1)$
holds, for those vertices which are also contained in the slightly smaller
region $2^{\ell-1}\widetilde{B}_{0}$ we already know that

$\left|{V}_{\geq
w^{\prime}}^{{\leq\ell-1}}{}{{\cap\,2^{\ell-1}\widetilde{B}_{0}}}\right|\leq
2^{(\ell-1)d}(w^{\prime})^{2-\beta+\eta}\widetilde{\nu}_{0}^{1-(\zeta+\varepsilon)^{-\ell+1}/(\beta-1)}.$
(17)

Now if $\ell=1$, then no other vertices were active in round $\ell-1=0$ by
(a). For $\ell\geq 2$, we need to examine the remaining region
$2^{\ell+1}\widetilde{B}_{0}\setminus 2^{\ell-1}\widetilde{B}_{0}$. Note that
this area is contained in $2^{\ell}\widetilde{B}_{1}$. Hence, we may apply (f)
with $i^{\prime}=1$ and $\ell^{\prime}=\ell-2$, and thus

$\displaystyle\mathbb{E}\left[\left|{V}_{\geq
w^{\prime}}^{{\leq\ell-1}}{}{{\cap\,(2^{\ell+1}\widetilde{B}_{0}\setminus
2^{\ell-1}\widetilde{B}_{0})}}\right|\right]$
$\displaystyle=O(1)2^{(\ell+1)d}\widetilde{\nu}_{0}(w^{\prime})^{1-\beta+\eta}w^{\prime}2^{(\ell-2)d}\widetilde{\nu}_{1}^{-(\zeta+\varepsilon)^{-\ell}/(\beta-1)}$
$\displaystyle=O(1)h^{\ell}(w^{\prime})^{2-\beta+\eta}\widetilde{\nu}_{0}^{1-(\zeta+\varepsilon)^{-\ell+1}/(\beta-1)}.$
(18)

Combining equations (17) and (18) we obtain

$\displaystyle\mathbb{E}\left[\left|{V}_{\geq
w^{\prime}}^{{\leq\ell-1}}{}{{\cap\,2^{\ell+1}\widetilde{B}_{0}}}\right|\right]=O(1)\min\left\\{h^{\ell}(w^{\prime})^{2-\beta+\eta}\widetilde{\nu}_{0}^{1-\frac{(\zeta+\varepsilon)^{-\ell+1}}{\beta-1}},2^{(\ell+1)d}\widetilde{\nu}_{0}(w^{\prime})^{1-\beta+\eta}\right\\},$
(19)

where the second term arises from dropping the condition on being active in
round $i-1$. Now we denote by
$\tilde{w}=\Theta(1)\widetilde{\nu}_{0}^{(\zeta+\varepsilon)^{-\ell+1}(\beta-1)^{-1}}2^{(\ell+1)d}h^{-\ell}$
the weight for which the two expressions in (19) coincide. Recall that for any
vertex $u=(x_{u},w_{u})$ of fixed weight (and independently of its position)
we have $\mathbb{E}[|{N}{(u)}{}|]=\Theta(w_{u})$ by Lemma 12. Moreover, by
Lemma 13, the probability $q(w)$ for a random neighbour of $u$ to have weight
at least $w$ is $O(w^{2-\beta+\eta/2})$, independently of $u$. Therefore we
have

$\displaystyle\mathbb{E}[|M_{*}(w)|]=O(q(w))\sum_{u\in{V}_{\geq
0}^{{\leq\ell-1}}{}{{\cap\,2^{\ell+1}\widetilde{B}_{0}}}}\mathbb{E}[|{N}{(u)}{}|]$
$\displaystyle\stackrel{{\scriptstyle
L.~{}\ref{lem:integral}}}{{=}}O(q(w))\int_{0}^{\infty}\min\left\\{h^{\ell}w_{u}^{2-\beta+\eta}\widetilde{\nu}_{0}^{1-\frac{(\zeta+\varepsilon)^{-\ell+1}}{\beta-1}},2^{(\ell+1)d}\widetilde{\nu}_{0}w_{u}^{1-\beta+\eta}\right\\}\left(\frac{d}{dw_{u}}w_{u}\right)dw_{u}.$

Using Lemma 11 with $\tilde{w}$ we obtain

$\displaystyle\mathbb{E}[|M_{*}(w)|]$
$\displaystyle=O(1)w^{2-\beta+\eta/2}2^{(\ell+1)d}\widetilde{\nu}_{0}\tilde{w}^{2-\beta+\eta}$
$\displaystyle=O(1)w^{2-\beta+\eta/2}2^{(\ell+1)d(3-\beta+\eta)}h^{\ell(\beta-2-\eta)}\widetilde{\nu}_{0}^{1-(\zeta+\varepsilon)^{-\ell+1}(\beta-2+\eta)/(\beta-1)}$
$\displaystyle\leq
w^{2-\beta+\eta/2}h^{\ell(\beta-2-2\eta)}\widetilde{\nu}_{0}^{1-(\zeta+\varepsilon)^{-\ell}(1+\Omega(\varepsilon)-O(\eta))/(\beta-1)}$
$\displaystyle\leq
w^{2-\beta+\eta/2}h^{\ell(\beta-2-2\eta)}\widetilde{\nu}_{0}^{1-(\zeta+\varepsilon)^{-\ell}/(\beta-1)}.$
(20)

Next we turn to the edges in $M^{*}(w)$. If $\ell=1$, then
${V}^{{\leq\ell-1}}{}{{\cap\,(\mathbb{T}^{d}\setminus
2^{\ell+1}\widetilde{B}_{0})}}$ is empty by (a), hence also $M^{*}(w)$. So
assume $\ell\geq 2$. Fix a vertex $v=(x_{v},w_{v})$ such that $x_{v}\in
2^{\ell}\widetilde{B}_{0}$ and $w_{v}\leq\hat{w}$ and denote by
$M^{*}(w,v):=\\{e\in M^{*}(w)\mid v\in e\\}$ the subset of $M^{*}(w)$
consisting of all edges incident with $v$. Now note that every edge in
$M^{*}(w,v)$ must bridge a distance of at least
$\tilde{r}_{\ell}:=2^{\ell}(\widetilde{\nu}_{0}/n)^{1/d}$ and hence Lemma 10
and Lemma 11 imply

$\displaystyle\mathbb{E}\left[\left|M^{*}(w,v)\right|\right]$
$\displaystyle=O(1)\int_{r_{\ell}}^{\infty}r^{d-1}n\int_{0}^{\infty}w_{*}^{1-\beta+\eta}\frac{d}{dw_{*}}\min\left\\{\left(\frac{w_{*}w_{v}}{r^{d}n}\right)^{\alpha},1\right\\}dw_{*}dr$
$\displaystyle=O(1)\int_{\tilde{r}_{\ell}}^{\infty}r^{d-1}n\left(\frac{r^{d}n}{w_{v}}\right)^{1-\beta+\eta}dr=O(1)(\tilde{r}_{\ell}^{d}n)^{2-\beta+\eta}w_{v}^{\beta-1+\eta}$
$\displaystyle=O(1)\left(\frac{2^{d\ell}\widetilde{\nu}_{0}}{w_{v}}\right)^{2-\beta+\eta}w_{v}=O(1)\widetilde{\nu}_{0}^{-\frac{(\zeta+\varepsilon)^{-\ell}}{\beta-1}}w_{v},$

where the last step follows from
$(\beta-2)(\beta-2-\eta)(\zeta+\varepsilon)^{2}\geq 1$ since we assumed
$w_{v}\leq\hat{w}=\widetilde{\nu}_{0}^{1/(\beta-1)}$ and $\ell\geq 2$. Hence,

$\displaystyle\mathbb{E}[|M^{*}(w)|]$
$\displaystyle=O(1)\widetilde{\nu}_{0}\int_{w}^{\infty}w_{v}^{1-\beta+\eta/2}\frac{d}{dw_{v}}\left(\widetilde{\nu}_{0}^{-(\zeta+\varepsilon)^{-\ell}/(\beta-1)}w_{v}\right)dw_{v}$
$\displaystyle\leq
O(1)w^{2-\beta+\eta/2}\widetilde{\nu}_{0}^{1-(\zeta+\varepsilon)^{-\ell}/(\beta-1)}.$

Together with (20), this shows that the expected number of vertices in $U(w)$
is also bounded by

$\mathbb{E}[|U(w)|]\leq
2w^{2-\beta+\eta/2}h^{\ell(\beta-2-2\eta)}\widetilde{\nu}_{0}^{1-(\zeta+\varepsilon)^{-\ell}/(\beta-1)},$

and therefore, by Markov’s inequality, we have

$\Pr\left[|U(w)|\geq\frac{1}{2}(2w)^{2-\beta+\eta}h^{\ell}\widetilde{\nu}_{0}^{1-(\zeta+\varepsilon)^{-\ell}/(\beta-1)}\right]=w^{-\eta/2}h^{-\Omega(\ell)}.$

As in the proof of (b), by a union bound over all weights of the form
$2^{s}w_{\text{min}}$ for
$s\in\\{0,\dots,\log_{2}(\hat{w}/w_{\text{min}})-1\\}$, we find that with
probability $1-h^{-\Omega(\ell)}$, for all $w\geq w_{\text{min}}$ we have

$\displaystyle|U(w)|\leq\frac{1}{2}w^{2-\beta+\eta}h^{\ell}\widetilde{\nu}_{0}^{1-(\zeta+\varepsilon)^{-\ell}/(\beta-1)},$
(21)

concluding the proof of (d).

(e) This follows from (a)–(d) by a simple union bound.

(f) Fix a vertex $v=(x_{v},w_{v})$ such that $x_{v}\in\mathbb{T}^{d}\setminus
2^{\ell+1}\widetilde{B}_{i-1}$. The statement (f) is trivial if
$w_{v}\geq\widetilde{\nu}_{i}^{(\zeta+\varepsilon)^{-\ell-2}/(\beta-1)}$, so
assume the contrary. We first estimate the number of neighbours in
$2^{\ell}\widetilde{B}_{i-1}$. Observe that every such vertex has distance at
least $\tilde{r}_{i-1,\ell}:=2^{\ell}(\widetilde{\nu}_{i-1}/n)^{1/d}$ of $v$.
Therefore, using
$w_{v}\leq\widetilde{\nu}_{i}^{(\zeta+\varepsilon)^{-\ell-2}/(\beta-1)}\leq\widetilde{\nu}_{i}^{(\zeta+\varepsilon)^{-2}/(\beta-1)}$,
we obtain

$\displaystyle\mathbb{E}\left[\left|{N}{(v)}{{\cap\,2^{\ell}\widetilde{B}_{i-1}}}\right|\right]$
$\displaystyle=O(1)2^{\ell
d}\widetilde{\nu}_{i-1}\int_{0}^{\infty}w^{1-\beta+\eta}\frac{d}{dw}\min\left\\{\left(\frac{ww_{v}}{2^{\ell
d}\widetilde{\nu}_{i-1}}\right)^{\alpha},1\right\\}dw$
$\displaystyle\stackrel{{\scriptstyle
L.~{}\ref{lem:evalintegral},\alpha>\beta-1}}{{=}}O(1)w_{v}\left(\frac{2^{\ell
d}\widetilde{\nu}_{i-1}}{w_{v}}\right)^{2-\beta+\eta}$
$\displaystyle=O(1)w_{v}2^{\ell
d}\left(\widetilde{\nu}_{i}^{(\zeta+\varepsilon)^{-1}-(\zeta+\varepsilon)^{-2}/(\beta-1)}\right)^{2-\beta+\eta}.$

Since
$(2-\beta-\eta)[(\zeta+\varepsilon)^{-1}-(\zeta+\varepsilon)^{-2}/(\beta-1)]=-(\zeta+\varepsilon)^{-2}(1+\Omega(\varepsilon))/(\beta-1)$
we deduce

$\displaystyle\mathbb{E}\left[\left|{N}{(v)}{{\cap\,2^{\ell}\widetilde{B}_{i-1}}}\right|\right]$
$\displaystyle=O(1)w_{v}2^{\ell
d}\widetilde{\nu}_{i}^{-(\zeta+\varepsilon)^{-2}/(\beta-1)-\Omega(\varepsilon)}$
$\displaystyle\leq\frac{1}{2}w_{v}2^{\ell
d}\widetilde{\nu}_{i}^{-(\zeta+\varepsilon)^{-\ell-2}/(\beta-1)}.$ (22)

In the case $\ell=0$, this already proves the assertion since in round $i-1$
no vertex outside of $\widetilde{B}_{i-1}$ is active by $\mathcal{E}(i-1)$,
and thus $\Pr[v\in{V}^{{=i}}{}{}]\leq\mathbb{E}[N(v)\cap
2^{\ell}\widetilde{B}_{i-1}]$.

So assume $\ell\geq 1$. Set $U_{*}:=\left|{N}^{{\leq
i+\ell-1}}{(v)}{{\cap\,(\mathbb{T}^{d}\setminus
2^{\ell}\widetilde{B}_{i-1})}}\right|$. In this case, we can use the induction
hypothesis of statement (f) for $i^{\prime}=i$ and $\ell^{\prime}=\ell-1$ to
estimate

$\displaystyle\mathbb{E}$ $\displaystyle\left[\left|U_{*}\right|\right]=$
$\displaystyle
O(1)\int_{0}^{\infty}r^{d-1}n\int_{0}^{\infty}w^{1-\beta+\eta}\frac{d}{dw}\left(\min\\{wh^{\ell}\widetilde{\nu}_{i}^{-\frac{(\zeta+\varepsilon)^{-\ell-1}}{\beta-1}},1\\}\min\\{\left(\frac{ww_{v}}{r^{d}n}\right)^{\alpha},1\\}\right)dwdr.$

To compute this integral, note that whenever the second minimum is attained by
$1$, the inner integral runs either over a polynomial in $w$ with exponent
$1-\beta+\eta<-1$, or over the zero function. On the other hand, whenever the
second minimum is is attained by the expression $(ww_{v}/(r^{d}n))^{\alpha}$,
then the inner integral runs over a a polynomial in $w$ with exponent larger
than $-1$ (either with exponent $\alpha-\beta+\eta>-1$, or even with exponent
$\alpha-\beta+\eta+1$). Therefore, by Lemma 11 for $\tilde{w}=r^{d}n/w_{v}$,
we obtain in all cases

$\displaystyle\mathbb{E}\left[\left|U_{*}\right|\right]$
$\displaystyle=O(1)\int_{0}^{\infty}r^{d-1}n\left(\frac{r^{d}n}{w_{v}}\right)^{1-\beta+\eta}\min\left\\{\left(\frac{r^{d}n}{w_{v}}\right)h^{\ell}\widetilde{\nu}_{i}^{-(\zeta+\varepsilon)^{-\ell-1}/(\beta-1)},1\right\\}dr.$

Similarly, let $r_{*}$ be defined by
$r_{*}^{d}n/w_{v}=h^{-\ell}\widetilde{\nu}_{i}^{(\zeta+\varepsilon)^{-\ell-1}/(\beta-1)}$,
then the exponent of $r$ in the antiderivative of the integrand is positive
for all $r<r_{*}$ and negative for all $r>r_{*}$. Hence,

$\displaystyle\mathbb{E}\left[\left|U_{*}\right|\right]$
$\displaystyle=O(1)w_{v}\left(h^{\ell}\widetilde{\nu}_{i}^{-(\zeta+\varepsilon)^{-\ell-1}/(\beta-1)}\right)^{\beta-2-\eta}\leq\frac{1}{2}w_{v}2^{\ell
d}\widetilde{\nu}_{i}^{-(\zeta+\varepsilon)^{-\ell-2}/(\beta-2)},$ (23)

since $(\zeta+\varepsilon)(\beta-2-\eta)\geq 1$ and $h=\omega(1)$. Together,
equations (22) and (23) prove the claim. ∎

###  6.2. Isolation strategies: Proof of Corollary 7

###### Proof.

By Theorem 17, whp there is no vertex outside of $\widetilde{B}_{i}$ which is
active in round $i$. Therefore, it suffices to (permanently) remove by the end
of round $i$ all edges that cross the boundary of $\widetilde{B}_{i}$, i.e.
all edges in $E(\widetilde{B}_{i},\mathbb{T}^{d}\setminus\widetilde{B}_{i})$.
This is very similar to [15, Lemma 7.1 and Theorem 7.2], where the number of
edges cutting a grid is considered. It does not follow directly from this
lemma since the error terms in [15] are too large for our purposes. However,
what _does_ follow directly from their proof is that among those edges that
are completely contained in $2\widetilde{B}_{i}$, the number of edges that
cross a fixed axis-parallel hyperplane is at most
$\widetilde{\nu}_{i}^{\max\\{3-\beta,1-1/d\\}+o(1)}$. Since the boundary of
$\widetilde{B}_{i}$ consists of a constant number of faces, this proves the
bound for those edges which have both endpoints in $2\widetilde{B}_{i}$.

So it remains to consider the set
$M_{i}:=E(\widetilde{B}_{i},\mathbb{T}^{d}\setminus 2\widetilde{B}_{i})$. Let
$\eta>0$ be any constant, and let $v=(x_{v},w_{v})$ be a vertex such that
$x_{v}\in\mathbb{T}^{d}\setminus 2\widetilde{B}_{i}$. Then by Lemma 14 (in the
case $\alpha>\beta-1$) the expected number of neighbours of $v$ inside of
$\widetilde{B}_{i}$ is

$\displaystyle\mathbb{E}[{N}{(v)}{{\cap\,\widetilde{B}_{i}}}]=O(\widetilde{\nu}_{i})\min\left\\{\left(\frac{w_{v}}{\|x_{v}\|^{d}n}\right)^{\beta-1-\eta},1\right\\}.$

Note that $v$ has distance at least $r_{i}:=(\widetilde{\nu}_{i}/n)^{1/d}$
from the origin. Thus we may use Lemma 10 and Lemma 11 to estimate

$\displaystyle\mathbb{E}[|M_{i}|]$
$\displaystyle=O(1)\int_{r_{i}}^{\infty}r^{d-1}n\int_{0}^{\infty}w_{v}^{1-\beta+2\eta}\frac{d}{dw_{v}}\widetilde{\nu}_{i}\min\left\\{\left(\frac{w_{v}}{r^{d}n}\right)^{\beta-1-\eta},1\right\\}dw_{v}dr$
$\displaystyle=O(\widetilde{\nu}_{i})\int_{r_{i}}^{\infty}r^{-1}(r^{d}n)^{2-\beta+2\eta}dr=O(\widetilde{\nu}_{i}^{3-\beta+2\eta}).$

Since $\widetilde{\nu}_{i}=\omega(1)$, we can deduce that
$\mathbb{E}[|M_{i}|]\leq\widetilde{\nu}_{i}^{3-\beta+3\eta}$ for sufficiently
large $n$. Since this holds for all $\eta>0$, the claim follows. ∎

###  6.3. Lower bound on the speed

In this section we show lower bounds for the probability that a vertex in a
specific region and with a specific weight will be active in some round,
provided that we start in the supercritical case. Recall that the
supercritical case is defined by $\rho=\omega(\rho_{c})$ for strong power-law
weights, and $\rho=\omega(\nu^{-1/(\beta-1-\eta)})$ otherwise. The same bounds
also hold in the critical case if at least $k$ “heavy” vertices are activated
in the first round, which happens with probability $\Omega(1)$.

The key idea is that the infection spreads in two ways: _(i)_ from heavy
vertices in one region to heavy vertices in the next (surrounding) region,
where the volume of the region increases by an exponent of $\zeta-\varepsilon$
in each step, and _(ii)_ from vertices of weight $w$ to nearby vertices of
weight $w^{1/(\zeta-\varepsilon)}$. We formalise the occurring weights with
the following definitions.

######  Definition 18.

Let $\varepsilon>0$ be a constant and let $\eta=\eta(\varepsilon)>0$ be a
constant which is sufficiently small compared to $\varepsilon$, cf. Section
2.3. For any integers $i\geq 0$ and $\ell\geq 0$, we define

$w_{i{{,\ell}}}:=\hat{w}_{-}({\nu}_{i})^{(\zeta-\varepsilon)^{-\ell}}={\nu}_{i}^{(\zeta-\varepsilon)^{-\ell}/(\beta-1+\eta)}=\nu^{(\zeta-\varepsilon)^{i-\ell}/(\beta-1+\eta)}.$

We abbreviate the set of all vertices in ${B}_{i}$ of weight at least at least
$w_{i{{,0}}}$ by $U_{i}:={V}_{\geq w_{i{{,0}}}}{}{{\cap\,{B}_{i}}}$, and we
call such vertices _heavy_ if the value of $i$ is clear from the context. As
usual, superscripts in the notation denote active vertices, so $U_{i}^{{\leq
j}}:={V}_{\geq w_{i{{,0}}}}^{{\leq j}}{}{{\cap\,{B}_{i}}}$. Furthermore we
denote by $\mathcal{H}(i)$ the event that in round $i+3$ all vertices in
$U_{i}$ are active.

The following theorem gives lower bounds on the probability that a vertex is
active in some round. It agrees with the above intuition in the following
sense: if $j$ is the first round in which a vertex has, say, probability $1/2$
to be active according to the bound in Theorem 19 (c), then $j$ agrees with
the round that is predicted by the above intuition, up to additive constants.
We will see in Section 7 that Theorem 17 provides matching lower bounds on
$j$, up to minor order terms. So in this sense, Theorem 19 is tight.

######  Theorem 19.

Let $\varepsilon$ and $\eta$ be as in Definition 18. Assume furthermore that
we are in the supercritical case, or instead that $|U_{i}^{{\leq 1}}|\geq k$.
Then the following is true:

  1. (a)

Whp $|U_{i}|={\nu}_{i}^{\Omega(\eta)}$ and $|U_{i}|=O({\nu}_{i})$ uniformly
for all $i\geq 0$.

  2. (b)

Whp all the events $\mathcal{H}(i)$ occur.

  3. (c)

There exist constants $C_{0},C_{1},C_{2}>0$ such that the following holds: Let
$v=(x_{v},w_{v})$ be any vertex with fixed position and weight and let
$i,\ell\geq 0$ be such that $x_{v}\in{B}_{i}$ and
$w_{v}\geq\max\\{w_{i{{,\ell}}},C_{0}\\}$. Then for sufficiently large
$n\in\mathbb{N}$,

$\Pr[v\in{V}^{{\leq
i+3+\ell}}{}{}\mid\mathcal{H}(0),\ldots,\mathcal{H}(i)]\geq
1-\exp\left[-C_{1}{\nu}_{i}^{{C_{2}(\zeta-\varepsilon)^{-\ell}}}\right].$

Before we prove Theorem 19, we remark the following.

######  Remark 20.

Our proof will in fact show that (c) still holds if we replace ${B}_{i}$ by an
arbitrary ball of the same volume, and that it suffices if only a constant
fraction of all heavy vertices is active. More precisely, let $B$ be any ball,
and let $\mathcal{H}(i^{\prime},B)$ be the event that in round $i^{\prime}$ at
least half of the vertices in $B$ of weight at least
$\hat{w}_{-}(n{\operatorname{Vol}\\!\left(B\right)})$ are active. Then there
are constants $C_{0},C_{1},C_{2}>0$ such that for any vertex $v=(x_{v},w_{v})$
with fixed position $x_{v}\in B$, and with fixed weight
$w_{v}\geq\max\left\\{(n{\operatorname{Vol}\\!\left(B\right)})^{(\zeta-\varepsilon)^{-\ell}/(\beta-1+\eta)},C_{0}\right\\}$
we have

$\Pr[v\in{V}^{{\leq i^{\prime}+\ell}}{}{}\mid\mathcal{H}(i^{\prime},B)]\geq
1-\exp\left[-C_{1}(n{\operatorname{Vol}\\!\left(B\right)})^{C_{2}(\zeta-\varepsilon)^{-\ell}}\right].$

For the sake of readability, we omit the details and prove Theorem (19) only
in the case $B={B}_{i}$.

###### Proof of Theorem 19.

(a) By definition of $U_{i}$,

$\mathbb{E}[|U_{i}|]\geq{\nu}_{i}w_{i{{,0}}}^{1-\beta-\eta/2}={\nu}_{i}^{\Omega(\eta)}.$

The random variable $|U_{i}|$ is Poisson distributed. Therefore, we have
$\Pr[|U_{i}|\leq\mathbb{E}[|U_{i}|]/2]\leq e^{-\Omega(\mathbb{E}[|U_{i}|])}$.
By a union bound over all $i$, we see that whp
$|U_{i}|\geq{\nu}_{i}^{\Omega(\eta)}$ for all $i\geq 0$. Similarly, the upper
bound follows since
$0\ll\mathbb{E}[|U_{i}|]\leq\mathbb{E}[|{B}_{i}|]=O({\nu}_{i})$.

(b) We first show that in the supercritical case for weak power-law weights,
whp $|U_{0}^{{\leq 1}}|\geq k$. Let $v=(x_{v},w_{v})$ be a vertex in $U_{0}$.
Then we claim that in round 1, such a vertex will be active with at least
constant probability. We may restrict ourselves to the case $w_{v}\leq\nu$,
since larger weights make it only easier to become active. Consider a ball
around $v$ with the property that every vertex of weight at least
$w_{\text{min}}$ (so _all_ vertices) in this ball have probability $\Omega(1)$
to connect to $v$. Observe that by condition (2) and (3) on the edge
probabilities we may choose the ball to have volume $\Omega(w_{v}/n)$. (For
$\alpha<\infty$ we may choose the volume to be exactly $w_{v}/n$, for
$\alpha=\infty$ we may have to choose it smaller by at most a constant
factor.) Since $w_{v}\leq\nu$, at least a constant fraction of this ball lies
in $B_{0}$. Hence, $\mathbb{E}[|{N}^{{\leq 0}}{(v)}{}|]=\Omega(\rho
w_{v})=\omega(1)$. Since $|{N}^{{\leq 0}}{(v)}{}|$ is a Poisson distributed
random variable, $v$ becomes active with high probability. In particular, if
we fix any $k$ vertices in $U_{0}$ then whp all $k$ of them will be active in
round $1$. This implies that whp $|U_{0}^{{\leq 1}}|\geq k$, as claimed.

Next we show that $|U_{0}^{{\leq 1}}|\geq k$ implies that whp at least an
$\Omega(1)$ fraction of all vertices in $U_{0}$ is active in round $2$. For
$\alpha<\infty$, any two vertices in $U_{0}$ have probability at least
$\Omega(\min\\{w_{0}^{2}/\nu,1\\})=\Omega(1)$ to be adjacent, independently of
each other. For $\alpha=\infty$, the probability is also $\Omega(1)$ since
$w_{0}^{2}/\nu=\omega(1)$. Hence, by the Chernoff bound, whp $|U_{0}^{{\leq
2}}|=\Omega(|U_{0}|)$.

We show that the same holds in the supercritical case for strong power-law
weights, i.e. whp at least an $\Omega(1)$ fraction of $U_{0}$ is active in
round $2$. Recall that $\rho=\omega(\nu^{-1/(\beta-1)})$ since we are
supercritical. Let $\rho^{\prime}$ be a function with the properties
$\rho^{\prime}=o(\rho)$,
$\rho^{\prime}=o(1/w_{0})=o(\nu^{-1/(\beta-1+\eta)})$, and
$\rho^{\prime}=\omega(\nu^{-1/(\beta-1)})$, and let
$w^{\prime}:=1/\rho^{\prime}$. Note that $\mathbb{E}[|{V}_{\geq
w^{\prime}}{}{{\cap\,B_{0}}}|]=\Omega((w^{\prime})^{1-\beta}\nu)=\omega(1)$.
As for weak power-laws, for a vertex $v$ of weight at least $w^{\prime}$, we
consider a ball $B$ around $v$ of volume $w^{\prime}/n$. In the case
$\alpha<\infty$, every vertex in $B$ has probability
$\Omega(\min\\{w_{\text{min}}w^{\prime}/w^{\prime},1\\})=\Omega(1)$ to connect
to $v$. In the case $\alpha=\infty$, we may achieve the same by shrinking the
ball $B$ by at most a constant factor. In either case, the expected number of
vertices in ${V}^{{\leq 0}}{}{}\cap B$ is $\rho
n{\operatorname{Vol}\\!\left(B\right)}=\Omega(\rho/\rho^{\prime})=\omega(1)$.
Hence, every vertex in ${V}_{\geq w^{\prime}}{}{}\cap B_{0}$ is in ${V}^{{\leq
1}}{}{}$ with probability $1-o(1)$. By Markov’s inequality, whp the number of
vertices in ${V}_{\geq w^{\prime}}{}{{\cap\,B_{0}}}$ that are _not_ in
${V}^{{\leq 1}}{}{}$ is $o(\mathbb{E}[|{V}_{\geq
w^{\prime}}{}{{\cap\,B_{0}}}|])$. In particular, whp $|{V}_{\geq
w^{\prime}}^{{\leq 1}}{}{}\cap B_{0}|=\omega(1)$. Finally, for any two
vertices $u\in U_{0}$ and $v\in{V}_{\geq w^{\prime}}{}{{\cap\,B_{0}}}$, the
probability that $u$ and $v$ are adjacent is $\Omega(1)$, since
$w_{0}w^{\prime}/\nu\geq w_{0}^{2}/\nu=\omega(1)$ with room to spare. The
claim now follows as for the other cases.

So we have shown that in all cases whp an $\Omega(1)$ fraction of all vertices
in $U_{0}$ is active in round $2$, so let us assume this. To show that
$\mathcal{H}(0)$ holds whp, recall that any two vertices in $U_{0}$ have
probability $\Omega(1)$ to be connected. Therefore, the probability that a
vertex in $U_{0}$ does not become active in round $3$ is at most
$\Pr[\mathrm{Bin}\left(|U_{0}|,\Omega(1)\right)<k]=\exp[-\Omega(|U_{0}|)]=o(1/|U_{0}|)$
by a Chernoff bound. Hence, by the union bound whp all vertices in $U_{0}$ are
active in round $3$. This proves that $\mathcal{H}(0)$ holds whp.

It remains to prove that the statement holds uniformly for all $i\geq 1$. By
(a) we may assume that for all $i\geq 0$ the set $|U_{i}|$ satisfies
$|U_{i}|={\nu}_{i}^{\Omega(\eta)}$ and $|U_{i}|=O({\nu}_{i})$.

We claim that any two vertices $v_{i-1}\in U_{i-1}$ and $v_{i}\in U_{i}$ with
fixed position and weight form an edge with probability $\Omega(1)$. Indeed,
this follows immediately since their distance is at most
$({\nu}_{i}/n)^{1/d}$, and hence

$\frac{w_{v_{i-1}}w_{v_{i}}}{\|x_{v_{i}}-x_{v_{i-1}}\|^{d}n}\geq\frac{w_{i-1{{,0}}}w_{i{{,0}}}}{{\nu}_{i}}={\nu}_{i}^{\frac{(\zeta-\varepsilon)^{-1}+1}{\beta-1+\eta}-1}={\nu}_{i}^{\Omega(\varepsilon)-O(\eta)}=\omega(1).$

Therefore, the number of edges from a vertex $v_{i}\in U_{i}$ into $U_{i-1}$
is lower bounded by a binomially distributed random variable
$\mathrm{Bin}\left(|U_{i-1}|,\Omega(1)\right)$. By the Chernoff bound, the
probability that $v_{i}$ has less than $k$ neighbours in $U_{i-1}$ is at most
$\exp[-\Omega(|U_{i}|)]=\exp[-{\nu}_{i-1}^{\Omega(\eta)}]$. A union bound over
all vertices in $U_{i-1}$ shows that still with probability at least
$1-\exp[-{\nu}_{i-1}^{\Omega(\eta)}]$ every vertex in $U_{i}$ has at least $k$
neighbours in $U_{i-1}$. A union bound over all $i\geq 1$ shows that whp the
same is still true for all $i\geq 1$ simultaneously. Hence, by a simple
induction, all the events $\mathcal{H}(i)$ occur, as required.

(c) We only give the proof in the case $\alpha<\infty$, and explain in the end
the changes that are necessary for $\alpha=\infty$. For $\alpha<\infty$, we
prove the statement for $C_{0}:=(8k)^{2d/(\varepsilon^{2}(\beta-2))}$,
$C_{1}:=4^{-d/\varepsilon}$ and
$C_{2}:=[\varepsilon(\beta-2)/2](\zeta-\varepsilon)/(\beta-1+\eta)$, where we
assume that $\varepsilon>0$ is sufficiently small. We use induction on $\ell$.
If $w_{v}\geq w_{i{{,0}}}$ then $\mathcal{H}(i)$ implies that $v\in A(i+3)$,
so for $\ell=0$ there is nothing to show. So let $\ell\geq 1$. Before we start
with the inductive step, note that we may assume

${\nu}_{i}^{(\zeta-\varepsilon)^{-\ell+1}}\geq
C_{0}^{\beta-1+\eta}\geq(8k)^{2d(\beta-1+\eta)/(\varepsilon^{2}(\beta-2))},$
(24)

since otherwise both the statements for $\ell$ and $\ell-1$ concern only
vertices of weight at least $C_{0}$, and thus the case $\ell$ follows
trivially from the statement for $\ell-1$. Let $v$ be a vertex with position
$x_{v}\in{B}_{i}$ and with weight $w_{v}\geq w_{i{{,\ell}}}$. We claim that
every vertex in distance at most
$r_{\ell}:=({\nu}_{i}^{(\zeta-\varepsilon)^{-\ell+1}}/n)^{1/d}$ with weight at
least $w_{i{{,\ell-1}}}$ has probability $\Omega(1)$ to connect to $v$.
Indeed, this follows from

$\displaystyle\frac{w_{i{{,\ell-1}}}w_{i{{,\ell}}}}{r_{\ell}^{d}n}$
$\displaystyle={\nu}_{i}^{[2-\beta-\eta+(\zeta-\varepsilon)^{-1}](\zeta-\varepsilon)^{-\ell+1}/(\beta-1+\eta)}$
$\displaystyle\geq{\nu}_{i}^{[\varepsilon(\beta-2)/2](\zeta-\varepsilon)^{-\ell+1}/(\beta-1+\eta)}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:weightMin}}}{{\geq}}(8k)^{d/\varepsilon}\geq
1$ (25)

Since $\ell\geq 1$, we have $r_{\ell}\leq({\nu}_{i}/n)^{1/d}$, which is the
radius corresponding to the ball ${B}_{i}$. Hence, if we consider a ball
around $v$ with radius $r_{\ell}$, then at least a $2^{-d}$ proportion of this
ball falls into ${B}_{i}$. Therefore, the expected size of $N_{\ell-1}(v)$
satisfies

$\displaystyle\mathbb{E}[|N_{\ell-1}(v)|]$
$\displaystyle=\Omega(1)2^{-d}r_{\ell}^{d}nw_{i{{,\ell-1}}}^{1-\beta+\eta}{\nu}_{i}^{[\varepsilon(\beta-2)/2](\zeta-\varepsilon)^{-\ell+1}/(\beta-1+\eta)}$
$\displaystyle\geq
c2^{-d}{\nu}_{i}^{\left[\varepsilon(\beta-2)/2+2\eta)\right](\zeta-\varepsilon)^{-\ell+1}/(\beta-1+\eta)}$

for some constant $c>0$ and any sufficiently large $n$. Furthermore, if the
constant $\varepsilon>0$ is sufficiently small we obtain

$\displaystyle\mathbb{E}[|N_{\ell-1}(v)|]$ $\displaystyle\geq
2^{-d/\varepsilon}{\nu}_{i}^{[\varepsilon(\beta-2)/2](\zeta-\varepsilon)^{-\ell+1}/(\beta-1+\eta)}\stackrel{{\scriptstyle\eqref{eq:weightMin}}}{{\geq}}(4k)^{d/\varepsilon}\geq
8k.$

Recall that $|N_{\ell-1}(v)|$ is a Poisson distributed random variable and
thus we have

$\displaystyle\Pr[|N_{\ell-1}(v)|<k]$
$\displaystyle\leq\exp(-\mathbb{E}[|N_{\ell-1}(v)|]/4)\cdot\exp(-\mathbb{E}[|N_{\ell-1}(v)|]/4)$
$\displaystyle\leq\exp(-2k)\exp\left(-4^{-d/\varepsilon}{\nu}_{i}^{[\varepsilon(\beta-2)/2](\zeta-\varepsilon)^{-\ell+1}/(\beta-1+\eta)}\right).$

So assume that $|N_{\ell-1}(v)|\geq k$, and pick any $k$ vertices
$v_{1},\ldots,v_{k}\in N_{\ell-1}(v)$. By induction hypothesis,

$\displaystyle\Pr[v_{1}\not\in A(i+\ell+1)]$
$\displaystyle\leq\exp\left[-4^{-d/\varepsilon}{\nu}_{i}^{[\varepsilon(\beta-2)/2](\zeta-\varepsilon)^{-\ell+2}/(\beta-1+\eta)}\right]$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:weightMin}}}{{\leq}}\exp\left[-2\cdot
4^{-d/\varepsilon}{\nu}_{i}^{[\varepsilon(\beta-2)/2](\zeta-\varepsilon)^{-\ell+1}/(\beta-1+\eta)}\right]$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:weightMin}}}{{\leq}}\exp(-k^{d})\exp\left[-4^{-d/\varepsilon}{\nu}_{i}^{[\varepsilon(\beta-2)/2](\zeta-\varepsilon)^{-\ell+1}/(\beta-1+\eta)}\right]$

where the second inequality holds since $\zeta-\varepsilon\geq 1+\varepsilon$
for any sufficiently small $\varepsilon>0$. The same bound applies to the
other $v_{j}$. By a simple union bound,

$\Pr[v_{1},\ldots,v_{k}\in A(i+\ell+1)]\geq
1-k\exp(-k^{d})\exp\left[-4^{-d/\varepsilon}{\nu}_{i}^{[\varepsilon(\beta-2)/2]\frac{(\zeta-\varepsilon)^{-\ell+1}}{\beta-1+\eta}}\right].$

Hence,

$\displaystyle\Pr[v\not\in A(i+\ell+2)]$
$\displaystyle\leq\Pr[|N_{\ell-1}(v)|<k]+\Pr[\\{v_{1},\ldots,v_{k}\\}\not\subseteq
A(i+\ell+1)]$
$\displaystyle\leq\left(\exp(-2k)+k\exp(-k^{d})\right)\exp\left[-4^{-d/\varepsilon}{\nu}_{i}^{[\varepsilon(\beta-2)/2]\frac{(\zeta-\varepsilon)^{-\ell+1}}{\beta-1+\eta}}\right]$
$\displaystyle\leq\exp\left[-4^{-d/\varepsilon}{\nu}_{i}^{[\varepsilon(\beta-2)/2]\frac{(\zeta-\varepsilon)^{-\ell+1}}{\beta-1+\eta}}\right]$
$\displaystyle=\exp\left[-C_{1}{\nu}_{i}^{C_{2}(\zeta-\varepsilon)^{-\ell}}\right]$

as required.

For $\alpha=\infty$, Equation (25) does not imply that the corresponding
vertices connect with probability $\Omega(1)$, but it suffices to decrease
$r_{\ell}$ by at most a constant factor to ensure this property. This can be
compensated by changing (for example) $C_{1}$. We omit the details. ∎

##  7\. Infection times: Proof of Theorem 4

###### Proof.

Let $v=(x_{v},w_{v})$ be an fixed vertex that satisfies the conditions in
Theorem 4. Let $\varepsilon>0$ be a constant and let
$\eta=\eta(\varepsilon)>0$ be a constant which is sufficiently small compared
to $\varepsilon$, cf. Section 2.3.

First we remark that it suffices to show that for every sufficiently small
$\varepsilon>0$, whp $L_{v}=(1\pm O(\varepsilon))\Lambda{(x_{v},w_{v})}\pm
O(1)$, where the hidden constants are both independent of $\varepsilon$. Then
by a standard diagonalizing argument, we also have whp $L_{v}=(1\pm
o(1))\Lambda{(x_{v},w_{v})}\pm O(1)$. We split the proof in three parts (I),
(II) and (III), “typical” vertices are treated in (III):

(I): Assume that $w_{v}>(\|x_{v}\|^{d}n)^{1/(\beta-1)}$ and the maximum in (4)
is $0$, i.e. we also have $w_{v}\geq\|x_{v}\|^{d}n/\nu$. In this case, the
lower bound on $L_{v}$ is trivial, so we show the upper bound. Since then the
second term in the maximum must be non-positive, we have $\|x_{v}\|^{d}n\leq
w_{v}\nu$. Let $i\geq 1$ be so large that
$(\zeta-\varepsilon)^{i}/(\beta-1+\eta)>1$, but observe that we may still
choose $i=O(1)$.

Assume first $\|x_{v}\|^{d}n\leq{\nu}_{i}$, so $x_{v}\in{B}_{i}$. By the
technical condition in Theorem 4 we have
$\|x_{v}\|^{d}n\geq\widetilde{\nu}_{0}$, and hence
$w_{v}\geq\widetilde{\nu}_{0}^{1/(\beta-1)}=\nu^{\Omega(1)}={\nu}_{i}^{\Omega(1)}$.
Hence, we may choose $\ell=O(1)$ such that $w_{v}\geq
w_{i{{,\ell}}}={\nu}_{i}^{(\zeta-\varepsilon)^{-\ell}/(\beta-1+\eta)}$, and it
follows directly from part (c) of Theorem 19 that whp $v$ is active after
$i+\ell+3=O(1)$ rounds, as required.

On the other hand, if $\|x_{v}\|^{d}n\geq{\nu}_{i}$ then every vertex in
${B}_{i}$ has distance at most $3\|x_{v}\|^{d}n$ from $v$. Let
$w_{i{}}:={\nu}_{i}^{1/(\beta-1+\eta)}$. By Theorem 19, after $i+3$ rounds all
vertices in ${V}_{\geq w_{i{}}}{}{{\cap\,{B}_{i}}}$ are active whp, and there
are ${\nu}_{i}^{\Omega(\eta)}=\omega(1)$ many such vertices. Note that any
such vertex has probability $\Omega(1)$ to form an edge with $v$, since
$w_{v}w_{i{}}/(3^{d}\|x_{v}\|^{d}n)\geq w_{i{}}/(3^{d}\nu)=\Omega(1)$.
Therefore, whp $v$ is active in round $i+4=O(1)$, again as required.

(II): Assume that still $w_{v}>(\|x_{v}\|^{d}n)^{1/(\beta-1)}$, but that the
maximum in (4) is attained by the second term, i.e.
$\|x_{v}\|^{d}n/w_{v}\geq\nu$. We need to show an upper and a lower bound on
$L_{v}$. For the upper bound, choose $i\geq 0$ minimal such that

$\|x_{v}\|^{d}n/w_{v}\leq w_{i},$ (26)

where
$w_{i{}}={\nu}_{i}^{1/(\beta-1+\eta)}=\nu^{(\zeta-\varepsilon)^{i}/(\beta-1+\eta)}$
as before. Observe that this $i$ satisfies

$i=\log\log_{\nu}(\|x_{v}\|^{d}n/w_{v})/\log(\zeta-\varepsilon)+O(1)\leq(1+O(\varepsilon))\Lambda{(x_{v},w_{v})}+O(1).$

By Theorem 19, whp all vertices in ${V}_{\geq w_{i{}}}{}{{\cap\,{B}_{i}}}$ are
active in round $i+3$, and there are $\omega(1)$ of them. As in (I), we
discriminate two sub-cases.

Either $\|x_{v}\|^{d}n\geq{\nu}_{i}$. In this case, the distance from $v$ to
any point in ${B}_{i}$ is at most $3\|x_{v}\|$, and $v$ has probability
$\Omega(1)$ to form an edge with each vertex in ${V}_{\geq
w_{i{}}}{}{{\cap\,{B}_{i}}}$ by (26). By Theorem 19, whp all these vertices
are active in round $i+3$, and there are $\omega(1)$ of them, so whp $v$ will
be active in round $i+4$.

Or $\|x_{v}\|^{d}n\leq{\nu}_{i}$, hence $x_{v}\in{B}_{i}$. Furthermore we have
$w_{v}>(\|x_{v}\|^{d}n)^{1/(\beta-1)}\geq(w_{i-1{}}w_{v})^{1/(\beta-1)}$ by
minimality of $i$ in (26), implying $w_{v}>w_{i-1{}}^{1/(\beta-2)}\geq
w_{i{}}$. Thus by Theorem 19 whp $v$ is active in round $i+3$. In either case,
whp $v$ is active in round $i+O(1)$, i.e. $L_{v}\leq
i+O(1)\leq(1+O(\varepsilon))\Lambda{(x_{v},w_{v})}+O(1)$, as required.

For the lower bound, if
$\|x_{v}\|^{d}n/w_{v}\leq\widetilde{\nu}_{0}=\nu^{(\beta-1)/(\beta-2)+\varepsilon}$
then $\Lambda{(x_{v},w_{v})}=O(1)$, so there is nothing to show.

Otherwise,
$\|x_{v}\|^{d}n/w_{v}\geq\widetilde{\nu}_{0}\geq\widetilde{\nu}_{0}^{1/(\beta-1-\eta)}$,
so we may choose $i\geq 0$ to be maximal such that

$\|x_{v}\|^{d}n/w_{v}\geq\tilde{w}_{i},$ (27)

where
$\tilde{w}_{i{}}=\widetilde{\nu}_{i}^{1/(\beta-1-\eta)}=\widetilde{\nu}_{0}^{{(\zeta+\varepsilon)^{i}/(\beta-1-\eta)}}$
as before. Note that this $i$ satisfies

$i=\log\log_{\nu}(\|x_{v}\|^{d}n/w_{v})/\log(\zeta+\varepsilon)-O(1)\geq(1-O(\varepsilon))\Lambda{(x_{v},w_{v})}-O(1).$

Let $\ell=O(1)$ be sufficiently large such that $\zeta^{\ell}>(\beta-1-\eta)$.
If $i\leq\ell$, then $i=O(1)$, and there is nothing to show. Otherwise, (27)
implies in particular

$\|x_{v}\|^{d}n\geq\Omega(1)\widetilde{\nu}_{i}^{1/(\beta-1-\eta)}=\Omega(1)\widetilde{\nu}_{i-\ell}^{(\zeta+\varepsilon)^{\ell}/(\beta-1-\eta)}>2\widetilde{\nu}_{i-\ell}.$

Hence, by Lemma 14 (with $C=2^{1/d}>1$) we obtain

$\displaystyle\mathbb{E}[N(v)\cap\widetilde{B}_{i-\ell}]$
$\displaystyle=O(1)\widetilde{\nu}_{i-\ell}\left(\|x_{v}\|^{d}n/w_{v}\right)^{1-\beta+\eta}.$

Using (27), we may continue

$\displaystyle\mathbb{E}[{N}{(v)}{{\cap\,\widetilde{B}_{i-\ell}}}]$
$\displaystyle=O(1)\widetilde{\nu}_{i-\ell}/\widetilde{\nu}_{i}=\widetilde{\nu}_{i}^{-\Omega(1)},$

where the last step holds for any $\ell\geq 1$. By Markov’s inequality, whp
$v$ has no neighbours in $\widetilde{B}_{i-\ell}$. On the other hand, by
Theorem 17 whp there is no active vertex outside of $\widetilde{B}_{i-\ell}$
in round $i-\ell$. Therefore, whp $v$ is not active in round $i-\ell+1$, i.e.
$L_{v}>i-\ell+1\geq(1-O(\varepsilon))\Lambda{(x_{v},w_{v})}-O(1)$, as
required.

(III): Assume $w_{v}\leq(\|x_{v}\|^{d}n)^{1/(\beta-1)}$. Again we need to show
an upper and a lower bound for $L_{v}$. For the _upper bound_ , let $i\geq 0$
be minimal with the property that $x_{v}\in{B}_{i}$, i.e.

$\|x_{v}\|^{d}n\leq{\nu}_{i}=\nu^{(\zeta-\varepsilon)^{i}}$ (28)

Observe that $i\geq 1$ because $\|x_{v}\|^{d}n\geq\widetilde{\nu}_{0}>\nu$ due
to the technical assumption in Theorem 4 and since the function $\Lambda{}$ is
non-negative. Thus, we have
$\|x_{v}\|^{d}n\geq{\nu}_{i-1}={\nu}_{i}^{1/(\zeta-\varepsilon)}$ by
minimality of $i$. Let $\ell\geq 0$ be minimal with the property that

$w_{v}>(\|x_{v}\|^{d}n)^{(\zeta-\varepsilon)^{-\ell}/(\beta-1+\eta)}$ (29)

Since we are in the case $w_{v}\leq(\|x_{v}\|^{d}n)^{1/(\beta-1)}$, we have
$\ell\geq 1$, and thus (29) is false if we replace $\ell$ by $\ell-1$. By
minimality of $i$, the right hand side of (29) is at least
${\nu}_{i}^{(\zeta-\varepsilon)^{-\ell-1}/(\beta-1+\eta)}$ and recall that we
only consider weights $w_{v}=\omega(1)$. Hence, Theorem 19 applies for
$\ell+1$, and, if we condition on events that hold whp, tells us that $v$ is
active in round $i+\ell+4$ with probability

$1-\exp\left[-C_{1}{\nu}_{i}^{C_{2}(\zeta-\varepsilon)^{-\ell-1}}\right]=1-o(1),$

where the last inequality holds due to the following estimate

${\nu}_{i}^{(\zeta-\varepsilon)^{-\ell-1}}\stackrel{{\scriptstyle\eqref{eq:speedupper2}}}{{\geq}}(\|x_{v}\|^{d}n)^{(\zeta-\varepsilon)^{-\ell-1}}\stackrel{{\scriptstyle\eqref{eq:speedupper3},\ell-1}}{{\geq}}w_{v}^{(\beta-1+\eta)/(\zeta-\varepsilon)^{2}}=\omega(1).$

It remains to note that by choice of $i$ and $\ell$ we have

$i=\log\log_{\nu}(\|x_{v}\|^{d}n)/\log(\zeta-\varepsilon)+O(1)$

and $\ell=i+\log\log_{\nu}w_{v}/\log(\zeta-\varepsilon)+O(1)$. Hence, whp
$L_{v}\leq i+\ell+4\leq(1+O(\varepsilon))\Lambda{(x_{v},w_{v})}+O(1)$, as
required.

For the _lower bound_ , we distinguish yet two more sub-cases. Let $\ell\geq
0$ be the smallest non-negative integer that satisfies

$w_{v}^{2}\geq
2^{-(\ell+1)d}(\|x_{v}\|^{d}n)^{(\zeta+\varepsilon)^{-\ell-3}/(\beta-1)}.$
(30)

(IIIa) Assume first that $\|x_{v}\|^{d}n\geq 2^{\ell+1}\widetilde{\nu}_{0}$.
In this case, let $i\geq 1$ be maximal with the property

$\|x_{v}\|^{d}n\geq
2^{\ell+1}\widetilde{\nu}_{i-1}=2^{\ell+1}\widetilde{\nu}_{0}^{(\zeta+\varepsilon)^{i-1}}.$
(31)

It is easy to check (e.g., by using the very generous estimate
$2<\widetilde{\nu}_{0}^{(\zeta+\varepsilon)^{i}}$) that $i$ satisfies

$i\geq\log\log_{\nu}(\|x_{v}\|^{d}n)/\log(\zeta+\varepsilon)-O(\log(\ell+1)).$
(32)

If $\ell=O(1)$ then $w_{v}=(\|x_{v}\|^{d}n)^{\Theta(1)}$ and therefore

$\Lambda{(x_{v},w_{v})}=\log\log_{\nu}(\|x_{v}\|^{d}n)/|\log(\beta-2)|\pm
O(1).$

Since by Theorem 17 (c) whp no vertex outside of $\widetilde{B}_{i-1}$ is
active in round $i-1$ and $x_{v}\not\in\widetilde{B}_{i-1}$, we have whp
$L_{v}>i-1\geq(1-O(\varepsilon))\Lambda{(x_{v},w_{v})}-O(1)$, as required.

Next observe that there exists $0\leq j\leq O(\log(\ell+1))$ such that
$\|x_{v}\|^{d}n\leq\widetilde{\nu}_{i+j}$. In particular, if $\ell>C$ for some
sufficiently large constant $C>0$ then $j<\ell$. Since we have already treated
the case $\ell=O(1)$, we may henceforth assume that $\ell>C$. Then $\ell-j>0$,
and by (31) the requirements of Theorem 17 (f) are met for $i$ and $\ell-j$.
By minimality of $\ell$,

$\displaystyle w_{v}^{2}$ $\displaystyle\leq 2^{-\ell
d}(\|x_{v}\|^{d}n)^{(\zeta+\varepsilon)^{-\ell-2}/(\beta-1)}\leq 2^{-\ell
d}\widetilde{\nu}_{i+j}^{(\zeta+\varepsilon)^{-\ell-2}/(\beta-1)}$
$\displaystyle=2^{-\ell
d}\widetilde{\nu}_{i}^{(\zeta+\varepsilon)^{-(\ell-j)-2}/(\beta-1)},$ (33)

and therefore Theorem 17 (f) yields that $v$ is not active in round $i+\ell-j$
with probability at least

$1-w_{v}2^{(\ell-j)d}\widetilde{\nu}_{i}^{-(\zeta+\varepsilon)^{-(\ell-j)-2}/(\beta-1)}\stackrel{{\scriptstyle\eqref{eq:speedlower5}}}{{\geq}}1-w_{v}^{-1}2^{-jd}=1-o(1).$

In order to relate $i+\ell-j$ with $\Lambda{(x_{v},w_{v})}$, we derive
$\|x_{v}\|^{d}n\geq\widetilde{\nu}_{0}^{(\zeta+\varepsilon)^{i-1}}$ from (31),
and plug it into (30) to obtain

$w_{v}^{2}\geq
2^{-(\ell+1)d}\widetilde{\nu}_{0}^{(\zeta+\varepsilon)^{i-\ell-4}/(\beta-1)}=2^{-(\ell+1)d}\nu^{\Theta(1)(\zeta+\varepsilon)^{i-\ell}}.$

Hence, taking logarithms on both sides,

$\Theta(1)(\zeta+\varepsilon)^{i-\ell}\log\nu\leq 2\log w_{v}+(\ell+1)d\log
2\leq O(\max\\{\log w_{v},\ell\\}).$ (34)

If the maximum is attained by $\log w_{v}$, then (34) gives $\ell\geq
i-\log\log_{\nu}w_{v}/\log(\zeta+\varepsilon)-O(1)$, and together with (32)
and $j=O(\log(1+\ell))$, we conclude
$i+\ell-j\geq(1-O(\varepsilon))\Lambda{(x_{v},w_{v})}-O(1)$, as required. On
the other hand, of the maximum in (34) is attained by $\ell$, then (34) yields

$\ell+O(\log\ell)\geq i+\frac{\log\log\nu}{\log(\zeta+\varepsilon)}-O(1)\geq
i-\frac{\log\log_{\nu}w_{v}}{\log(\zeta+\varepsilon)}-O(1),$

where the second inequality comes from $w_{v}=\omega(1)$. Thus we obtain again
$i+\ell-j\geq(1-O(\varepsilon))\Lambda{(x_{v},w_{v})}-O(1)$, as required. This
concludes the proof of the lower bound in the case $\|x_{v}\|^{d}n\geq
2^{\ell+1}\widetilde{\nu}_{0}$.

(IIIb) Assume $\|x_{v}\|^{d}n\leq 2^{\ell+1}\widetilde{\nu}_{0}$. It remains
to show the lower bound on $L_{v}$ in this case. We want to apply Theorem 17
(f) for $i=0$, but we need to change the definition of $\ell$ slightly. Let
$\ell^{\prime}\geq 0$ be minimal with the property

$w_{v}^{2}\geq
2^{-(\ell^{\prime}+1)d}\widetilde{\nu}_{0}^{(\zeta+\varepsilon)^{-\ell^{\prime}-3}/(\beta-1)}.$
(35)

Similar as before, this definition implies
$\ell^{\prime}+O(\log(\ell^{\prime}+1))\geq-\log\log_{\nu}w_{v}/\log(\zeta+\varepsilon)-O(1)$.
If $\ell^{\prime}\leq 1$ then $w_{v}=\widetilde{\nu}_{0}^{\Omega(1)}$. In this
case, since $\|x_{v}\|^{d}n\leq 2^{\ell+1}\widetilde{\nu}_{0}$, a sufficient
condition for $\ell$ to satisfy (30) is

$\widetilde{\nu}_{0}^{\Omega(1)}\geq
2^{-(\ell+1)d}(2^{\ell+1}\widetilde{\nu}_{0})^{(\zeta+\varepsilon)^{-\ell-3}/(\beta-1)},$

which is already satisfied for $\ell=O(1)$. Since $\ell$ was chosen minimally,
this implies $\ell=O(1)$ and thus $\|x_{v}\|^{d}n=\widetilde{\nu}_{0}^{O(1)}$,
and the lower bound is trivial. So assume instead that $\ell^{\prime}>1$. Let
$\ell^{*}:=\min\\{\ell^{\prime}-1,\Lambda{(x_{v},w_{v})}\\}$. Then by the
assumption in Theorem 4, we have
$\ell^{*}\leq\log_{2}(\|x_{v}\|^{d}n/\widetilde{\nu}_{0})$, and hence
$\|x_{v}\|^{d}n\geq 2^{\ell^{*}}\widetilde{\nu}_{0}$. Since
$\ell^{*}<\ell^{\prime}$, the reverse of (35) holds. These two properties
allow us to apply Theorem 17 (f) with $i=0$ and $\ell^{*}-1$, which tells us
that $v$ is not active in round $\ell^{*}-1$ with probability at least
$1-w_{v}^{-1}=1-o(1)$. It remains to relate $\ell^{*}$ with
$\Lambda{(x_{v},w_{v})}$. To this end, all that remains to be shown is that
$\log\log_{\nu}(\|x_{v}\|^{d}n)=o(\ell^{\prime})+O(1)$. Since
$\|x_{v}\|^{d}n\leq 2^{\ell+1}\widetilde{\nu}_{0}$, we have
$\log_{\nu}(\|x_{v}\|^{d}n)\leq o(\ell)+O(1)$. However, by minimality of
$\ell$, we have

$w_{v}^{2}\leq 2^{-\ell
d}(\|x_{v}\|^{d}n)^{(\zeta+\varepsilon)^{-\ell-2}/(\beta-1-\eta)}\leq(2^{\ell+1}\widetilde{\nu}_{0})^{(\zeta+\varepsilon)^{-\ell-2}/(\beta-1)},$

and similar as for (31) it can be easily deduced that
$\ell=O(\log\log_{\nu}w_{v})=O(\ell^{\prime})$. This concludes the proof for
the case $\|x_{v}\|^{d}n\leq 2^{\ell}\widetilde{\nu}_{0}$. ∎

##  8\. Threshold and speed of the process: Proof of Theorem 1 and Theorem 2

We prove Theorem 1 and Theorem 2 together. Let $\varepsilon>0$ be a constant
and let $\eta=\eta(\varepsilon)>0$ be a constant which is sufficiently small
compared to $\varepsilon$, cf. Section 2.3.

We first show the second statement of Theorem 2.

######  Claim 21.

Assume that $\alpha>\beta-1$ and $\nu=n^{o(1)}$, then
$|{V}^{{\leq(1-\varepsilon)i_{\infty}}}{}{}|=o(n)$ whp.

###### Proof.

Let $i_{0}$ be (somewhat arbitrary) the largest integer such that
$\widetilde{\nu}_{i_{0}-1}\leq n/\log^{2}n$ and note that then
$i_{0}\geq(1-O(\varepsilon))(\log\log_{\nu}n)/|\log(\beta-2)|$. Moreover, for
$i_{1}:=(1-\varepsilon)(\log\log n)/|\log(\beta-2)|$ we have
$2^{i_{1}}\widetilde{\nu}_{i_{0}-1}=o(n)$, so whp there are $o(n)$ vertices in
$2^{i_{1}}\widetilde{B}_{i_{0}-1}$. Next consider the vertices outside of
$2^{i_{1}}\widetilde{B}_{i_{0}-1}$. By Theorem 17 each such vertex of weight
at most $\log\log n$ has probability $o(1)$ to be in ${V}^{{\leq
i_{0}+i_{1}}}{}{}$. Therefore, the expected number of vertices of weight at
most $\log\log n$ in ${V}^{{\leq i_{0}+i_{1}}}{}{}$ is $o(n)$. On the other
hand, the total expected number of vertices of weight larger than $\log\log n$
is also $o(n)$. Altogether, this shows $\mathbb{E}[|{V}^{{\leq
i_{0}+i_{1}}}{}{}|]=o(n)$, and the statement follows from Markov’s inequality.
∎

### Subcritical regime: (iii), (v).

We will indeed show that whp the process does not infect any vertices in the
first step.

######  Claim 22.

${V}^{{\leq 1}}{}{}={V}^{{\leq 0}}{}{}$ whp.

###### Proof.

For any vertex $v=(x_{v},w_{v})$ with fixed weight and position we denote by
$\mu_{v}:=\mathbb{E}[|{N}{(v)}{{\cap\,B_{0}}}|]$ its expected number of
neighbours in $B_{0}$. We have shown in Lemma 14 that for any constant $C>1$,

$\mu_{v}=O(\nu)\cdot\begin{cases}\min\left\\{w_{v}/\nu,1\right\\},&\text{if
}\|x_{v}\|\leq C(\nu/n)^{1/d}/2,\\\
\min\left\\{\left(w_{v}/(\|x_{v}\|^{d}n)\right)^{m},1\right\\}&\text{if
}\|x_{v}\|\geq C(\nu/n)^{1/d}/2,\end{cases}$ (36)

where $m=\min\\{\alpha,\beta-1-\eta\\}>1$. Since initially only vertices in
$B_{0}$ are activated, recall that the number ${N}^{{\leq 0}}{(v)}{}$ of
_initially active_ neighbours of $v$ is Poisson distributed with mean
$\rho\mu_{v}$. In particular, $\Pr[|{N}^{{\leq 0}}{(v)}{}|\geq
k]=\Pr[\mathrm{Po}\left(\rho\mu_{v}\right)\geq
k]=O(1)\min\\{(\rho\mu_{v})^{k},1\\}$. Clearly, we can bound the number
$|{V}^{{=1}}{}{}|$ of vertices that turn active in round $1$ by the number of
vertices that have at least $k$ neighbours in ${V}^{{\leq 0}}{}{}$. (It is
only an upper bound since the latter also counts vertices which were already
in ${V}^{{\leq 0}}{}{}$.)

So let us first consider the contribution
$n_{\mathrm{in}}:=|{V}^{{=1}}{}{{\cap\,2B_{0}}}|$ of vertices
$v=(x_{v},w_{v})$ inside of $2B_{0}$. By (36) these satisfy
$\mu_{v}=O(w_{v})$, and thus by Lemma 10 and 11 we obtain

$\mathbb{E}[n_{\mathrm{in}}]=O(1)\int_{0}^{\infty}\nu
w^{1-\beta+\gamma}\frac{d}{dw}\min\\{(\rho
w)^{k},1\\}dw=O(\nu\rho^{\beta-1-\gamma})=o(1),$ (37)

where $\gamma=0$ in case of a strong power-law, and otherwise $\gamma$ is an
arbitrary positive constant.

On the other hand, to estimate the contribution
$n_{\mathrm{out}}:=|{V}^{{=1}}{}{{\cap\,(\mathbb{T}^{d}\setminus 2B_{0})}}|$
of vertices $v=(x_{v},w_{v})$ outside of $2B_{0}$, we may use
$\mu_{v}=O(\nu)(w_{v}/(\|x_{v}\|^{d}n))^{m}$ by (36). Furthermore, since each
such vertex has distance at least $(\nu/n)^{1/d}$ from the origin, Lemma 10
and Lemma 11 imply

$\displaystyle\mathbb{E}[n_{\mathrm{out}}]$
$\displaystyle=O(1)\int_{(\nu/n)^{1/d}}^{\infty}r^{d-1}n\int_{0}^{\infty}w^{1-\beta+\eta}\frac{d}{dw}\min\left\\{\left(\rho\nu\left(\frac{w}{r^{d}n}\right)^{m}\right)^{k},1\right\\}dwdr$
$\displaystyle=O(1)\int_{(\nu/n)^{1/d}}^{\infty}r^{d-1}n\left(\frac{r^{d}n}{(\rho\nu)^{1/m}}\right)^{1-\beta+\eta}dr$
$\displaystyle=O(1)\nu^{2-\beta+\eta}(\rho\nu)^{(\beta-1+\eta)/m}$

Now we use that $\rho=O(\nu^{-1/(\beta-1)})$. Observe that this bound holds
both in case (iii) and (v), and that it even holds for the critical case (ii).
We derive $\rho\nu=O(\nu^{(\beta-2)/(\beta-1)})$, and hence
$\mathbb{E}[n_{\mathrm{out}}]=\nu^{-(\beta-2)(1-1/m)+O(\eta)}$. Thus, since
$m>1$, if $\eta>0$ is small enough we have

$\mathbb{E}[n_{\mathrm{out}}]=o(1).$ (38)

We will later use the fact that this also holds in the critical regime (ii).

Together (37) and (38) show that $\mathbb{E}[|{V}^{{=1}}{}{}|]=o(1)$, and thus
by Markov’s inequality whp no vertices turned active in round $1$, as claimed.
∎

### Critical regime: (ii).

We first show that with constant probability no further vertices are ever
activated.

######  Claim 23.

${V}^{{\leq 1}}{}{}={V}^{{\leq 0}}{}{}$ with probability $\Omega(1)$.

###### Proof.

First observe that (38) also holds in this regime, i.e. by Markov’s inequality
whp no vertex outside of $2B_{0}$ is active in round $1$. Furthermore, let
$\xi>0$ be a (small) constant, to be determined later, and let
$w_{0{}}:=\nu^{1/(\beta-1)}$. Moreover, note that $|{V}_{\geq\xi
w_{0{}}}{}{{\cap\,2B_{0}}}|$ is Poisson distributed with mean $O(\nu(\xi
w_{0{}})^{1-\beta})=O(1)$, since $\xi=\Omega(1)$. Therefore the event
$\mathcal{A}:=\\{{V}_{\geq\xi w_{0{}}}{}{{\cap\,2B_{0}}}=\emptyset\\}$ occurs
with probability at least $\exp[-O(1)]=\Omega(1)$. Consequently it suffices to
show that ${V}_{\leq\xi w_{0{}}}^{{\leq 1}}{}{{\cap\,2B_{0}}}={V}^{{\leq
0}}{}{}$ with probability $\Omega(1)$ if we condition on the event
$\mathcal{A}$.

Since every vertex $v=(x_{v},w_{v})$ satisfies
$\mathbb{E}[|{N}{(v)}{{\cap\,B_{0}}}|]\leq\mathbb{E}[|{N}{(v)}{}|]=O(w_{v})$,
by (11), the number of neighbours in ${V}^{{\leq 0}}{}{}$ is a Poisson
distributed random variable with mean at most $O(\rho w_{v})$. Observe that
this upper bound remains valid if we condition on the event $\mathcal{A}$,
since this can only decrease the expected degree of $v$. Therefore we obtain

$\Pr\left[|{N}^{{\leq 0}}{(v)}{}|\geq
k\;\middle|\;\mathcal{A}\right]=O(1)\min\\{(\rho w_{v})^{k},1\\}=O((\rho
w_{v})^{k}),$

and by Lemma 10 it follows that

$\displaystyle\mathbb{E}\left[|{V}_{\leq\xi
w_{0{}}}^{{=1}}{}{{\cap\,2B_{0}}}|\;\middle|\;\mathcal{A}\right]$
$\displaystyle=O\left(\nu(\xi w_{0{}})^{1-\beta}(\rho\xi
w_{0{}})^{k}+\int_{0}^{\xi w_{0{}}}\nu w^{1-\beta}\frac{d}{dw}(\rho
w)^{k}dw\right)$ $\displaystyle=O(1)\nu(\xi w_{0{}})^{1-\beta}(\rho\xi
w_{0{}})^{k}=O(\xi^{k+1-\beta}),$

where all the hidden constants are independent of $\xi$. Now note that we may
choose $\xi>0$ small enough such that $\mathbb{E}\left[|{V}_{\leq\xi
w_{0{}}}^{{=1}}{}{{\cap\,2B_{0}}}|\;\middle|\;\mathcal{A}\right]\leq 1/2$, and
then by Markov’s inequality $|{V}_{\leq\xi
w_{0{}}}^{{=1}}{}{{\cap\,2B_{0}}}|=0$ with conditional probability at least
$1/2$. Thus ${V}^{{\leq 1}}{}{}={V}^{{\leq 0}}{}{}$ with probability
$\Omega(1)$, and the claim follows. ∎

Next we show that with constant probability at least $k$ heavy vertices will
be activated in the first round. Afterwards, the remaining steps will be
identical with the supercritical regime, so we prove them together, cf. below.

######  Claim 24.

$|{V}_{\geq w_{0{}}}^{{=1}}{}{{\cap\,B_{0}}}|\geq k$ with probability
$\Omega(1)$.

###### Proof.

We first consider the case $\alpha<\infty$. Note that the number of vertices
in $B_{0}$ of weight at least $w_{0{}}=\nu^{1/(\beta-1)}$ is Poisson
distributed with mean $\Theta(\nu w_{0}^{\beta-1})=\Theta(1)$. In particular,
with probability $\Omega(1)$ there are at least $k$ such vertices. So assume
this event holds, and let $v_{1},\dots,v_{k}$ be $k$ distinct such vertices.
For each $1\leq i\leq k$, denote by $K_{i}$ be the intersection of $B_{0}$
with the ball of volume $\nu^{1/(\beta-1)}/n$ around $v_{i}$. Note that
$n{\operatorname{Vol}\\!\left(K_{i}\right)}=\Omega(\nu^{1/(\beta-1)})$. The
number of vertices in ${V}^{{\leq 0}}{}{{\cap\,K_{i}}}$ is Poisson distributed
with mean $\rho n{\operatorname{Vol}\\!\left(K_{i}\right)}$, so in particular
$\Pr[|{V}^{{\leq 0}}{}{{\cap\,K_{i}}}|\geq k]=\Omega(1)$. Note that the events
$\mathcal{K}(i):=\\{|{V}^{{\leq 0}}{}{{\cap\,K_{i}}}|\geq k\\}$ are positively
associated for different $i$, i.e, conditioning on the events
$\mathcal{K}(i_{1}),\ldots,\mathcal{K}(i_{s})$ does not decrease the
probability of $\mathcal{K}(i)$ for any subset of (distinct) indices
$i_{1},\ldots,i_{s},i$. Hence,

$\Pr[\forall i\in\\{1,\ldots
k\\}:\mathcal{K}(i)]\geq\prod_{i=1}^{k}\Pr[\mathcal{K}(i)]=\Omega(1)$

by the law of conditional probability.

On the other hand, for each vertex $v$ with fixed weight and fixed position in
$K_{i}$ we have $\Pr[\\{v,v_{i}\\}\in
E]=\Omega(w_{0}/\nu^{1/(\beta-1)})=\Omega(1)$, and this lower bound is
independent for any two such vertices. So conditioned on the events
$\mathcal{K}(i)$, we have $\Pr[v_{i}\in{V}^{{\leq
1}}{}{}\mid\mathcal{K}(1),\ldots,\mathcal{K}(k)]=\Omega(1)$, and this lower
bound is independent for all $i$. Altogether, we have shown that with
probability $\Omega(1)$ we have $\\{v_{1},\dots,v_{k}\\}\subseteq{V}_{\geq
w_{0{}}}^{{=1}}{}{{\cap\,B_{0}}}$, proving the claim in the case of
$\alpha>\infty$.

The case $\alpha=\infty$ is completely analogous, except that it may be
necessary to shrink the balls around $v_{1},\ldots,v_{k}$ be at most a
constant factor, so that still every vertex in the $i$-th ball has probability
$\Omega(1)$ to connect to $v_{i}$. Since this only decreases the expected
number of (active) vertices in each ball by constant factors, the remaining
proof stays the same. We omit the details. ∎

### Supercritical regime: (i), (iv).

In this proof we also include the critical regime (ii), provided that at least
$k$ heavy vertices got activated in the first round, i.e. $|{V}_{\geq
w_{0{}}}^{{=1}}{}{{\cap\,B_{0}}}|\geq k$, where as before
$w_{0{}}=\nu^{1/(\beta-1)}$. Let $\varepsilon>0$ be constant.

######  Claim 25.

$\mathbb{E}[|{V}^{{\leq(1+\varepsilon)i_{\infty}}}{}{}|]=\Omega(n)$.

###### Proof.

Let $i\geq 0$ be the smallest index such that ${\nu}_{i}\geq n$ (and thus
${B}_{i}=\mathbb{T}^{d}$), and note that
$i\leq(1+\varepsilon)(\log\log_{\nu}n)/|\log(\beta-2)|$ if $n$ is sufficiently
large. Then there exists $\ell\leq(1+\varepsilon)(\log\log n)/|\log(\beta-2)|$
such that $w_{i{{,\ell}}}=O(1)$. Theorem 19 tells us immediately that every
vertex of weight at least $C$ has probability $\Omega(1)$ to be in
$A(i+3+\ell)$, for some sufficiently large constant $C>0$. Since the expected
number of vertices of weight at least $C$ is $\Omega(n)$, this already shows
the claim. ∎

It remains to proof the corresponding whp statement.

######  Claim 26.

$|{V}^{{\leq(1+\varepsilon)i_{\infty}}}{}{}|=\Omega(n)$ whp.

###### Proof.

Let $h=h(n)=\omega(1)$ be a function with $\log\log h=o(\log\log n)$. Then by
the same argument as before, every vertex of weight at least
$w_{h}:=\hat{w}_{-}(h)=h^{1/(\beta-1+\eta)}$ has probability
$1-h^{-\Omega(1)}$ to be in ${V}^{{\leq(1+\varepsilon/2)i_{\infty}}}{}{}$. Now
decompose the torus $\mathbb{T}^{d}$ into balls $Q_{1},\ldots,Q_{s}$ of volume
$\Theta(h/n)$.444This is possible since we use the $\infty$-norm. It would
also suffice to consider any disjoint balls with total volume $\Omega(1)$. Fix
any such ball $Q$, and call $Q$ _good_ if in round
$j:=(1+\varepsilon/2)i_{\infty}$ at least half of the vertices in ${V}_{\geq
w_{h}}{}{{\cap\,Q}}$ are active, and _bad_ otherwise. Recall that in
expectation only a $o(1)$ fraction of the vertices in ${V}_{\geq
w_{h}}{}{{\cap\,Q}}$ are inactive in round $j$, so by Markov’s inequality the
probability that $Q$ is bad is $o(1)$. So in expectation only a $o(1)$
fraction of the sets $Q_{1},\ldots,Q_{s}$ are bad, and again by Markov’s
inequality, whp at least half of them are good.

Now let $C>0$ be a sufficiently large constant, and assume $Q$ is good. Then
we may apply Remark 20 (for some suitably chosen $0\leq\ell=O(\log\log h)$) to
deduce that an expected $2/3$-fraction of the vertices in ${V}_{\geq
C}{}{{\cap\,Q}}$ are active in round $j+\ell$, if $C>0$ is sufficiently large.
In formula, $\mathbb{E}[|{V}_{\geq C}^{{\leq j+\ell}}{}{{\cap\,Q}}|]\geq
2\mathbb{E}[|{V}_{\geq C}{}{{\cap\,Q}}|]/3$, and thus by Markov’s inequality,

$\Pr\left[\left|{V}_{\geq C}^{{\leq
j+\ell}}{}{{\cap\,Q}}\right|\geq\mathbb{E}\left[\left|{V}_{\geq
C}{}{{\cap\,Q}}\right|\right]/2\right]=\Omega(1),$

and this bound holds independently of the activity in any other ball.
Therefore, by a Chernoff bound, whp an $\Omega(1)$ fraction of the balls
$Q_{1},\ldots,Q_{s}$ satisfy $|{V}_{\geq C}^{{\leq
j+\ell}}{}{{\cap\,Q}}|\geq\mathbb{E}\left[\left|{V}_{\geq
C}{}{{\cap\,Q}}\right|\right]/2=\Omega(h)$, and thus whp $|{V}^{{\leq
j+\ell}}{}{}|=\Omega(s\cdot h)=\Omega(n)$. Since
$j+\ell\leq(1+\varepsilon)i_{\infty}$ for sufficiently large $n$, the claim
follows. ∎

### Proof of Theorem 1 and Theorem 2

###### Proof.

Theorem 1 follows from Claims 22, 23, 24 and 26, while Theorem 2 is proven by
Claims 21 and 26. ∎

##  9\. Concluding remarks

We have shown that in the GIRG model for scale-free networks with underlying
geometry, even a small region can cause an infection that spreads through a
linear part of the population. We have analysed the process in great detail,
and we have determined its metastability threshold, its speed, and the time at
which individual vertices become active. Moreover, we have shown how a policy-
maker can utilize this knowledge to enforce a successful quarantine strategy.
We want to emphasize that the latter result is only a proof of concept,
intended to illustrate the possibilities that come from a thorough
understanding of the role of the underlying geometry in infection processes.
In particular, we want to remind the reader that bootstrap percolation is not
a perfect model for viral infections (though it has been used to this end),
but is more adequate for processes in which the probability of transmission
grows more than proportional if more than one neighbours is active, like
believes spreading through a social network (“What I tell you three times is
true.”), or action potential spreading through a neuronal network.

Therefore, this paper is only a first step. There are many other models for
the spreading of activity, most notably SIR and SIRS models for
epidemiological applications, and we have much yet to learn from analysing
these models in geometric power-law networks like GIRGs. From a technical
point of view, it is unsatisfactory that our analysis does not include the
case $\alpha\leq\beta-1$. We believe that also in this case, the bootstrap
percolation process is essentially governed by the geometry of the underlying
space, only in a more complex way. Understanding this case would probably also
add to our toolbox for analysing less “clear-cut” processes.

## References

  * [1] Joan Adler and Uri Lev, _Bootstrap percolation: visualizations and applications_ , Brazilian Journal of Physics 33 (2003), no. 3, 641–644.
  * [2] William Aiello, Anthony Bonato, Colin Cooper, Jeanette Janssen, and Paweł Prałat, _A spatial web graph model with local influence regions_ , Internet Mathematics 5 (2008), no. 1-2, 175–196.
  * [3] Michael Aizenman and Joel Lebowitz, _Metastability effects in bootstrap percolation_ , Journal of Physics A: Mathematical and General 21 (1988), no. 19, 3801.
  * [4] Réka Albert and Albert-László Barabási, _Statistical mechanics of complex networks_ , Reviews of modern physics 74 (2002), no. 1, 47.
  * [5] Hamed Amini, _Bootstrap percolation in living neural networks_ , Journal of Statistical Physics 141 (2010), no. 3, 459–475.
  * [6] Hamed Amini, Rama Cont, and Andreea Minca, _Resilience to contagion in financial networks_ , Mathematical finance (2013).
  * [7] Hamed Amini and Nikolaos Fountoulakis, _Bootstrap percolation in power-law random graphs_ , Journal of Statistical Physics 155 (2014), no. 1, 72–92.
  * [8] József Balogh, Béla Bollobás, Hugo Duminil-Copin, and Robert Morris, _The sharp threshold for bootstrap percolation in all dimensions_ , Transactions of the American Mathematical Society 364 (2012), no. 5, 2667–2701.
  * [9] József Balogh, Yuval Peres, and Gábor Pete, _Bootstrap percolation on infinite trees and non-amenable groups_ , Combinatorics, Probability and Computing 15 (2006), no. 05, 715–730.
  * [10] Albert-László Barabási, _Network science: Luck or reason_ , Nature 489 (2012), no. 7417, 507–508.
  * [11] Gareth Baxter, Sergey Dorogovtsev, Alexander Goltsev, and José Mendes, _Bootstrap percolation on complex networks_ , Physical Review E 82 (2010), no. 1, 011103.
  * [12] Marián Boguñá, Dmitri Krioukov, and Kimberly Claffy, _Navigability of complex networks_ , Nature Physics 5 (2009), no. 1, 74–80.
  * [13] Marián Boguñá, Fragkiskos Papadopoulos, and Dmitri Krioukov, _Sustaining the internet with hyperbolic mapping_ , Nature communications 1 (2010), 62.
  * [14] Milan Bradonjić and Iraj Saniee, _Bootstrap percolation on random geometric graphs_ , Probability in the Engineering and Informational Sciences 28 (2014), no. 02, 169–181.
  * [15] Karl Bringmann, Ralph Keusch, and Johannes Lengler, _Geometric inhomogeneous random graphs_ , arxiv (2015).
  * [16] by same author, _Average distance in a general class of scale-free graphs with underlying geometry_ , arxiv (2016).
  * [17] Elisabetta Candellero and Nikolaos Fountoulakis, _Bootstrap percolation and the geometry of complex networks_ , arXiv:1412.1301 (2014).
  * [18] Shai Carmi, Shlomo Havlin, Scott Kirkpatrick, Yuval Shavitt, and Eran Shir, _A model of internet topology using k-shell decomposition_ , Proceedings of the National Academy of Sciences 104 (2007), no. 27, 11150–11154.
  * [19] Damon Centola, _The spread of behavior in an online social network experiment_ , Science 329 (2010), no. 5996, 1194–1197.
  * [20] John Chalupa, Paul Leath, and Gary Reich, _Bootstrap percolation on a bethe lattice_ , Journal of Physics C: Solid State Physics 12 (1979), no. 1, L31–L35.
  * [21] Or Cohen, Anna Keselman, Elisha Moses, Rodríguez Martínez, Jordi Soriano, and Tsvi Tlusty, _Quorum percolation in living neural networks_ , EPL (Europhysics Letters) 89 (2010), no. 1, 18008.
  * [22] Colin Cooper, Alan Frieze, and Paweł Prałat, _Algorithms and models for the web graph: 9th international workshop, waw 2012, halifax, ns, canada, june 22-23, 2012. proceedings_ , ch. Some Typical Properties of the Spatial Preferred Attachment Model, pp. 29–40, Springer Berlin Heidelberg, Berlin, Heidelberg, 2012.
  * [23] Sergey Dorogovtsev, Alexander Goltsev, and José Mendes, _K-core organization of complex networks_ , Physical review letters 96 (2006), no. 4, 040601.
  * [24] Sergey Dorogovtsev and José Mendes, _Evolution of networks_ , Advances in Physics 51 (2002), no. 4, 1079–1187.
  * [25] Paul Dreyer and Fred Roberts, _Irreversible k-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion_ , Discrete Applied Mathematics 157 (2009), no. 7, 1615–1627.
  * [26] Hafsteinn Einarsson, Johannes Lengler, Konstantinos Panagiotou, Frank Mousset, and Angelika Steger, _Bootstrap percolation with inhibition_ , arXiv:1410.3291 (2014).
  * [27] Hafsteinn Einarsson, Johannes Lengler, and Angelika Steger, _A high-capacity model for one shot association learning in the brain_ , Frontiers in Computational Neuroscience 8 (2014), no. 140.
  * [28] Paola Flocchini, Elena Lodi, Fabrizio Luccio, Linda Pagli, and Nicola Santoro, _Dynamic monopolies in tori_ , Discrete applied mathematics 137 (2004), no. 2, 197–212.
  * [29] Jian Gao, Tao Zhou, and Yanqing Hu, _Bootstrap percolation on spatial networks_ , Scientific Reports 5 (2015), 14662.
  * [30] Allen Gersho and Debasis Mitra, _A simple growth model for the diffusion of a new communication service_ , Systems, Man and Cybernetics, IEEE Transactions on SMC-5 (1975), no. 2, 209–216.
  * [31] Mark Granovetter, _Threshold models of collective behavior_ , American Journal of Sociology 83 (1978), no. 6, 1420–1443.
  * [32] Mark S. Granovetter, _The strength of weak ties_ , American Journal of Sociology 78 (1973), no. 6, 1360–1380.
  * [33] Randi Griffin and Charles Nunn, _Community structure and the spread of infectious disease in primate social networks_ , Evolutionary Ecology 26 (2012), no. 4, 779–800.
  * [34] Wei Huang and Chunguang Li, _Epidemic spreading in scale-free networks with community structure_ , Journal of Statistical Mechanics: Theory and Experiment 2007 (2007), no. 01, P01014.
  * [35] Emmanuel Jacob and Peter Mörters, _Spatial preferential attachment networks: Power laws and clustering coefficients_ , The Annals of Applied Probability 25 (2015), no. 2, 632–662.
  * [36] Svante Janson, Tomasz Łuczak, Tatyana Turova, and Thomas Vallier, _Bootstrap percolation on the random graph $G$($n,p$)_, The Annals of Applied Probability 22 (2012), no. 5, 1989–2047.
  * [37] Jeannette Janssen and Abbas Mehrabian, _Algorithms and models for the web graph: 12th international workshop, waw 2015, eindhoven, the netherlands, december 10-11, 2015, proceedings_ , ch. Rumours Spread Slowly in a Small World Spatial Network, pp. 107–118, Springer International Publishing, Cham, 2015\.
  * [38] Amin Karbasi, Johannes Lengler, and Angelika Steger, _Automata, languages, and programming: 42nd international colloquium, icalp 2015, kyoto, japan, july 6-10, 2015, proceedings, part ii_ , ch. Normalization Phenomena in Asynchronous Networks, pp. 688–700, Springer Berlin Heidelberg, Berlin, Heidelberg, 2015.
  * [39] Scott Kirkpatrick, Winfried Wilcke, Robert Garner, and Harald Huels, _Percolation in dense storage arrays_ , Physica A: Statistical Mechanics and its Applications 314 (2002), no. 1, 220–229.
  * [40] Robert Kozma, _Neuropercolation_ , Scholarpedia 2 (2007), no. 8, 1360\.
  * [41] Renaud Lambiotte and Pietro Panzarasa, _Communities, knowledge creation, and information diffusion_ , Journal of Informetrics 3 (2009), no. 3, 180–190.
  * [42] Cristian Moukarzel and Thomas Sokolowski, _Long-range k-core percolation_ , Journal of Physics: Conference Series 246 (2010), no. 1, 012019.
  * [43] Javier Orlandi, Jordi Soriano, Enrique Alvarez-Lacalle, Sara Teller, and Jaume Casademunt, _Noise focusing and the emergence of coherent activity in neuronal cultures_ , Nature Physics 9 (2013), no. 9, 582–590.
  * [44] Fragkiskos Papadopoulos, Maksim Kitsak, Ángeles Serrano, Marián Boguñá, and Dmitri Krioukov, _Popularity versus similarity in growing networks_ , Nature 489 (2012), no. 7417, 537–540.
  * [45] Marlon Ramos, Jia Shao, Saulo Reis, Celia Anteneodo, José Andrade, Shlomo Havlin, and Hernán Makse, _How does public opinion become extreme?_ , Scientific reports 5 (2015), 10032.
  * [46] Christian Schmeltzer, Jordi Soriano, Igor Sokolov, and Sten Rüdiger, _Percolation of spatially constrained Erdős-Rényi networks with degree correlations_ , Physical Review E 89 (2014), no. 1, 012116\.
  * [47] Friedhelm Schwenker, Friedrich Sommer, and Günther Palm, _Iterative retrieval of sparsely coded associative memory patterns_ , Neural Networks 9 (1996), no. 3, 445–455.
  * [48] Munik Shrestha and Cristopher Moore, _Message-passing approach for threshold models of behavior in networks_ , Physical Review E 89 (2014), no. 2, 022805.
  * [49] Tsvi Tlusty and Jean-Pierre Eckmann, _Remarks on bootstrap percolation in metric networks_ , Journal of Physics A: Mathematical and Theoretical 42 (2009), no. 20, 205004.
  * [50] Tatyana Turova, _The emergence of connectivity in neuronal networks: from bootstrap percolation to auto-associative memory_ , Brain research 1434 (2012), 277–284.
  * [51] Christopher Warren, Leonard Sander, and Igor Sokolov, _Geography in a scale-free network model_ , Physical Review E 66 (2002), no. 5, 056105\.
  * [52] Duncan Watts, _A simple model of global cascades on random networks_ , Proceedings of the National Academy of Sciences 99 (2002), no. 9, 5766–5771.
  * [53] Xin-Jian Xu, Xun Zhang, and José Mendes, _Impacts of preference and geography on epidemic spreading_ , Physical Review E 76 (2007), no. 5, 056109.
  * [54] Zhi-Dan Zhao, Ying Liu, and Ming Tang, _Epidemic variability in hierarchical geographical networks with human activity patterns_ , Chaos: An Interdisciplinary Journal of Nonlinear Science 22 (2012), no. 2, 023150\.