Information Dissemination via Random Walks in d-Dimensional SpaceHenry Lam ∗ Zhenming Liu † Michael Mitzenmacher ‡ Xiaorui Sun § Yajun Wang ¶Abstract
We study a natural information dissemination problem
for multiple mobile agents in a bounded Euclidean space.
Agents are placed uniformly at random in the d-dimensional
space {−n, ..., n}d at time zero, and one of the agents holds a
piece of information to be disseminated. All the agents thenperform independent random walks over the space, and theinformation is transmitted from one agent to another if thetwo agents are suﬃciently close. We wish to bound the total
time before all agents receive the information (with highprobability). Our work extends Pettarin et al’s work [10],which solved the problem for d ≤ 2. We present tightbounds up to polylogarithmic factors for the case d = 3.
(While our results extend to higher dimensions, for spaceand readability considerations we provide only the cased = 3 here.) Our results show the behavior when d ≥ 3
is qualitatively diﬀerent from the case d ≤ 2. In particular,
as the ratio between the volume of the space and the numberof agents varies, we show an interesting phase transition
for three dimensions that does not occur in one or two
dimensions.

1 Introduction
We study the following information diﬀusion problem:
let a1 , a2 , ..., am be m agents initially starting at locations chosen uniformly at random in V d = {−n, −(n −1), . . . , n}d and performing independent random walks
over this space. One of the agents initially has a message, and the message is transmitted from one agent toanother when they are suﬃciently close. We are interested in the time needed to ﬂood the message, that is,
the time when all agents obtain the message. In othersettings, this problem has been described as a virus diffusion problem, where the message is replaced by a virusthat spreads according to proximity. We use informa∗ Department of Mathematics and Statistics, Boston University. Email: khlam@math.bu.edu.
† Harvard
School of Engineering and Applied Sciences.
Supported by NSF grant CCF-0915922.
Email:
zliu@eecs.harvard.edu.
‡ Harvard School of Engineering and Applied Sciences. Supported in part by NSF grants CCF-0915922 and IIS-0964473.
Email: michaelm@eecs.harvard.edu.
§ Columbia University. Email: xiaoruisun@cs.columbia.edu.
¶ Microsoft Research Asia. Email: yajunw@microsoft.com.

1612

tion diﬀusion and virus spreading interchangeably, depending on which is more useful in context. This isa natural model that has been extensively studied. For
example, Alves et al. and Kesten et al. coined the name“frog model” for this problem in the virus setting, andstudied the shape formed by the infected contour in thelimiting case [1, 2, 7]. In the ﬂooding time setting, earlyworks used a heuristic approximation based on simplifying assumptions to characterize the dynamics of the
spread of the message [3, 8, 13]. More recent works
provide fully rigorous treatments under this or similar
random walk models [4, 5, 10, 12, 9].
The most relevant recent works are those of Pettarin
et al. [10] and Peres et al. [9, 12]. The work of Pettarin
et al. examines the same model as ours, but theiranalysis is only for one- and two-dimensional grids. The
work of Sinclair and Stauﬀer [12] considers a similar
model they call mobile geometric graphs, and theirwork extends to higher dimensions. However, theirfocus and model both have strong diﬀerences from ours.
For example, they assume a Poisson point process ofconstant intensity, leading to a number of agents linear
in the size of the space. In contrast, our results allow
a sublinear number of agents, a scenario not directly
relevant to their model. Also, they focus on structural
aspects on the mobile graphs, such as percolation, while
we are primarily interested in the diﬀusion time. There
are additional smaller diﬀerences, but the main pointis that for our problem we require and introduce newtechniques and analysis.
Our paper presents matching lower bounds andupper bounds (up to polylogarithmic factors) for theﬂooding problems in d-dimensional space for an arbitrary constant d. For ease of exposition, in this paper we focus on the speciﬁc case where d = 3, which
provides the main ideas. Two- and three-dimensionalrandom walks have quite diﬀerent behaviors – speciﬁcally, two-dimensional random walks are recurrent while
three-dimensional random walks are transient – so it
is not surprising that previous results for two dimensions fail to generalize immediately to three-dimensional
space. Our technical contributions include new techniques and tools for tackling the ﬂooding problem bybuilding sharper approximations on the eﬀect of agent
interactions. The techniques developed in this paper

Copyright © SIAM.
Unauthorized reproduction of this article is prohibited.

are also robust enough that our results can be extended
to variations of the model, such as allowing probabilistic infection rules, replacing discrete time random walks
by continuous time Brownian motions, or allowing theagents to make jumps [5]. These extensions will be reported in future work.
Although the information diﬀusion problem in threeor more dimensions appears less practically relevant
than the two-dimensional case, we expect the model
will still prove valuable. For instance, particles ina high dimensional space may provide a latent-space
representation of the agents in a dynamic social network[6, 11], so understanding such information diﬀusion
processes may be helpful for designing appropriate
latent space models in the future. Also, the problem
is mathematically interesting in its own right.
1.1 Our models and results We follow the model
developed in [10]. Let V d = {−n, −(n − 1), ..., 0, ..., (n −1), n}d be a d-dimensional grid. Let A = {a1 , a2 , ..., am }be a set of moving agents on V d . At t = 0, the agents
spread over the space according to some distribution
D. Throughout this paper, we focus on the case where
D is uniform. Agents move in discrete time steps.
Every agent performs a symmetric random walk deﬁned
in the natural way. Speciﬁcally, at each time stepan agent not at a boundary moves to one of its 2dneighbors, each with probability 1/(2d). If an agent
is at a boundary, so there is no edge in one or more
directions, we treat each missing edge as a self-loop.
Let Ξ1 (t), ..., Ξm (t) ∈ {0, 1} each be a random variable,
where Ξi (t) represents whether the agent ai is infected
at time step t. We assume Ξ1 (0) = 1 and Ξi (0) = 0 for
all i ̸= 1. The value Ξi (t) will change from 0 to 1 if attime t it is within distance 1 to another infected agent
aj . (We use distance 1 instead of distance 0 to avoid
parity issues.) Once a value Ξj (t) becomes 1, it stays 1.
Definition 1.1. (Information diﬀusion problem). Let
A1 , A2 , . . . , Am ∈ V d be the initial positions of theagents a1 , . . . , am and let St1 (A1 ), St2 (A2 ), . . . , Stm (Am )be m independent random walks starting at A1 , . . . , Am
respectively, so that Sti (P ) is the position of agent ai attime t given that at t = 0 its position was P ∈ V d . The
infectious state of each agent at time step t is a binary
random variable Ξi (t) such that• Ξ1 (0) = 1, Ξi (0) = 0 for all other i, and• for all t > 0, Ξi (t) = 1 if and only if(Ξi (t −(1) = 1) or)∃j : Ξj (t − 1) = 1 ∧ Sti (Ai ) − Stj (Aj ) 1 ≤ 1 .

The following results for the diﬀusion time for oneand two-dimensional spaces are proved in [10].
Theorem 1.1. Consider the information diﬀusion
problem for d = 1, 2 dimensions, and assume the agentsare initially uniformly distributed over V d . Then, withhigh probability,(1.1)

T = Θ̃(n2 · m−1/d ).

It is natural to ask whether Equation 1.1 also holds
for d ≥ 3. Our results show this is not the case.
Theorem 1.2. (Diﬀusion time for d ≥ 3) Consider the
information diﬀusion problem for d ≥ 3 with initially
uniformly distributed agents over V d . Then there exists
a constant c such that
cnd−2 log2 n < m < nd :T = Θ̃(nd/2+1 · m−1/2 ) with high probability;m < cnd−2 log−2 n :T ≤ Θ̃(nd /m) with high prob. and T ≥ Θ̃(nd /m) a.s.

if
if
(1.2)

Notice that Theorems 1.2 and 1.1 yield the same
result for d = 2, as well as when d = 1 and m =Θ(n). Here when we say with high probability, wemean the statement holds with probability 1 − n−γ forany constant γ and suitably large n. When we sayalmost surely, we mean with probability 1 − o(1). Whenm ≥ nd , the result is implicit in [7] and the diﬀusion
time in this case is Θ̃(n). Finally, there are sometechnical challenges regarding the case cnd−2 log−2 n ≤m ≤ cnd−2 log2 n that we expect to address in futurework.
An interesting point of our result is that when
the number of agents m is greater than nd−2 , theﬁnishing time is less than the mixing time of eachindividual random walk, and therefore the analysis
requires techniques that do not directly utilize themixing time. The rest of this extended abstract focuseson the lower and upper bounds for this interesting case,and, as previously mentioned, only for d = 3.
Theorem 1.2 can also be expressed in terms of thedensity of agents. Let λ = m/nd be the density.
We can√express the diﬀusion time as T = Θ̃(n/ λ) w.h.p. forcn−2 log2 n < λ < 1, whereas for λ < cn−2 log−2 n wehave T ≤ Θ̃(1/λ) w.h.p. and T ≥ Θ̃(1/λ) almost surely.
We remark that all theorems/propositions/lemmas
in this paper are assumed to hold for suﬃciently largen, but for conciseness we may not restate this conditionin every instance.
2

Lower boundThe ﬁnishing time of the diﬀusion process, or the Let us ﬁrst state our lower bound result more precisely
diﬀusion time, is T = inf{t ≥ 0 : |{Ξi (t) = 1}| = m}.
as follows.

1613

Copyright © SIAM.
Unauthorized reproduction of this article is prohibited.

Theorem 2.1. Let a1 , ..., am be placed uniformly at
The results in [2, 7] are not directly applicable in our
2
3
3
random
on
V
such
that
1600n
log
n
≤
m
≤
n
.
Let
settingbecause the growth rate they obtain is linear in√ℓ2 =n3 /m. For suﬃciently large n, the diﬀusion time, as a result of their assumption of constant agent
time T satisﬁes the following inequality
density in an inﬁnite space, in contrast to our use ofa size parameter n that scales with the agent density.
1−29
It is fairly simple to see that blindly applying a linear
Pr[T ≤ℓ2 n logn] ≤ exp (− log n log log n) .
81
growth rate to our setting of o(1) density is too crude.
On the other hand, analyzing how agent density aﬀects
We use a local analysis to prove our lower bound.
the growth rate is a potentially feasible approach but
The key idea is that under uniform distribution ofcertainly not straightforward.
agents, the extent any particular infected agent can
Our approach more closely follows [10]. The main
spread the virus within a small time increment is conlimitation of [10], when applied to higher dimensions, isﬁned to a small neighborhood with high probability. By
how to control the interaction among islands. If islands
gluing together these local estimates, we can approxiinteract too often, because they are too close together,mate the total diﬀusion time. To explain our local analthe argument, which is based on a low probability ofysis, assume we start with an arbitrary infected agent,interaction, breaks down. However, if one parametrizes
say a1 . Let us also assume, for simplicity, that all theislands to prevent such interaction, then the boundother uniformly distributed agents are uninfected. Conthat can be obtained is too weak. For d > 2 thissider the scenario within a small time increment, say ∆t.
constraint ultimately limits the analysis for the caseDuring this time increment the agent a1 infects whoof o(1) density. We attempt to remedy the problem
ever it meets in the small neighborhood that contains
by using islands as an intermediate step to obtainits extent of movement. The newly infected agents thenlocal estimates of the inﬂuence of each initially infected
continue to move and infect others. The size of the ﬁnal
agent over small periods of time. This analysis involves
region that contains all the infected agents at ∆t thenlooking at a branching process representing the spread
depends on the rate of transmission and the extent ofof the infection, signiﬁcantly extending the approach of
movement of all of the infected agents. In particular, if[10].
∆t is small enough, the expected number of transmissions performed by a1 is less than one; even if it infects
2.1 Local diﬀusion problem This subsection foanother agent, the number of infections it causes withincuses on the local analysis as discussed above. In Secthe same ∆t is also less than one, and so on. The nettion 2.2, we will proceed to discuss how to utilize thiseﬀect is an eventual dying-out of this “branching proanalysis to get the lower bound in Theorem 2.1. The
cess” (which we later model by what we call a diﬀusion
two main diﬃculties in our analysis are: 1) probabilistree), which localizes the positions of all infected agents
tic estimates for the meeting time/position of multiple
at time ∆t to a small neighborhood around the initial
random walks are typically only useful asymptotically;
position of a1 .
2) walks near the boundary introduce further analytical
Before laying out our analysis, let us brieﬂy review
complications. To begin with, the following deﬁnition
the main methodologies in obtaining lower bound reserves to handle the second issue:
sults in related work, and point out their relation to
our analysis and diﬃculties in directly applying them Definition 2.1. (Interior region) The interior reto higher dimensions. Two potential existing methods gion V(r) parameterized by r is the set of lattice points
arise in [2, 7] and [10]. The former analyzes the growth in V 3 that have at least L -distance r to the boundary.
∞rate of the size of the total infected region; an upperbound on this growth rate translates to a lower boundFor any point P ∈ V 3 , deﬁne B(P, x) = {Q ∈ V 3 :for the diﬀusion time. The latter work, focusing on ∥Q − P ∥ ≤ x} as the x-ball of neighborhood of P∞
d = 1, 2, uses an “island diﬀusion rule”, which essen- under the L -norm. We have the following result:∞tially speeds up infection by allowing infections to occur
immediately on connected components in an underlying Proposition 2.1. Consider a diﬀusion following Defgraph where edges are based on the distance between inition 1.1. Let S0 be the initial position of the only inagents. This approach avoids handling the issue of the fected agent a1 at time 0, and W be an arbitrary subset√
meeting time of random walks when they are very close, of lattice points in V(20ℓ2 log n), where ℓ2 = n3 /m.
a regime where standard asymptotic results may not ap- Denote ∆t = ℓ2 log−28 n. Deﬁne the binary random
2ply, while still providing a way to bound the diﬀusion variable b(W) as follows:time by arguing about the low probability of interaction
among diﬀerent “islands”.
• If S0 ∈ W: b(W) is set as 1 if and only if all the1614

Copyright © SIAM.
Unauthorized reproduction of this article is prohibited.

infected agents at time ∆t can be covered by the ball in ∆t time units. At this time point, the newly infected
B(S0 , 9ℓ2 log n).
agents inside the ball continue to spread the virus toneighborhoods of size at most 9ℓ2 log n, again with high• If S0 ∈/ W: b(W) = 1.
probability. This gives an enlarged area of infection withradius at most 18ℓ2 log n. Continuing in this way, theWe have Pr[b(W) = 1] ≥ 1 − exp(−5 log n log log n).
lower bound in Theorem 1.2 is then the time for the3
The proposition yields that with high probability, infection to spread over V . This observation will be
all the infected agents lie within a neighborhood of made rigorous in the next subsection.
The rest of this subsection is devoted to the argudistance Õ(ℓ2 ) at time Õ(ℓ22 ). The variable ℓ2 is chosen
ments
of Proposition 2.1. It consists of two main steps.
such that the expected number of infections spanned by
2
First,
weneed to estimate the expected number of inan initially infected agent a1 within Õ(ℓ2 ) units of time
fectionsdone
by a single initially infected agent within
and a neighborhood of Õ(ℓ2 ) distance is O(1). This can3
distance
9ℓ
log
n and time increment ∆t. Second, we
2
be seen by solving m(ℓ2 /n) × (1/ℓ2 ) = Õ(1), where3
iteratetoconsidereach newly infected agent. The analm(ℓ2 /n) is the expected number of agents in a cube ofysis
requirestheconditionthat the global conﬁguration
size ℓ2 × ℓ2 × ℓ2 , and Õ(1/ℓ2 ) is the meeting probability
2behaves“normally”,
ascenariothat occurs with suitwithin time Õ(ℓ2 ) between any pair of random walks
ably
high
probability,
as
we
show.
We call this condiwith initial distance ℓ2 . This choice of ℓ2 appears to
tion
“good
behavior”,
whichis
introduced
through thebe the right threshold for our analysis. Indeed, a larger
severaldeﬁnitions
below:
scale than ℓ2 would induce a large number of infections
made by a1 , and also subsequent infections made by
newly infected agents, with an exploding aﬀected region Definition 2.2. (Island, [10]) Let A = {a1 , ..., am }3
as an end result. On the other hand, a smaller scale be the set of agents in V . For any positive integer
than ℓ2 would degrade our lower bound. This is because γ > 0, let Gt (γ) be the graph with vertex set A suchthe diﬀusion time is approximately of order n/ℓ2 , the that there is an edge between two vertices if and only if
number of spatial steps to cover V 3 , times ℓ22 , the time the corresponding agents are within distance γ (undertaken for each step, equaling nℓ2 . Hence a decrease in L1 -norm) at time t. The island with parameter γ of anagent ai ∈ A at time step t, denoted by Isdt (ai , γ) is theℓ2 weakens the bound1 .
Secondly, we introduce W in Proposition 2.1 to connected component of Gt (γ) containing ai .
avoid the case when S0 is close to the boundary. As wehave mentioned, such boundary conditions often complicate random walk analysis. Although the impact of
the boundary’s presence has been addressed in previous
work (e.g., [5, 10]), existing results are not fully satisfactory. For example, when two simple random walks
S 1 and S 2 start near the boundary, only a lower boundfor the probability that two walks meet within a speciﬁc
number of time steps is available ([10]); we do not knowof an upper bound counterpart. We arrange our proof
so that it is suﬃcient to analyze the diﬀusion pattern ofa virus when it starts far from the boundary. Finally,
we note that no eﬀort has been made to optimize theexponent 28 in ∆t’s deﬁnition.
We brieﬂy explain how our global lower bound canbe readily obtained from Proposition 2.1, which is astrong characterization of the local growth rate of infection region size. Imagine the following evolution. Starting with a single infected agent, with high probability
the infection spreads to a ball of radius at most 9ℓ2 log n
1 In

the case of general d-dimensional space, ℓ2 is√chosensuch that m(ℓ2 /n)d × (1/ℓd−2) = Õ(1), giving ℓ2 =nd /m.
2
Throughout the paper such d-dimensional analog can be carriedout in similar fashion, but for ease of exposition we shall not bringup these generalizations and will focus on the 3-dimensional case.

1615

Definition 2.3. (Good behavior) Let
ℓ1
=
−3
−1/3
nm
.
For
1
≤
i
≤
(ℓ
/ℓ
)
log
n,
deﬁne
B
(P
)
=
2 1
i
(
)
B P, iℓ1 log−1 n and let ∂Bi (P ) = Bi (P ) − Bi−1 (P ).
5n)|∂Bi (P )|m
For any P ∈ V 3 , deﬁne mi (P ) = (log (2n+1). Let
3
us deﬁne the following binary random variables:• Good density. Let {Dt : t ≥ 0} be a sequence of0, 1 random variables such that Dt = 1 if and only
if for all P ∈ V 3 and all i ≤ (ℓ2 /ℓ1 ) log−3 n, thenumber of agents in ∂Bi (P ) is at most mi (P ), forall time steps up to t. We say the diﬀusion process
has the good density property at time t if Dt = 1.
• Small islands. Let {Et : t ≥ 0} be a sequence of0, 1 random variables such that Et = 1 if and only
if |Isds (aj , ℓ1 log−1 n)| ≤ 3 log n for all aj ∈ A and0 ≤ s ≤ t. We say that the diﬀusion process has
the small islands property at time t if Et = 1.
• Short travel distance. Let {Lt : t ≥ 0} be asequence of 0, 1 random variables such that Lt = 1
if and only if for all i ∈ [m] and all t1 < t2 ≤ twith t2 − t1 ≤ ℓ22 log−12 n, we have ∥Sti1 − Sti2 ∥1 ≤3ℓ2 log−4 n. We say the process has the short travel
distance property at time t if Lt = 1.

Copyright © SIAM.
Unauthorized reproduction of this article is prohibited.

Finally, let Gt = Dt × Et × Lt , and say the diﬀusion process is diﬀerent from the diﬀusion models introduced
process behaves well at time t if Gt = 1. We also focus in [10, 12, 9]. In our formulation, an island is infected
on t ≤ n2.5 and deﬁne the random variable G = Gn2.5 . only if meeting occurs between one uninfected andone previously infected agent. In [10, 12, 9] (using
The value n2.5 in the deﬁnition is chosen such that our notations), an island is infected once it contains a
it lies well beyond our lower bound for the case m < n3 , previously infected agent. As a result, infections occur
but is small enough for our forthcoming union bound. less frequently in our model than the models in [10,By using properties of random walks and techniques 12, 9]. This diﬀerence is the key to getting a tight lower
derived in [10], we havebound for dimensions higher than 2. More precisely, ourinfection rule allows us to build a terminating branching
Lemma 2.1. Let A = {a1 , ..., am } be agents that are process, or what we call a “diﬀusion tree” in the
distributed uniformly in V 3 at t = 0. For suﬃciently following deﬁnition, whose generations are deﬁned via
large n, we have Pr[G = 1] ≥ 1−exp(−6 log n log log n). the infection paths from the source. The termination ofthis branching process constrains the region of infection
With this global “good behavior”, we have theto a small neighborhood around the source with afollowing estimate:probability of larger order than obtained in [10]. This
Lemma 2.2. Let A = {a , . . . , a } be agents that in turn leads to a tighter global lower bound.
1m

are distributed in V 3 in such a way that D0 =1. Let S 1 , S 2 , . . . , S m be their corresponding random
walks. Consider an arbitrary agent aj with S0j ∈V(2ℓ2 log−4 n). Let {ai1 , . . . , aik } be the set of agents
outside B1 (S0j ) at time 0. Deﬁne Xj,ℓ as the indicator random variable that represents whether theagentsaj and aiℓ meet within time [0, ∆t].
[
] We have∑j−4En) < log−3 n.
ℓ≤k Xj,ℓ D0 = 1, S0 ∈ V(2ℓ2 log

Lemma 2.2 says that if the initial distribution of
agents possesses good behavior, then the expected number of direct infections on far-away agents is small. For
agents close to the initially infected agents, we instead
utilize the concept of islands, and formally introduce a
new diﬀusion process with a modiﬁed “island diﬀusion”
rule. It is easy to see that the new diﬀusion process canbe coupled with the original diﬀusion process (evolving
with Deﬁnition 1.1) by using the same random walks inthe same probability space.

Definition 2.5. (Diffusion tree) Let
W⊆
V(2ℓ2 log n) be a subset of lattice points. Consider adiﬀusion, following the island diﬀusion rule, that starts
with an initially infected island Isd0 (a1 , ℓ1 log−1 n).
Recall that S01 denotes a1 ’s position at t = 0. The
diﬀusion tree Tr with respect to W has the following
components:/ W, Tr = ∅.
1. If S01 ∈2. If S01 ∈ W,
• The root of Tr is a dummy node r.
• The children of r are all the agents in
Isd0 (a1 , ℓ1 log−1 n).
• aℓ′ is a child of aℓ (aℓ′ ∈ child(aℓ )) if aℓ′ isinfected by aℓ before time ∆t.
• aℓ′ is a direct child of aℓ (aℓ′ ∈ dchild(aℓ )) ifaℓ′ ∈ child(aℓ ) and it is directly infected by aℓ .

Definition 2.4. (Diﬀusion Process with Island Diﬀu- For technical reasons, if aℓ′ is not in Tr, we letsion Rule) Consider a diﬀusion process in which m child(aℓ ) = ∅ and dchild(aℓ ) = ∅.
agents are performing random walks on V 3 . An uninWe refer to the root of the tree as the 0th level of thefected agent aj becomes infected at time t if one of thetree
and count levels in the standard way. The height
following conditions holds:of the tree is the number of levels in the tree. Note
1. it meets a previously infected agent at time t. For that a diﬀusion tree deﬁned in this way can readily beconvenience, we say aj is directly infected if it is interpreted as a branching process (See, e.g., Chapter
infected in this way.
0 in [14]), in which the jth generation of the process
corresponds with the jth level nodes in Tr.
−1
2. it is inside Isdt (ai , ℓ1 log n) where ai is directly
Next we incorporate the good behavior variable Gt
infected at time t.
with the diﬀusion tree. The motivation is that, roughly
speaking, consistently good behavior guarantees a small
We shall call the coupled process in Deﬁnition 2.4 number of infections, or creation of children, at eachthe diﬀusion process with island diﬀusion rule. This level. This can be seen through Lemma 2.2.

1616

Copyright © SIAM.
Unauthorized reproduction of this article is prohibited.

We note that Proposition 2.1 deals with the casewhen there is only one initially infected agent. As discussed brieﬂy in the discussion following the proposition, we want to iterate this estimate so that at every
time increment ∆t, the infected region is constrained
within a certain radius from the initial positions of all
the agents that are already infected at the start of the increment. Our argument is aided by noting which agents
infect other agents. To ease the notation for this purNote that the deﬁnition of the stopped diﬀusion pose, we introduce an artiﬁcial concept of virus type,
tree involves global behavior of the whole diﬀusion denoted by νi,t . We say an agent gets a virus of typeprocess due to the introduction of Gt . On the other νi,t if the meeting events of this agent can be traced
hand, Tr = Tr′ with overwhelming probability, so we upstream to the agent ai , where ai is already infected
can translate the properties of Tr′ back to Tr easily. at time t. In other words, assume that ai is infected at
The main property of the stopped diﬀusion tree is the time t, and imagine that we remove the viruses in all
following:
infected agents except ai but we keep the same dynamics of all the random walks. We say a particular agent
Lemma 2.3. Consider a diﬀusion process with the is- gets νi,t if it eventually gets infected under this imagiland diﬀusion rule. Let aℓ be an arbitrary agent with nary scenario. Note that under this artiﬁcial framework
infection time T (ℓ). We haveof virus types it is obvious that an agent can get many
diﬀerent types of virus, in terms of both i and t.
[]
E |dchild′ (aℓ )| FT (ℓ) , STℓ (ℓ) ∈ V(2ℓ2 log−4 n) ≤ log−3 n,
In parallel to Proposition 2.1, we introduce thefamilyof binary random variables bi,t to represent(2.3)′
whethera virus of type νi,t can be constrained in a ballwhere dchild (·) is deﬁned for a stopped diﬀusion treewith radius 9ℓ2 log n:with respect to an arbitrary set W ⊆ V(20ℓ2 log n).
Definition 2.6. (Stopped diffusion tree)
Consider a diﬀusion process with island diﬀusion
rule, and let T (ℓ) be the time that aℓ becomes infectedin the process. The stopped diﬀusion tree Tr′ (withrespect to ai and W) is a subtree of Tr induced by theset of vertices {aℓ : aℓ ∈ Tr ∧ GT (ℓ) = 1}. We writeaℓ ∈ child′ (aℓ′ ) if aℓ ∈ child(aℓ′ ) and aℓ ∈ Tr′ . Also,aℓ ∈ dchild′ (aℓ′ ) if aℓ ∈ dchild(aℓ′ ) and aℓ ∈ Tr′ .

We regard the conditional expectation in Equation 2.3 as a random variable, and Ft is the ﬁltration up
to time t. The interpretation is that the expected number of aℓ ’s direct children is less than log−3 n, regardlessof the global conﬁguration at the infection time of aℓ ,as long as it lies in V(2ℓ2 log−4 n) at that time.
Recursive utilization of Lemma 2.3 on successive
tree levels leads to the following lemma:

Definition 2.7. (bi,t and virus of type νi,t ) Let
B = B(P, n4 ) where P = (n/2, n/2, n/2). Let a1 , ..., ambe agents that are uniformly distributed on V 3 at t = 0
and diﬀuse according to Deﬁnition 1.1. Let t be an
arbitrary time step and i ∈ [m]. At time t, a virus oftype νi,t emerges on agent ai and diﬀuses. Deﬁne thebinary random variable bi,t as follows:• If Sti ∈ B: bi,t is set as 1 if and only if all the agents
infected by the virus of type νi,t at time t + ∆t canbe covered by the ball B(Sti , 9ℓ2 log n).

Lemma 2.4. Consider a diﬀusion process with the island diﬀusion rule starting with an infected island
Isd0 (a1 , ℓ1 log−1 n). For the stopped diﬀusion tree Tr′• If Sti ∈/ B: bi,t = 1.
′
with respect to any W ⊆ V(20ℓ2 log n), let Height(Tr )Let us start with the observation that bi,t = 1 forbe its height. Then we have Pr[Height(Tr′ ) > 2 log n] ≤alliand t with high probability. This can be seen easilyexp(−3 log n log log n).
by applying Proposition 2.1 to every agent and taking
This lemma is the key to proving Proposition 2.1. a union bound across all i and t.
The bound on the height of the diﬀusion tree limits
the family of random varithe number of infected generations from the initially in- Corollary 2.1. Consider
2.5
ables
{b
:
i
∈
[m],
t
≤
n
}
deﬁned above. We havei,tfected a1 . Together with short travel distance property
in Deﬁnition 2.3, it eﬀectively constrains the positions∧of all infected agents into a small ball around a1 , which Pr (bi,t = 1) ≥ 1 − exp(−4 log n log log n).
leads to Proposition 2.1.
i∈[m],t≤n2.5
2.2 From local to global process This subsection
We also need the following lemma on the denwill be devoted to proving Theorem 2.1 via Proposi- sities of agents in a linearly sized ball centered attion 2.1, or in other words, to turn our local probabilis- (n/2, n/2, n/2), which can be shown using a standard
tic bound into a global result on the diﬀusion time.
Chernoﬀ bound and taking a union bound across all t.

1617

Copyright © SIAM.
Unauthorized reproduction of this article is prohibited.

Lemma 2.5. Let B = B(P, n/8), where P =On the other hand, the physical dimensions of B
(n/2, n/2, n/2). Let Bt be the indicator variable that and B give that
there is at least one agent in B at time t. Let B =∏′′′n∥STi ′ − STi ′′ ∥∞ ≥ − 1t≤n2.5 Bt , the indicator variable that there is at least8
one agent in B at all times in [0, n2.5 ]. We have
which gives a contradiction.
Pr[B = 0] ≤ exp(− log2 n)
3 Upper bound
We next present our major lemma for this subsec- We now focus on an upper bound for the diﬀusion time.
Our main result is the following:tion.

for suﬃciently large n.

Lemma 2.6. Let a1 , ..., am be placed uniformly at random on V 3 such that m ≥ 1600n log2 n. Let ℓ2 =√n3 /m. Let {bi,t : i ∈ [m], t ≤ n2.5 } and B be
the random variables described above. If bi,t = 1 for
all i, t and B = 1, then the diﬀusion time is at least1
Tc = 81ℓ2 n log−29 n.

Theorem 3.1. Let a1 , . . . , am be placed uniformly
at random on V 3 , where n ≤ m ≤ n3 . Let ℓ̂2 =√n3 /m log n. When n is suﬃciently large, the diﬀusion
time T satisﬁes
1
Pr[T ≥ 128nℓ̂2 log47 n] ≤ exp(− log2 n).
2

Notice that by Corollary 2.1 and Lemma 2.5,
Note
[∧
]
√ that this theorem shows that an upper boundPr i≤m,t≤n2.5 (bi,t = 1) ≥ 1 − exp(−4 log n log log n). of Õ(n n3 /m) holds for the diﬀusion time with highprobability. Hence the upper and lower bounds “match”
Pr[B = 1] ≥ 1 − exp(− log2 n).
up to logarithmic factors. We remark that the constant
Together with Lemma 2.6, Theorem 2.1 then follows.
47 in the exponent has not been optimized.
The main goal of this section is to prove this theoProof. Without loss of generality, we assume the x, y,rem.
Our proof strategy relies on calculating the growthand z coordinates of S01 are all negative. We can always
rateof
the total infected agents evolving over time; suchrotate the space V 3 at t = 0 correspondingly to ensure
growth rate turns out to be best characterized as thethis assumption holds.
increase/decrease in infected/uninfected agents relative
We shall prove by contradiction. Consider two balls
to the size of the corresponding population. More preB and B deﬁned above. Assume the diﬀusion timecisely, we show that for a well-chosen time increment,
is less than Tc . First, because B = 1, a necessary
either the number of infected agents doubles or thecondition for the diﬀusion to complete is that an infected
number of uninfected agents reduces by half with highagent visits the smaller ball B at a time T ′ ≤ Tc (sinceprobability. The choice of time increment is complex,
otherwise the agents in B would be uninfected all thedepending on the analysis of the local interactions intime, including at Tc ). We call this agent ai′ . Next,
small cubes and the global geometric arrangements offor the infection to get into B, it must happen thatthese cubes with respect to the distribution of infected
there is an infected agent that enters B from outside,agents.
whose infection trajectory eventually reaches ai′ . We
As with the lower bound proof, our technique fordenote T ′′ to be the last time that this happens, and theproving
Theorem 3.1 is diﬀerent from existing methods.
responsible agent to be ai′′ . We focus on the trajectory
Roughly,
existing methods can be decomposed into twoof infection that goes from ai′′ to ai′ that lies completely
steps
(see
for example [10]): 1) In the ﬁrst step, consider
inside B (which exists since T ′′ is the last time of entry).
a small ball of length r that contains the initiallyNote that we consider at most ⌈Tc /∆t⌉ time increments
infected agent. One can see that for d = 2, when theof ∆t. Now, since bi,t = 1 for all i and t, by repeated
number of agents in the ball is Θ̃(m(r/n)2 ), within timeuse of triangle inequality, we getincrement r2 the number of infections to agents initially
⌈ ⌉
′
′′
Tc
in this ball is Ω̃(1) w.h.p.. 2) The second step is to∥STi ′ − STi ′′ ∥∞ ≤ 9ℓ2 log nprove that for any ball that has Ω̃(1) infected agents∆t() at time t, its surrounding adjacent balls will also have−29
(1/81)ℓ2 n log
n≤ 9ℓ2 log n+1Ω̃(1) infected agents by time t + r2 . From these two−28
2ℓ2 logn
steps, one can recursively estimate the time to spreadninfection across the whole space V 2 to be n/r × r2 = nr≤
+ 9ℓ2 log n9w.h.p.. In other words, at time nr all the balls in V 2
n<−1
will have Ω̃(1) infected agents. Moreover, every agent in
8

1618

Copyright © SIAM.
Unauthorized reproduction of this article is prohibited.

V 2 is infected in the same order of time units, becauseΩ̃(1) is also the total number of agents in any ball undergood density condition. Finally,√ it is then clear that agood choice of r is then n/ m, which would give theoptimal upper bound.
The critical diﬀerence in the analysis for d > 2 lies
primarily in the magnitude of the meeting probabilityof random walks. In the case of d = 2, the meetingprobability of two random walks at distance r withintime r2 is Θ̃(1), whereas for d > 2 the meetingprobability is Θ(1/rd−2 ). For d = 2, this means that
it is easy, i.e. w.h.p., for infection to transmit from aball with Ω̃(1) infected agents to an adjacent uninfectedball, so that the latter also has Ω̃(1) infected agents after
a time increment of r2 . In the case d > 2, however,Ω(rd−2 ) infected agents must be present in a ball totransmit virus eﬀectively to its adjacent uninfected ballwithin r2 time. Consequently, arguing for transmission
across adjacent balls becomes problematic (more details
are in the full paper). In light of this, we take analternate approach to analyze both the local interactions
and the global distribution of infected agents. Insteadof focusing on transmission from one infected ball toanother, we calculate the spreading rate across thewhole space. This turns out to be fruitful in obtaining
a tight upper bound.
We brieﬂy describe the forthcoming analysis. As
with the lower bound, we start with local analysis. We
partition the space V 3 into disjoint subcubes each ofsize ℓ̂2 × ℓ̂2 × ℓ̂2 . Here ℓ̂2 is just a logarithmic factor
larger than ℓ2 , the size of subcubes used for the lower
bound, so that with overwhelming probability there areat least ℓ̂2 agents in a subcube. We show that, withinevery subcube, over a time increment of length Θ(ℓ̂22 )the number of infections is roughly a Ω̃(1)-fraction of
the minimum of the number of infected and uninfectedagents. Hence, at least locally, we have the desired
behavior described above.
We then leverage the local analysis to obtain the
global result. However, this is not straightforward.
For example, consider the beginning when the numberof infected agents is small. If infected agents are
distributed uniformly throughout the whole space, itwould be easy to show that new infections would
roughly grow in proportion to the number of infectedagents. However, if infected agents are concentrated
into a small number of subcubes, we have to show that
there are enough neighboring subcubes on the boundaryof these infected subcubes that these subcubes become
infected suitably rapidly, so that after the appropriate
time increment the number of infected agents doubles.
Similar arguments arise for the case when infectedagents are dominant, with the end result being a halving

1619

of the uninfected population.
We now make the above discussion rigorous. First,
let b = (2n + 1)/ℓ̂2 , so there are in total b3 subcubes.
As in the previous section, we divide the time into smallintervals. We reuse the symbol ∆t to represent thelength of each interval but here we set ∆t = 16ℓ̂22 . Our
local bound is built within each subcube (and pair ofneighboring subcubes) in the time increment ∆t:Lemma 3.1. Let W ⊂ V 3 be a region that can be coveredby a ball of radius 2ℓ̂2 under the L∞ -norm. Let Af
and Au be subsets of infected and uninfected agents in
W at time t such that |Af | = m1 , |Au | = m2 , andmax{m1 , m2 } = ℓ̂2 / log2 n. Given any initial placementof the agents of Af and Au , let M (t) be the numberof agents in[ Au that become infected] at time t + ∆t.
1 ,m2 }We have Pr M (t) ≥ τ0 min{mFt ≥ τ0 log−6 n for
log4 nsome constant τ0 , where Ft denotes the information of
the whole diﬀusion process up to time t.
The high level idea in proving Lemma 3.1 is tocount the total number of times the infected agents meetthe uninfected ones between time t and t + ∆t. The
probability two agents in W can meet each other withintime ∆t is approximately Ω̃(1/ℓ̂2 ) (this fact is provedin the full paper). The expected number of meetings
is thus Ω̃(1/ℓ̂2 ) × m1 m2 = Ω̃(min{m1 , m2 }). The
total number of newly infected agents is the number of
meetings modulo possible overcounts on each originallyuninfected agent. Hence we show that the number of
meetings is Õ(1) for each uninfected agent to conclude
that Ω̃(min{m1 , m2 }) more agents become infected attime t + ∆t.
The next step is to characterize the growth rate
at a larger scale. This requires more notation. We
denote the set of b3 subcubes of size ℓ̂2 × ℓ̂2 × ℓ̂2 as
C = {hi,j,k : i, j, k ∈ [b]}. For an arbitrary subcube
hi,j,k , we deﬁne its neighbors as N (hi,j,k ) = {hi′ ,j ′ ,k′ :|i − i′ | + |j − j ′ | + |k − k ′ | = 1}. In other words, hi′ ,j ′ ,k′is a neighbor of hi,j,k if and only if both subcubes sharea facet. ∪Let H be an arbitrary subset of C. We write
N (H) = h∈H N (h).
Definition 3.1. (Exterior and interior surface)
Let H be a subset of C. The exterior surface of H is
∂H = N (H) − H. Let H be the complement of H.
˙ = N (H) − H, i.e., theThe interior surface of H is ∂Hexterior surface of the complement of H.
At time step t = i∆t, let Gt be the set of all
subcubes that contain more than ℓ̂2 /2 infected agentsand let gt = |Gt |; let Bt = Gt be the rest of the subcubesand let bt = |Bt |. We call a subcube in Gt an infected

Copyright © SIAM.
Unauthorized reproduction of this article is prohibited.

(good ) subcube and a subcube in Bt an uninfected (bad )subcube.
We classify the agents in the process according to
the subcubes they reside in. To facilitate our analysis,
we adopt the notational system A·t and A·,·t to represent
the total number of agents that belong to the typespeciﬁed in the superscript. Speciﬁcally, let Aft be theset of infected agents at time t; decompose the set Aft
f,G∪ Af,Bis the set of infected
as Aft = Af,Gtt , where At
agents residing in the subcubes in Gt and Atf,B the
set of infected agents in Bt . Similarly, let Aut be theset of all uninfected agents; decompose the set Aut asu,GAut = Au,G
∪ Au,Bis the set of uninfectedtt , where At
agents residing in the subcubes in Gt and Au,B
the set oft
uninfected agents in Bt . Furthermore, we denote ∆AGtand ∆ABt as the set of agents in Gt and Bt respectively
that are infected between t and t + ∆t. Hence the total
increase in infected agents, or equivalently the total
decrease in uninfected agents, between t and t + ∆t is]G begiven by ∆A = ∆AG ∪ ∆AB . Lastly, we let ∆Aand
Pr |∆ABt | ≥ |∂Gt | ·τ0 ℓ̂2
Ft , Dt = 1 ≥ τ0 log−6 n.
4 log13 nCorollary 3.2. We have[Pr |∆AGt | ≥

]
τ02
u,G
|A
|
F
,
D
=
1
≥ τ0 log−6 nttt
4 log38 n

and[Pr |∆AB
t | ≥

]
τ02
f,B
|A
|
F
,
D
=
1
≥ τ0 log−6 n.
ttt
4 log38 n

The proofs of these two corollaries both rely on using coupled diﬀusion processes that have slower diﬀusion rates. These processes only allow infection locallyi.e. within each “pair” of subcubes on the surface of Gt
in the case of Corollary 3.1 and within each subcube in
Corollary 3.2, and hence can be tackled by Lemma 3.1.
The surface ∂Gt in Corollary 3.1 appears naturally fromtttta matching argument between neighboring infected andthe set of agents in Gt ∪ ∂Gt that are infected between t
uninfected subcubes. Roughly speaking, the bounds
and t + ∆t.
in Corollary 3.1 are tighter and hence more useful for
Similar to the lower bound analysis, here we also
the cases where infected/uninfected agents are dense in
introduce good density conditions that can be easily
the infected/uninfected subcubes, while those in Corolveriﬁed to hold with high probability, and reuse thelary 3.2 are for cases where the agent types are more
symbols Dt and D with slightly diﬀerent meanings from
uniformly distributed.
the last section:
We now move to the global diﬀusion upper bound.
As
discussedin the beginning of this section, the balance
Definition 3.2. Let {Dt : t ≥ 0} be a sequence ofbetweenthe
distributions of each type of subcube andbinary random variables such that Dt = 1 if for all
the
distributionsof actual agents plays a crucial role intime steps on or before t, the number of agents for any
ouranalysis.
Fix
an arbitrary time t, we classify the3subcube in V with size ℓ̂2 × ℓ̂2 × ℓ̂2 is between ℓ̂2 and2joint
conﬁgurationsof the agents into four types:2ℓ̂2 log n. Also, let D = Dn2.5 .
• type 1 (namely P1,t ): when |Gt | ≤ 21 ((2n + 1)/ℓ̂2 )3f
1
and |Af,GThe following lemma shows that Dt = 1 with hight | ≥ 2 |At |.
probability:• type 2 (namely P2,t ): when |Gt | ≤ 12 ((2n + 1)/ℓ̂2 )3f
1
and |Af,Gt | < 2 |At |.
Lemma 3.2. For any t ≤ n2.5 , Pr[Dt = 0] ≤• type 3 (namely P3,t ): when |Gt | > 12 ((2n + 1)/ℓ̂2 )31
exp(− 15log2 n) for suﬃciently large n.
1u
and |Au,Gt | < 2 |At |.
• type 4 (namely P4,t ): when |Gt | > 12 ((2n + 1)/ℓ̂2 )3
We now state two bounds on the growth rate of the1uagent types, one relative to the “boundary subcubes”
and |Au,Gt | ≥ 2 |At |.
∂Gt and one relative to the total agents of each type:
Recall that Ft refers to the information on the global
conﬁgurations up to time t. We shall abuse notation
Corollary 3.1. For some constant τ0 ,slightly and say Ft ∈ Pi,t if the conﬁguration of the
agents at time t belongs to the ith type described above.
τ0 ℓ̂2B−6G]
Pr |∆At ∩ ∆At | ≥ |∂Gt | ·Ft , Dt = 1 ≥ τ0 log n.Notice that Ft belongs to exactly one of the sets P1,t ,4 log13 n
P2,t , P3,t , P4,t . In brief, scenarios P1,t and P2,t havea majority of uninfected subcubes, while P3,t and P4,tConsequently,
have a majority of infected subcubes. From anotherperspective, P1,t and P3,t refer to situations when theτ0 ℓ̂2−6
G]dominant types (with respect to the status of infection)Pr |∆At | ≥ |∂Gt | ·Ft , Dt = 1 ≥ τ0 log n
4 log13 n
are dense in their subcube types (infected/uninfected

1620

Copyright © SIAM.
Unauthorized reproduction of this article is prohibited.

subcubes), while P2,t and P4,t refer to the more uniform
scenarios. The next lemma states that when Ft ∈ P1,t ∪P2,t , the total number of infected agents |Aft | grows inproportion to a monotone function of |Aft | within ∆t
steps. On the other hand, when Ft ∈ P3,t ∪ P4,t , thetotal number of uninfected agents |Aut | is reduced inproportion to a monotone function of |Aut | within ∆t
steps.

Note thatbound suggests that for each time
√ this 45
increment 4 mlogn∆t, either the number of infectednagents doubles or the number of uninfected agents is
reduced by half with high)Therefore, within( √ probability.
45
log
n∆t
= 128nℓ̂2 log47 ntime at most 2 log n · 4 mn
all the agents get infected with probability at least1 − 2 log n exp(− log2 n). This proves Theorem 3.1.
To summarize our approach, Corollaries 3.1 and3.2 ﬁrst translate the local infection rate of Lemma 3.1
Lemma 3.3. Fix an arbitrary t, deﬁne the following into a rate based on the subcube types (i.e. good andevents,bad subcubes). Then Lemma 3.3 further aggregates the
}
{
(
)2/3
growth rate to depend only on the infected and uninf
|At |
ℓ̂2
e1 (t) =|∆At | ≥ 0.09τ0 4ℓ̂ log
fected agents, by looking at the geometrical arrange13
2n
log n
2
{
}
ment of the subcubes. Nevertheless, the bound fromτ2e2 (t) =|∆At | ≥ 8 log038 n |Aft |Lemma 3.3 is still too crude, but
a long}{√ mby making
)2/3
(
45
|Au
log
n
times,
enoughsequenceoftrials
i.e.
4
at
ℓ̂2
t|
n
e3 (t) =|∆At | ≥ 0.015τ0 4ℓ̂ log2 nlog13 n
2
least
one
of
the
four
scenarios
deﬁned
in
Lemma
3.3
{
}
τ2
e4 (t) =|∆At | ≥ 8 log038 n |Aut | .
occurs for a signiﬁcant number of times, despite theΩ(log−6 n) probability of occurrence for each individual−6
We have Pr[ei | Ft ∈ Pi,t , Dt = 1] ≥ τ0 log n for step for any of the four scenarios. This leads to thei = 1, 2, 3, 4.
probabilistic bound for χ1 (t) ∨ χ2 (t).

Intuitively, e1 and e2 connect the number of newly
infected agents to the original number of infected agents.
When e1 or e2 are triggered suﬃciently many times,
the number of infected agents doubles. Meanwhile, e3
and e4 connect the number of newly infected agents tothe original number of uninfected agents. When e3 or
e4 are triggered suﬃciently many times, the number of
uninfected agents halves.
The key to proving Lemma 3.3, which will ultimately lead to a bound on the global growth rate of doubling/halving the total number of infected/uninfectedagents as depicted in the next proposition, is a geometric relation between the boundary of Gt , i.e. ∂Gt ,and Gt itself. More speciﬁcally, an isoperimetric boundon Gt guarantees that no matter how packed together
these good subcubes are, there are still an order |Gt |2/3
of them exposed to the bad subcubes, hence the global
infection rate cannot be too slow.
Our major proposition presented next essentiallypins down the number of times these events need to
be triggered to double the number of infected agents or
halve the number of uninfected ones.
Proposition 3.1. Consider the information diﬀusion
problem√over V 3 with m agents. For any ﬁxed t ≤45
n2.5 − 4 m
n log n∆t, deﬁne the following events
χ1 (t) ≡(|Af √ mχ2 (t) ≡t+4nlog45 n∆t)
| ≥ 2|Aft | and)(1|Aut+4√ m log45 n∆t | ≤ |Aut | .
n2

We have Pr[χ1 (t) ∨ χ2 (t)] ≥ 1 − exp(− log2 n).

1621

4 The case when the number of agents is sparse
Finally, let us state our result on the case where m =o(n):Proposition 4.1. Let a1 , a2 , ..., am be placed uniformly
at random on V 3 , where m < n log−2 n. Let a1 be theagent that holds a virus at t = 0, and T be the diﬀusion
time. We have for any constant c > 0,
Pr[T <
Pr[T >

n3log−c n] ≤ log−c n andm

2n3
log15 n] ≤ exp(−(log2 n)/2).
m

References[1] O. S. M. Alves, F. P. Machado, S. Yu. Popov,and K. Ravishankar.
The shape theorem forthe frog model with random initial conﬁguration.
arXiv:math/0110280v1, October 2001.
[2] O. S. M. Alves, S. Yu. Popov, and F. P. Machado. The
shape theorem for the frog model. Annals of Applied
Probability, 12(2):533–546, 2002.
[3] Tamio Arai, Eiichi Yoshida, and Jun Ota. Information diﬀusion by local communication of multiple mobile robots. In Proceedings of IEEE International Conference on Systems, Man and Cybernetics, 1993, pages
535–540, 1993.
[4] Andrea E. F. Clementi, Angelo Monti, and Riccardo
Silvestri. Fast ﬂooding over manhattan. In PODC,
pages 375–383. ACM, 2010.

Copyright © SIAM.
Unauthorized reproduction of this article is prohibited.

[5] Andrea E. F. Clementi, Francesco Pasquale, and Riccardo Silvestri. Manets: High mobility can make up for
low transmission power. In ICALP (2), volume 5556
of Lecture Notes in Computer Science, pages 387–398.
Springer, 2009.
[6] Peter D. Hoﬀ, Adrian E. Raftery, and Mark S. Handcock. Latent space approaches to social network analysis. Journal of the American Statistical Association,
97:1090–1098, 2001.
[7] Harry Kesten and Vladas Sidoravicius. The spread ofa rumor or infection in a moving population. Annalsof Probability, 33(6):pp. 2402–2462, 2005.
[8] Abdelmajid Khelil, Christian Becker, Jing Tian, andKurt Rothermel. An epidemic model for information
diﬀusion in manets. In Proceedings of the 5th ACM
international workshop on Modeling analysis and simulation of wireless and mobile systems, MSWiM, pages
54–60. ACM, 2002.
[9] Yuval Peres, Alistair Sinclair, Perla Sousi, and Alexandre Stauﬀer:. Mobile geometric graphs: Detection,
coverage and percolation. In SODA, pages 412–428.
SIAM, 2011.
[10] Alberto Pettarin, Andrea Pietracaprina, Geppino
Pucci, and Eli Upfal.
Tight bounds on information dissemination in sparse mobile networks.
arXiv:1101.4609v2, 2011.
[11] Purnamrita Sarkar and Andrew W. Moore. Dynamic
social network analysis using latent space models.
SIGKDD Explorations, 7(2):31–40, 2005.
[12] Alistair Sinclair and Alexandre Stauﬀer. Mobile geometric graphs, and detection and communication problems in mobile wireless networks. arXiv:1005.1117v2,
2010.
[13] Yi Wang, Shyam Kapadia, and Bhaskar Krishnamachari. Infection spread in wireless networks withrandom and adversarial node mobilities. In Proceeding of the 1st ACM SIGMOBILE workshop on Mobility
models, MobilityModels ’08, pages 17–24. ACM, 2008.
[14] David Williams. Probability with martingales. Cambridge mathematical textbooks. Cambridge University
Press, 1991.

1622

Copyright © SIAM.
Unauthorized reproduction of this article is prohibited.