arXiv:1511.03927v4 [cs.DC] 23 Jul 2016

Find Your Place: Simple Distributed Algorithms for
Community Detection
Luca Becchetti

Andrea Clementi

Sapienza Università di Roma
Rome, Italy
becchetti@dis.uniroma1.it

Università di Roma Tor Vergata
Rome, Italy
clementi@mat.uniroma2.it

Emanuele Natale

Francesco Pasquale

Luca Trevisan

Sapienza Università di Roma
Rome, Italy
natale@di.uniroma1.it

Sapienza Università di Roma
Rome, Italy
pasquale@dis.uniroma1.it

U.C. Berkeley
Berkeley, CA, United States
luca@berkeley.edu

Abstract
Given an underlying graph, we consider the following dynamics: Initially, each node
locally chooses a value in {−1, 1}, uniformly at random and independently of other nodes.
Then, in each consecutive round, every node updates its local value to the average of the
values held by its neighbors, at the same time applying an elementary, local clustering rule
that only depends on the current and the previous values held by the node.
We prove that the process resulting from this dynamics produces a clustering that exactly
or approximately (depending on the graph) reflects the underlying cut in logarithmic time,
under various graph models that exhibit a sparse balanced cut, including the stochastic
block model. We also prove that a natural extension of this dynamics performs community
detection on a regularized version of the stochastic block model with multiple communities.
Rather surprisingly, our results provide rigorous evidence for the ability of an extremely
simple and natural dynamics to address a computational problem that is non-trivial even in
a centralized setting.
Keywords: Distributed Algorithms, Averaging Dynamics, Community Detection, Spectral
Analysis, Stochastic Block Models.

1

Introduction

Consider the following distributed algorithm on an undirected graph: At the outset, every
node picks an initial value, independently and uniformly at random in {−1, 1}; then, in each
synchronous round, every node updates its value to the average of those held by its neighbors.
A node also tags itself “blue” if the last update increased its value, “red” otherwise.
We show that under various graph models exhibiting sparse balanced cuts, including the
stochastic block model [27], the process resulting from the above simple local rule converges, in
logarithmic time, to a colouring that exactly or approximately (depending on the model) reﬂects
the underlying cut. We further show that our approach simply and naturally extends to more
communities, providing a quantitative analysis for a regularized version of the stochastic block
model with multiple communities.
Our algorithm is one of the few examples of a dynamics [4, 3, 20, 46] that solves a computational problem that is non-trivial in a centralized setting. By dynamics we here mean
synchronous distributed algorithms characterized by a very simple structure, whereby the state
of a node at round t depends only on its state and a symmetric function of the multiset of states
of its neighbors at round t − 1, while the update rule is the same for every graph and every node
and does not change over time. Note that this deﬁnition implies that the network is anonymous,
that is, nodes do not possess distinguished identities. Examples of dynamics include update
rules in which every node updates its state to the plurality or the median of the states of its
neighbors,1 or, as is the case in this paper, every node holds a value, which it updates to the
average of the values held by its neighbors. In contrast, an algorithm that, say, proceeds in two
phases, using averaging during the ﬁrst 10 log n rounds and plurality from round 1 + 10 log n
onward, with n the number of nodes, is not a dynamics according to our deﬁnition, since its
update rule depends on the size of the graph. As another example, an algorithm that starts by
having the lexicographically ﬁrst vertex elected as “leader” and then propagates its state to all
other nodes again does not meet our deﬁnition of dynamics, since it assigns roles to the nodes
and requires them to possess distinguishable identities.
The Averaging dynamics, in which each node updates its value to the average of its neighbors, is perhaps one of the simplest and most interesting examples of linear dynamics and it
always converges when G is connected and not bipartite: It converges to the global average of
the initial values if the graph is regular and to a weighted global average if it isn’t [12, 49]. Important applications of linear dynamics have been proposed in the recent past [31, 5, 52, 33], for
example to perform basic tasks such as self-stabilizing consensus in faulty distributed systems
[7, 54, 47]. The convergence time of the Averaging dynamics is the mixing time of a random
walk on G [49]. It is logarithmic in |V | if the underlying graph is a good expander [28], while it
is slower on graphs that exhibit sparse cuts.
While previous work on applications of linear dynamics has focused on tasks that are speciﬁc
to distributed computing (such as reaching consensus, or stability in the presence of faulty
nodes), in this paper we show that our simple protocol based on the the Averaging dynamics
is able to address community detection, i.e., it identiﬁes partition (V1 , V2 ) of a clustered graph
G = ((V1 , V2 ), E), either exactly (in which case we have a strong reconstruction algorithm) or
approximately (in which case we speak of a weak reconstruction algorithm).

1.1

Our contributions

Consider a graph G = (V, E). We show that, if a partition (V1 , V2 ) of G exists, such that 1V1 −1V2
is2 (or is close to) a right-eigenvector of the second largest eigenvalue of the transition matrix
of G, and the gap between the second and the third largest eigenvalues is suﬃciently large,
1

When states correspond to rational values.
As explained further, 1Vi , is the vector with |V | components, such that the j-th component is 1 if j ∈ Vi , it
is 0 otherwise.
2

1

our algorithm identiﬁes the partition (V1 , V2 ), or a close approximation thereof, in a logarithmic
number of rounds. Though the algorithm we propose does not explicitly perform any eigenvector
computation, its exploits the spectral structure of the underlying graph, based on the intuition
that the dynamics is a distributed simulation of the power method. Our analysis involves two
main novelties, relating to how nodes assign themselves to clusters, and to the spectral bounds
that we prove for certain classes of graphs.
A conceptual contribution is to make each node, at each round t, assign itself to a cluster
(“ﬁnd its place”) by considering the diﬀerence between its value at time t and its value at time
t − 1. Such a criterion removes the component of the value lying in the ﬁrst eigenspace without
explicitly computing it. This idea has two advantages: it allows a particularly simple algorithm,
and it gives a running time that depends on the third eigenvalue of the transition matrix of the
graph. In graphs that have the structure of two expanders joined by a sparse cut, the running
time of the algorithm depends only on the expansion of the components and it is faster than
the mixing time of the overall graph. To the best of our knowledge, this is the ﬁrst distributed
block reconstruction algorithm converging faster than the mixing time.
Our algorithm works on any graph where (i) the right-eigenspace of the second eigenvalue
of the transition matrix is correlated to the cut between the two clusters and (ii) the gap
between the second and third eigenvalues is suﬃciently large. While these conditions have been
investigated for the spectrum of the adjacency matrix of the graph, our analysis requires these
conditions to hold for the transition matrix. A technical contribution of this paper is to show
that such conditions are met by a large class of graphs, that includes graphs sampled from the
stochastic block model. Proving spectral properties of the transition matrix of a random graph
is more challenging than proving such properties for the adjacency matrix, because the entries
of the transition matrix are not independent.
Strong reconstruction for regular clustered graphs. A (2n, d, b)-clustered regular graph
G = ((V1 , V2 ), E) is a connected graph over vertex set V1 ∪ V2 , with |V1 | = |V2 | = n, adjacency
matrix A, and such that every node has degree d and it has (exactly) b neighbors outside its
cluster. If the two subgraphs induced by V1 and V2 are good expanders and b is suﬃciently
small, the second and third eigenvalues of the graph’s transition matrix P = (1/d) · A are
separated by a large gap. In this case, we can prove that the following happens with high
probability (for short w.h.p 3 ): If the Averaging dynamics is initialized by having every node
choose a value uniformly and independently at random in {−1, 1}, within a logarithmic number
of rounds the system enters a regime in which nodes’ values are monotonically increasing or
decreasing, depending on the community they belong to. As a consequence, every node can
apply a simple and completely local clustering rule in each round, which eventually results in a
strong reconstruction (Theorem 3.2).
We then show that, under mild assumptions, a graph selected from the regular stochastic block
model [13] is a (2n, d, b)-clustered regular graph that satisﬁes the above spectral gap hypothesis,
w.h.p. We thus obtain a fast and extremely simple dynamics for strong reconstruction, over
the full range of parameters of the regular stochastic block model for which this is known to be
possible using centralized algorithms [45, 13] (Section 1.2 and Corollary 3.3).
We further show that a natural extension of our algorithm, in which nodes maintain an array
of values and an array of colors, correctly identiﬁes a hidden balanced k-partition in a regular
clustered graph with a gap between λk and λk+1 . Graphs sampled from the regular stochastic
block model with k communities satisfy such conditions, w.h.p. (Theorem 5.1).
Weak reconstruction for non-regular clustered graphs. As a main technical contribution, we extend the above analysis to show that our dynamics also ensures weak reconstruction in clustered graphs having two clusters that satisfy an approximate regularity condition and a gap between second and third eigenvalues of the transition matrix P (TheoWe say that a sequence of events En , n = 1, 2, . . . holds with high probability if P (En ) = 1 − O(1/nγ ) for
some positive constant γ > 0.
3

2

rem 4.3). As an application, we then prove that these conditions are met by the stochastic
block model [1, 17, 18, 21, 27, 30, 41], a random graph model that oﬀers a popular framework
for the probabilistic modelling of graphs that exhibit good clustering or community properties.
We here consider its simplest version, i.e., the random graph G2n,p,q consisting of 2n nodes
and an edge probability distribution deﬁned as follows: The node set is partitioned into two
subsets V1 and V2 , each of size n; edges linking nodes belonging to the same partition appear
in E independently at random with probability p = p(n), while edges connecting nodes from
diﬀerent partitions appear with probability q = q(n) < p. Calling a = pn and b = qn, we
prove that graphs sampled from G2n,p,q satisfy
the above approximate regularity and spectral
p
gap conditions, w.h.p., whenever a − b > (a + b) · log n (Lemma 4.4).
We remark that the latter result for the stochastic block model follows from an analysis that
applies to general non-random clustered graphs and hence does not exploit crucial properties
of random graphs. A further technical contribution of this paper is a reﬁned, ad-hoc analysis
of the Averaging dynamics for the G2n,p,q model, showing that this protocol achieves weakreconstruction,
correctly classifying a 1 − ε fraction of vertices, in logarithmic time whenever a −
p
b > Ωε ( (a + b)) and the expected degree d = a+b grows at least logarithmically (Theorem 4.7).
This reﬁned analysis requires a deeper understanding of the eigenvectors of the transition matrix
of G. Coja-Oghlan [17] deﬁned certain graph properties that guarantee that a near-optimal
bisection can be found based on eigenvector computations of the adjacency matrix. Similarly, we
show simple suﬃcient conditions under which a right eigenvector of the second largest eigenvalue
of the transition matrix of a graph approximately identiﬁes the hidden partition. We give a tight
analysis of the spectrum of the transition matrix of graphs sampled from the stochastic block
model in Section D.2. Notice that the analysis of the transition matrix is somewhat harder than
that of the adjacency matrix, since the entries are not independent of each other; we were not
able to ﬁnd comparable results in the existing literature.

1.2

Related work and additional remarks

Dynamics for block reconstruction. Dynamics received considerable attention in the recent
past across diﬀerent research communities, both as eﬃcient distributed algorithms [4, 7, 47, 42]
and as abstract models of natural interaction mechanisms inducing emergent behavior in complex
systems [3, 14, 20, 23, 46]. For instance, simple averaging dynamics have been considered to
model opinion formation mechanisms [19, 24], while a number of other dynamics have been
proposed to describe diﬀerent social phenomena [22]. Label propagation algorithms [48] are
dynamics based on majority updating rules [4] and have been applied to some computational
problems including clustering. Several papers present experimental results for such protocols
on speciﬁc classes of clustered graphs [6, 38, 48]. The only available rigorous analysis of label
propagation algorithms on planted partition graphs is the one presented in [34], where the
authors propose and analyze a label propagation protocol on G2n,p,q for dense topologies. In
particular, their analysis considers the case where p = Ω(1/n1/4−ε ) and q = O(p2 ), a parameter
range in which very dense clusters of constant diameter separated by a sparse cut occur w.h.p.
In this setting, characterized by a polynomial gap between p and q, simple combinatorial and
concentration arguments show that the protocol converges in constant expected time. They also
conjecture a logarithmic bound for sparser topologies.
Because of their relevance for the reconstruction problem, we also mention another class of
algorithms, belief propagation algorithms, whose simplicity is close to that of dynamics. Belief
propagation algorithms are best known as message-passing algorithms for performing inference in
graphical models [39]. Belief propagation cannot be considered a dynamics: At each round, each
node sends a diﬀerent message to each neighbors, thus the update rule is not symmetric w.r.t.
the neighbors, requiring thus port numbering [51], and the required local memory grows linearly
in the degree of the node. Non-rigorous methods have given strong evidence that some belief
propagation algorithms are optimal for the reconstruction problem [18]. Its rigorous analysis is
3

a major challenge; in particular, the convergence to the correct value of belief propagation is
far from being fully-understood on graphs which are not trees [53, 43]. As we discuss in the
next subsection, more complex algorithms, inspired by belief propagation, have been rigorously
shown to perform reconstruction optimally.
General algorithms for block reconstruction. While an important goal, improving performance of spectral clustering algorithms and testing their limits to the purpose of block reconstruction is not the main driver behind this work. Still, for the sake of completeness, we next
compare our dynamics to previous general algorithms for block reconstruction.
Several algorithms for community detection are spectral: They typically consider the eigenvector associated to the second eigenvalue of the adjacency matrix A of G, or the eigenvector
corresponding to the largest eigenvalue of the matrix A − nd J [8, 16, 17, 41] 4 , since these
are correlated with the hidden partition. More recently spectral algorithms have been proposed [2, 17, 44, 35, 11] that ﬁnd a weak reconstruction even in the sparse, tight regime.
Even though the above mentioned algorithms have been presented in a centralized setting,
spectral algorithms turn out to be a feasible approach also for distributed models. Indeed,
Kempe and McSherry [32] show that eigenvalue computations can be performed in a distributed
fashion, yielding distributed algorithms for community detection in various models, including
the stochastic block model. However, the algorithm of Kempe and McSherry as well as any
distributed version of the above mentioned centralized algorithms are not dynamics. Actually,
adopting the eﬀective concept from Hassin and Peleg in [26], such algorithms are even not
light-weight : Diﬀerent and not-simple operations are executed at diﬀerent rounds, nodes have
identities, messages are treated diﬀerently depending on the originator, and so on. Moreover, a
crucial aspect is convergence time: The mixing time of the simple random walk on the graph is
a bottleneck for the distributed algorithm of Kempe and McSherry and for any algorithm that
performs community detection in a graph G by employing the power method or the Lanczos
method [36] as a subroutine to compute the eigenvector associated to the second eigenvalue of
the adjacency matrix of G. Notice that the mixing time of graphs sampled from G2n,p,q is at
Ω(1) .
least of the order of a+b
2b : hence, it can be super-logarithmic and even n
In general, the reconstruction problem has been studied extensively using a multiplicity of
techniques, which include combinatorial algorithms [21], belief propagation [18], spectral-based
techniques [41, 17], Metropolis approaches [30], and semideﬁnite programming [1], among others.
Stochastic Block Models have been studied in a number of areas, including computer science
[8, 41, 40], probability theory [45], statistical physics [18], and social sciences [27]. Unlike the
distributed setting, where the existence of light-weight protocols [26] is the main issue (even in
non-sparse regimes), in centralized setting strong attention has been devoted to establishing
sharp thresholds for weak and strong reconstruction. Deﬁne a = np as the expected internal
degree (the number of neighbors that each node has on the same side of the partition) and b = nq
as the expected external degree (the number of neighbors that each node has on the opposite
side of the partition).
Decelle et al. [18] conjectured that weak reconstruction is possible if and
√
and Mossel et al. [44, 40, 45]. Strong
only if a − b > 2 a + b. This was proved by Massoulie
√
recovery is instead possible if and only if a − b > 2 a + b + log n [1].
Versions of the stochastic block model in which the random graph is regular have also been
considered [45, 13]. In particular√Brito et al. [13] show that strong reconstruction is possible in
polynomial-time when a − b > 2 a + b − 1.
4

A is the adjacency matrix of G, J is the matrix having all entries equal to 1, d is the average degree and n
is the number of vertices.

4

2

Preliminaries

Distributed block reconstruction. Let G = ((V1 , V2 ), E) be a graph with V1 ∩ V2 = ∅.
A weak (block) reconstruction is a two-coloring of the nodes that separates V1 and V2 up to
a small fraction of the nodes. Formally, we deﬁne an ε-weak reconstruction as a map f :
V1 ∪ V2 → {red, blue} such that there are two subsets W1 ⊆ V1 and W2 ⊆ V2 with |W1 ∪ W2 | >
(1 − ε)|V1 ∪ V2 | and f (W1 ) ∩ f (W2 ) = ∅. When ε = 0 we say that f is a strong reconstruction.
Given a graph G = ((V1 , V2 ), E), the block reconstruction problem requires computing an εreconstruction of G.
In this paper, we propose the following distributed protocol. It is based on the averaging
dynamics and produces a coloring of the nodes at the end of every round. In the next two
sections we show that, within O(log n) rounds, the coloring computed by the algorithm we
propose achieves strong reconstruction of the two blocks in the case of clustered regular graphs
and weak reconstruction in the case of clustered non-regular graphs.
Averaging protocol:
Rademacher initialization: At round t = 0 every node v ∈ V independently samples
its value from {−1, +1} uniformly at random;
Updating rule: At each subsequent round t > 1, every node v ∈ V
1. (Averaging dynamics) Updates its value x(t) (v) to the average of the values
of its neighbors at the end of the previous round
2. (Coloring) If x(t) (v) > x(t−1) (v) then v sets color(t) (v) = blue otherwise v sets
color(t) (v) = red.
The choice of the above coloring rule will be clariﬁed in the next section, just before Theorem
3.2. We give here two remarks. First of all, the algorithm is completely oblivious to time, being
a dynamics in the strictest sense. Namely, after initialization the protocol iterates over and over
at every node. Convergence to a (possibly weak) reconstruction is a property of the protocol,
of which nodes are not aware, it is something that eventually occurs. Second, the clustering
criterion is completely local, in the sense that a decision is individually and independently made
by each node in each round, only on the basis of its state in the current and previous rounds.
This may seem counterintuitive at ﬁrst, but it is only superﬁcially so. Despite being local,
the clustering criterion uses information that reﬂects the global structure of the network, since
nodes’ values are related to the second eigenvector of the network’s transition matrix.
The Averaging dynamics and random walks on G. The analysis of the Averaging
dynamics on a graph G is closely related to the behavior of random walks in G, which are best
studied using tools from linear algebra that we brieﬂy summarize below.
Let G = (V, E) be an undirected graph (possibly with multiple edges and self loops), A its
adjacency matrix and di the degree of node i. The transition matrix of (the random walk on) G
is the matrix P = D −1 A, where D is the diagonal matrix such that Di,i = di . Pi,j = (1/di ) · Ai,j
is thus the probability of going from i to j in one-step of the random walk on G. P operates as
the random walk process on G by left multiplication, and as the Averaging dynamics by right
multiplication. For i = 1, 2, deﬁne 1Vi , as the |V |-dimensional vector, whose j-th component is
1 if j ∈ Vi , it is 0 otherwise. If (V1 , V2 ) is a bipartition of the nodes with |V1 | = |V2 | = n, we
deﬁne the partition indicator vector χ = 1V1 − 1V2 . If x is the initial vector of values, after t
rounds of the Averaging dynamics the vector of values at time t is x(t) = P t x. The product of
the power of a matrix times a vector is best understood in terms of the spectrum of the matrix,
which is what we explore in the next section.

5

In what follows we always denote by λ1 > . . . > λ2n the eigenvalues of P . Recall that,
since P is a stochastic matrix we have λ1 = 1 and λ2n > −1, moreover for all graphs that are
connected and not bipartite it holds that λ2 < 1 and λ2n > −1. We denote by λ the largest, in
absolute value, among all but the ﬁrst two eigenvalues, namely λ = max {|λp
: i = 3, 4, . . . , 2n}.
i| P
2
Unless otherwise speciﬁed, the norm of a vector x is the ℓ2 norm kxk :=
i (x(i)) and the
norm of a matrix A is the spectral norm kAk := supx:kxk=1 kAxk. For a diagonal matrix, this is
the largest diagonal entry in absolute value.

3

Strong reconstruction for regular graphs

If G is d-regular then P = (1/d)A is a √
real symmetric matrix and P and A have the same set
of eigenvectors. We denote by v1 = (1/ 2n)1, v2 , . . . , v2n a basis of orthonormal eigenvectors,
where each vi is the eigenvector
associated to eigenvalue λi . Then, we can write a vector x as
P
a linear combination x = i αi vi and we have:
!
2n
X
X
1 X
t
t
λti αi vi ,
x(i) 1 +
P x=
λi αi vi =
2n
i=2

i

i

x(t)

P tx

which implies that
=
tends to α1 v1 as t tends to inﬁnity, i.e., it converges to the vector
that has the average of x in every coordinate.
We next show that, if the regular graph is “well” clustered, then the Averaging protocol
produces a strong reconstruction of the two clusters w.h.p.

Definition 3.1 (Clustered Regular Graph). A (2n, d, b)-clustered regular graph G = ((V1 , V2 ), E)
is a graph over vertex set V1 ∪ V2 , with |V1 | = |V2 | = n and such that: (i) Every node has degree
d and (ii) Every node in cluster V1 has b neighbors in cluster V2 and every node in V2 has b
neighbors in V1 .
We know that 1 is an eigenvector of P with eigenvalue 1, and it is easy to see that the
partition indicator vector χ is an eigenvector of P with eigenvalue 1 − 2b/d (see Observation A.3
in Appendix A). We ﬁrst show that, if 1 − 2b/d happens to be the second eigenvalue, after t
rounds of the Averaging dynamics, the conﬁguration x(t) is close to a linear combination of 1
and χ. Formally, if λ < 1 − 2b/d we prove (see Lemma C.1 in Appendix C) that there are reals
α1 , α2 such that for every t
x(t) = α1 1 + α2 λt2 χ + e(t)

where

e(t)

∞

√
6 λt 2n .

(1)

Informally speaking, the equation above naturally “suggested” the choice of the coloring rule
in the Averaging protocol, once we considered the diﬀerence of two consecutive values of any
node u, i.e.,
(t−1)
x(t−1) (u) − x(t) (u) = α2 λt−1
(u) − e(t) (u) .
2 (1 − λ2 )χ(u) + e

(2)

Intuitively, if λ is suﬃciently small, we can exploit the bound on e(t) ∞ in (3) to show that,
after a short initial phase, the sign of x(t−1) (u) − x(t) (u) is essentially determined by χ(u), thus
by the community u belongs to, w.h.p. The following theorem and its proof provide formal
statements of the above fact.
Theorem 3.2 (Strong reconstruction). Let G = ((V1 , V2 ), E) be a connected (2n, d, b)-clustered
regular graph with 1 − 2b/d > (1 + δ)λ for an arbitrarily-small constant δ > 0. Then the
Averaging protocol produces a strong reconstruction within O(log n) rounds, w.h.p.

6


Outline of Proof. From (3), we have that sgn x(t−1) (u) − x(t) (u) = sgn (α2 χ(u)) whenever
(t−1)
(u) − e(t) (u)
α2 λt−1
2 (1 − λ2 ) > e

(3)

√
From (3) we have that e(t) (u) 6 λt 2n, thus (3) is satisﬁed for all t such that
!
√
2 2n
1
t − 1 > log
·
.
|α2 |(1 − λ2 )
log (λ2 /λ)
The second key-step of the proof relies on the randomness of the initial vector. Indeed, since
x is a vector of independent and uniformly distributed random variables in {−1, 1}, the absolute
diﬀerence between the two partial averages in the two communities, i.e. |α2 |, is “suﬃciently”
large, w.h.p. More precisely, observe that both hx, χi and hx, 1i have the distribution of a sum of

,
2n Rademacher random variables. Such a sum takes the value 2k − 2n with probability 21n 2n
k

1
1 2n
√
and so every possible value has probability at most 2n n ≈ 2πn . Consequently, if R is the
√ 
sum of 2n Rademacher random variables, we have P |R| 6 δ 2n 6 O(δ). This implies that
1
hχ, xi > n−γ , for some positive constant γ, w.h.p. (see Lemma B.1). The theorem
|α2 | = 2n
thus follows from the above bound on |α2 | and from the hypothesis λ2 > (1 + δ)λ.
Remark. Graphs to which Theorem 3.2 apply are those consisting of two regular expanders
connected by a regular sparse cut. Indeed, let G = ((V1 , V2 ), E) be a (2n, d, b)-clustered regular
graph, and let λA = max {λ2 (A1 ), λ2 (A2 )} and λB = λ2 (B), where A1 , A2 and B are the adjacency matrices of the subgraphs induced by V1 , V2 and the cut between V1 and V2 , respectively.
Since λ = ad λA + db λB , if a − b > (1 + ε)(aλA + bλB ), G satisﬁes the hypothesis of Theorem 3.2.
Regular stochastic block model. We can use Theorem 3.2 to prove that the Averaging
protocol achieves strong reconstruction in the regular stochastic block model. In the case of
two communities, a graph on 2n vertices is obtained as follows: Given two parameters a(n)
and b(n) (internal and external degrees, respectively), partition vertices into two equal-sized
subsets V1 and V2 and then sample a random a(n)-regular graph over each of V1 and V2 and
a random b(n)-regular graph between V1 and V2 . This model can be instantiated in diﬀerent
ways depending on how one samples the random regular graphs (for example, via the uniform
distribution over regular graphs, or by taking the disjoint union of random matchings) [45, 13].
If G is a graph sampled from the regular stochastic block model with internal and external
degrees a and b respectively, then it is a (2n, d, b)-clustered graph with largest eigenvalue of
the transition matrix 1 and corresponding eigenvector 1, while χ is also an eigenvector, with
eigenvalue 1 − 2b/d, where d := a + b. Furthermore, we can derive the following upper bound on
the maximal absolute value achieved by the other 2n−2 eigenvalues corresponding to eigenvectors
orthogonal to 1 and χ:
2 √
(4)
( a + b − 1 + on (1))
λ6
a+b
This bound can be proved using some general result of Friedman and Kohler [25] on random
a−b
degree k lifts of a graph. (see Lemma D.1 in Appendix D). Since λ2 = a+b
, using (3) in Theorem
3.2, we get a strong reconstruction for the regular stochastic block model:
Corollary 3.3. √Let G be a random graph sampled from the regular stochastic block model with
a − b > 2(1 + η) a + b for any constant η > 0, then the Averaging protocol produces a strong
reconstruction in O(log n) rounds, w.h.p.

7

4

Weak reconstruction for non-regular graphs

The results of Section 3 rely on very clear spectral properties of regular, clustered graphs, immediately reﬂecting their underlying topological structure. Intuition suggests that these properties
should be approximately preserved if we suitably relax the notion of regularity. With this simple
intuition in mind, we generalize our approach for regular graphs to a large class of non-regular
clustered graphs.
Definition 4.1 (Clustered γ-regular graphs). A (2n, d, b, γ)-clustered graph G = ((V1 , V2 ), E)
is a graph over vertex set V1 ∪ V2 , where |V1 | = |V2 | = n such that: i) Every node has degree
d ± γd, and ii) Every node in V1 has b ± γd neighbors in V2 and every node in V2 has b ± γd
neighbors in V1 .
If G is not regular then matrix P = D −1 A is not symmetric in general, however it is possible
to relate its eigenvalues and eigenvectors to those of a symmetric matrix as follows. Denote
the normalized adjacency matrix of G as N := D −1/2 AD −1/2 = D 1/2 P D −1/2 . Notice that N is
symmetric, P and N have the same eigenvalues λ1 , . . . , λ2n , and x is an eigenvector of P if and
only if D 1/2 x is an eigenvector of N (if G is regular then P and N are the same matrix). Let
w1 , . . . , w2n be a basis of orthonormal eigenvectors of N , with wi the eigenvector associated to
D 1/2 1
. If we set vi := D −1/2 wi , we obtain a set
eigenvalue λi , for every i. We have that w1 = kD
P 1/2 1k
of eigenvectors for P and we can write x = i αi vi as a linear combination of them. Then, the
averaging process can again be described as
t

P x=

X

λti αi vi

= α1 v1 +

2n
X

λti αi vi .

i=2

i

So, if G is connected and not bipartite, the Averaging dynamics converges to α1 v1 . In general,
it is easy to see that αi = wiT D 1/2 x (see the ﬁrst lines in the proof of Lemma 4.2) and α1 v1 is
the vector
P
1T Dx
−1/2
T 1/2
i di x(i)
1= P
w1 =
(w1 D x) · D
· 1.
1/2
2
kD 1k
i di

As in the regular case, if the transition matrix P of a clustered γ-regular graph has λ2 close to
1 and |λ3 |, . . . , |λ2n | small, the Averaging dynamics has a long phase in which x(t) = P t x is
close to α1 1 + α2 v2 .
However, providing an argument similar to the regular case is considerably harder, since
the partition indicator vector χ is no longer an eigenvector of P . In order to ﬁx this issue, we
generalize (3), proving in Lemma 4.2 that x(t) is still close to a linear combination of 1 and χ.
We set ν = 1 − 2b
d , since this value occurs frequently in this section.
Lemma 4.2. Let G be a connected (2n, d, b, γ)-clustered graph with γ 6 1/10, and assume the
Averaging dynamics is run on G with initial vector x. If λ < ν we have:

for some vectors z and e(t)

x(t) = α1 1 + α2 λt2 χ + α2 λt2 z + e(t) ,
√
88 γ
2n and ke(t) k 6 4λt kxk. Coefficients α1 and α2
with kzk 6 ν−λ
3
1

are α1 =

1⊺ Dx
1
kD 2 1k2

and α2 =

w2⊺ D 2 x

1
w2⊺ D 2 χ

.

Outline of Proof. We prove the following two key-facts: (i) the second eigenvalue of the transition
matrix of G is not much smaller than 1 − 2b/d, and (ii) D 1/2 χ is close, in norm, to its projection
on the second eigenvector of the normalized adjacency matrix N . Namely, in Lemma C.2 we
prove that if λ3 < ν then
λ2 > ν − 10γ

and

D 1/2 χ − β2 w2 6
8

44 γ √
2nd,
ν − λ3

where β2 = χ⊺ D 1/2 w2 .

(5)

Now, we can use the above bounds to analyze x(t) = P t x. To begin, note that N =
D −1/2 AD −1/2 and P = D −1 A imply that P = D −1/2 N D 1/2 and P t = D −1/2 N t D 1/2 . Thus,
1/2
for any vector
P2n x, if we write D x as a linear combination of an orthonormal basis of N ,
1/2
D x = i=1 ai wi , we get
t

P x=D

−1/2

t

N D

1/2

x=D

−1/2

2n
X

ai λti wi

=

2n
X

ai λti D −1/2 wi .

i=1

i=1

We next estimate the ﬁrst term, the second term, and the sum of the remaining terms:
w1⊺ D 1/2 x
a1
D 1/2 1
- We have w1 = kD
=
=
1/2 1k , so the ﬁrst term can be written as α1 1 with α1 =
1/2
k D 1k
kD1/2 1k
1⊺ Dx
2.
kD1/2 1k
√
44 γ
- If we write D 1/2 χ = β2 w2 + y, with β2 = w2⊺ D 1/2 χ, (4) implies that kyk 6 ν−λ
2nd. Hence
3
the second term can be written as
!
a2
D 1/2 χ − y
a2 t
t −1/2
t −1/2
λ χ − λt2 z = α2 λt2 χ − α2 λt2 z,
=
a2 λ2 D
w2 = a2 λ2 D
β2
β2 2
β2
where

and

44 γ √
88 γ √
2
2nd =
2n,
kzk = D −1/2 y 6 D −1/2 kyk 6 √ ·
ν − λ3
d ν − λ3

w2⊺ D 1/2 x
.
α2 = a2 /β2 =
w2 D 1/2 χ
- As for all other terms, observe that
(t) 2

ke k =

2n
X

2

ai λti D −1/2 wi

6 D

−1/2

2

2

ai λti wi

i=3

i=3

= D −1/2

2n
X

2

2n
X

−1/2
a2i λ2t
i 6 D

2

λ2t

2n
X

a2i 6 D −1/2

2

λ2t D 1/2 x

2

i=3

i=3

6 D −1/2

2

D 1/2

2

λ2t kxk2 6 16λ2t kxk2 .

The above lemma allows us to generalize our approach to achieve eﬃcient, weak reconstruction
in non-regular clustered graphs. The full proof of the following theorem is given in appendix
C.1.
Theorem 4.3 (Weak reconstruction). Let G be a connected (2n, d, b, γ)-clustered graph with
γ 6 c(ν − λ3 ) for a suitable constant c > 0. If λ < ν and λ2 > (1 + δ)λ for an arbitrarily-small
positive constant δ, the Averaging protocol produces an O(γ 2 /(ν − λ3 )2 )-weak reconstruction
within O(log n) rounds w.h.p.5
Outline of Proof. Lemma 4.2 implies that for every node u at any round t we have
(t−1)
x(t−1) (u) − x(t) (u) = α2 λt−1
(u) − e(t) (u)
2 (1 − λ2 ) (χ(u) + z(u)) + e

Hence, for every node u such that |z(u)| < 1/2,6 we have sgn x(t−1) (u) − x(t) (u) = sgn (α2 χ(u))
whenever
1
(t−1)
α2 λt−1
(6)
(u) − e(t) (u) .
2 (1 − λ2 ) > e
2
5
6

Consistently, Theorem 3.2 is a special case of this one when γ = 0.
The value 1/2 is chosen here only for readability sake, any constant smaller than 1 will do.

9

√
From Lemma 4.2 we have e(t) (u) 6 4λt 2n, thus (4) is satisﬁed for any t such that
!
√
1
16 2n
·
.
t − 1 > log
|α2 |(1 − λ2 )
log (λ2 /λ)
The right-hand side of the above formula is O(log n) w.h.p., because of the following three points:
i) λ2 > (1 + δ)λ by hypothesis; ii) 1 − λ2 > 1/(2n4 ) from Cheeger’s inequality (see e.g. [15])
and the fact that the graph is connected; iii) using similar (although harder - see Lemma B.2)
arguments as in the proof of Theorem 3.2, we can prove that Rademacher initialization of x
−c
w.h.p. implies |α2 | >
Lemma 4.2
√ n for some large enough positive constant c. Finally, from
88 γ
we have kzk 6 ν−λ3 2n. Thus, the number of nodes u with z(u) > 1/2 is O(nγ 2 /(ν −λ3 )2 ).
Roughly speaking, the above theorem states that the quality of block reconstruction depends
on the regularity of the graph (through parameter γ) and conductance within each community
(here represented by the diﬀerence |ν − λ3 |). Interestingly enough, as long as |ν − λ3 | = Θ(1),
the protocol achieves O(γ 2 )-weak reconstruction on (2n, d, b, γ)-clustered graphs.
Stochastic block model. Below we prove that the stochastic block model G2n,p,q satisﬁes the
hypotheses of Theorem 4.3, w.h.p., and, thus, the Averaging protocol eﬃciently produces a
good reconstruction. In what follows, we will often use the following parameters of the model:
expected internal degree a = pn, expected external degree b = qn, and d = a + b.
p
(a + b) logpn then a positive constant δ exLemma 4.4. Let G ∼ G2n,p,q . If a − b >
ists n
such that the following hold
w.h.p.:
i)
G
is
(2n,
d, b, 6 log n/d)-clustered and ii) λ 6
o
p
min λ2 /(1 + δ) , 24 (log n)/d .
Outline of Proof. Claim (i) follows (with probability 1 − n−1 ) from an easy application of
the Chernoﬀ bound. As for Claim (ii), since G is not regular and random, we derive spectral
properties on its adjacency matrix A by considering a “more-tractable” matrix, namely the
expected matrix


B := E [A] =

pJ, qJ
qJ, pJ

where Bi,j is the probability that the edge (i, j) exists in a random graph G ∼ G2n,p,q . In
Lemma D.2 we will prove that such a G is likely to have an adjacency matrix A close to B in
spectral norm. Then, in Lemma D.3 we will show that every clustered graph whose adjacency
matrix is close to B has the properties required in the analysis of the Averaging dynamics,
thus getting Claim (ii).
By combining Lemma 4.4 and Theorem 4.3, we achieve weak reconstruction for the stochastic
block model.
√
Corollary 4.5. Let G ∼ G2n,p,q . If a − b > 25 d log n and b = Ω(log n/n) then the Averaging
protocol produces an O(d log n/(a − b)2 )-weak reconstruction in O(log n) rounds w.h.p.
Outline
of Proof. From Lemma 4.4 we get that w.h.p. G is (2n, d, b, γ)-clustered with γ 6
p
6 log n/d, |λi | 6 4γ for all i = 3, . . . , 2n and λ2 > (1 + δ)λ3 for some constant δ > 0. Given
the hypotheses on√a and b, we also have that the graph is connected w.h.p. Moreover, since
dν = (a − b) > 25 d log n, then
√
√

γ
dγ
6 d log n
d log n
√
=O
=
6
.
ν − λ3
dν − dλ3
(a − b)
(a − b) − 24 d log n

Theorem 4.3 then guarantees that the Averaging protocol ﬁnds an O d log n/(a − b)2 -weak
reconstruction w.h.p.
10

4.1

Tight analysis for the stochastic block model

p
In Lemma 4.4 we have shown that, when (a − b) > (a + b) log n, a graph sampled according
to G2n,p,q satisﬁes the hypothesis of Theorem 4.3 w.h.p.: The simple Averaging protocol thus
gets weak-reconstruction in O(log n) rounds. √
As for the parameters’ range of G2n,p,q , p
we know
that the above result is still oﬀ by a factor log n from the threshold (a − b) > 2 (a + b)
[44, 40, 45], the latter being a necessary condition for any (centralized or not) non-trivial weak
reconstruction. Essentially, the reason behind this gap is that, while Theorem 4.3 holds for any
(i.e. “worst-case”) (2n, d, b, γ)-clustered graph, in order to apply it to G2n,p,q we need to choose
parameters a and b in a way that γd bounds the variation of the degree of any node w.r.t. the
regular case w.h.p.
On the other hand, since the degrees in G2n,p,q are distributed according to a sum of Bernoulli
random variables, the rare event that some degrees are much higher than the average does not
aﬀect too much the eigenvalues and eigenvectors of the graph. Indeed, by adopting ad-hoc
arguments for G2n,p,q , we prove that the Averaging protocol actually achieves an O(d/(a−b)2 )weak reconstruction w.h.p., provided that (a − b)2 > c1 (a + b) > 5 log n, thus matching the
weak-reconstruction threshold up to a constant factor for graphs of logarithmic degree. The
main argument relies on the spectral properties of G2n,p,q stated in the following lemma, whose
complete proof is given in Appendix D.
1

Lemma 4.6. Let G ∼ G2n,p,q . If (a − b)2 > c1 (a + b) > 5 log n and6 a + b < n 3 −c5 for some
positive constants c1 and c5 , then the following claims hold w.h.p.:
√
1. λ2 > 1 − 2b/d − c2 / d for some constant c2 > 0,
2. λ2 > (1 + δ)λ for some constant δ > 0 (where as usual λ = max{|λ3 |, . . . , |λ2n |}),
√
1
3. | 2nd(D −1/2 w2 )(i) − χ(i)| 6 100
for each i ∈ V \ S, for some subset S with |S| =
O(nd/(a − b)2 ).
Idea of the proof. The key-steps of the proof are two probability-concentration results. In
Lemma D.5, we prove a tight bound on the deviation of the Laplacian L(A) = I − N of G2n,p,q
from the Laplacian of the expected matrix L(B) = I − d1 B. As one may expect from previous
results on the Erdős-Rényi model and from Le and Vershynin’s recent concentration results√for
inhomogeneous Erdős-Rényi graph (see [37]), we can prove that w.h.p. kL(A)−L(B)k = O( d),
even when d = Θ(log n). To derive the latter result, we leverage on the aforementioned Le and
Vershynin’s bound on the spectral norm of inhomogeneous √
Erdős-Rényi graphs; in G2n,p,q this
bound implies that if d = Ω(log n) then w.h.p. kA−Bk = O( d). Then, while Le and Vershynin
replace the Laplacian matrix with regularized versions of it, we are able to bound kL(A)−L(B)k
directly by upper bounding it with kA − Bk and an additional factor kB − d−1 D 1/2 BD 1/2 k. We
then bound from aboveP
the√latter√additional factorP
thanks to our second result: In Lemma D.6,
2
we prove that w.h.p.
( di − d) 6 2n and (di − d)2 6 2nd. We can then prove the
ﬁrst two claims of Lemma 4.6 by bounding the distance of the eigenvalues of N from those of
d−1 B via Lemma A.5. As for the third claim of the lemma, we prove it by upper bounding
the components of D −1/2 w orthogonal to χ. In particular, we can limit the projection w1 of
D −1/2 w on 1 by using Lemma D.6. Then, we can upper bound the projection w⊥ of D −1/2 w
on the space orthogonal to both χ and 1 with Lemma D.5: We look at N as a perturbed
version of B and apply the Davis-Kahan theorem. Finally, we conclude the proof observing that
kw2 − (2n)−1/2 k 6 2(kw1 k + kw⊥ k).
Once we have Lemma 4.6 we can prove the main theorem on G2n,p,q with the same argument
used for Theorem 4.3 (the full proof is given in Appendix D).

11

1

Theorem 4.7. Let G ∼ G2n,p,q . If (a − b)2 > c1 (a + b) > 5 log n and7 a + b < n 3 −c5 for
some positive constants c1 and c5 , then the Averaging protocol produces an O(d/(a − b)2 )-weak
reconstruction within O(log n) rounds w.h.p.

5

Moving beyond two communities: An outlook

The Averaging protocol can be naturally extended to address the case of more communities.
One way to achieve this is by performing a suitable number of independent, parallel runs of the
protocol. We next outline the analysis for a natural generalization of the regular block model.
This allows us to easily present the main ideas and to provide an intuition of how and why the
protocol works.
Let G = (V, E) be a d-regular graph in which V is partitioned into k equal-size communities
V1 , . . . , Vk , while every node in Vi has exactly a neighbors within Vi and exactly b neighbors in
each Vj , for j 6= i. Note that d = a + (k − 1) · b. It is easy to see that the transition matrix P
of the random walk on G has an eigenvalue (a − b)/d with multiplicity k − 1. The eigenspace
of (a − b)/d consists of all stepwise vectors that are constant within each community Vi and
whose entries sum to zero. If max{|λ2n |, λk+1 } < (1 − ε) · (a − b)/d, P has eigenvalues λ1 = 1,
λ2 = · · · = λk = (a − b)/d, with all other eigenvalues strictly smaller by a (1 − ε) factor.
Let T be a large enough threshold such that, for all t > T , λt2 > n2 λtk+1 and note that T is
in the order of (1/ε) log n. Let x ∈ RV be a vector. We say that a vertex v is of negative type
with respect to x if, for all t > T , the value (P t x)v decreases with t. We say that a vertex v is
of positive type with respect to x if, for all t > T , the value (P t x)v increases with t. Note that
a vertex might have neither type, because (P t x)v might not be strictly monotone in t for all
t > T.
In Appendix E we prove the following: If we pick ℓ random vectors x1 , . . . , xℓ , each in
{−1, 1}V then, with high probability, i) every vertex is either of positive or negative type for
each xi ;8 ii) furthermore, if we associate a “signature” to each vertex, namely, the sequence of
ℓ types, then vertices within the same Vi exhibit the same signature, while vertices in diﬀerent
Vi , Vj have diﬀerent signatures. These are the basic intuitions that allow us to prove the following
theorem.
Theorem 5.1 (More communities). Let G = (V, E) be a k-clustered d-regular graph defined as
above and assume that λ = max{|λ2n |, λk+1 } < (1 − ε) a−b
d , for a suitable constant ε > 0. Then,
for ℓ = Θ(log n), the Averaging protocol with ℓ parallel runs produces a strong reconstruction
within O(log n) rounds, w.h.p.

References
[1] Emmanuel Abbe, Afonso S Bandeira, and Georgina Hall. Exact recovery in the stochastic
block model. IEEE Trans. on Information Theory, 62(1):471–487, 2014.
[2] Emmanuel Abbe and Colin Sandon. Detection in the stochastic block model with multiple
clusters: proof of the achievability conjectures, acyclic bp, and the information-computation
gap. arXiv preprint arXiv:1512.09080, 2015.
[3] Yehuda Afek, Noga Alon, Omer Barad, Eran Hornstein, Naama Barkai, and Ziv BarJoseph. A biological solution to a fundamental distributed computing problem. science,
331(6014):183–185, 2011.
7

1

It should be possible to weaken the condition d < n 3 −c5 via some stronger concentration argument; see the
proof of Lemma D.6 in Appendix D.5 for details.
8
I.e., for every t > T , (P t x)v monotonically increases (or decreases) with t.

12

[4] Dana Angluin, James Aspnes, and David Eisenstat. A Simple Population Protocol for Fast
Robust Approximate Majority. Distributed Computing, 21(2):87–102, 2008. (Preliminary
version in DISC’07).
[5] Tuncer Can Aysal, Mehmet Ercan Yildiz, Anand D Sarwate, and Anna Scaglione. Broadcast
gossip algorithms for consensus. Signal Processing, IEEE Transactions on, 57(7):2748–2761,
2009.
[6] Michael J Barber and John W Clark. Detecting network communities by propagating labels
under constraints. Physical Review E, 80(2):026129, 2009.
[7] Florence Bénézit, Patrick Thiran, and Martin Vetterli. Interval consensus: from quantized
gossip to voting. In Proc. of the 34th IEEE Int. Conf. on Acoustics, Speech and Signal
Processing (ICASSP ’09), pages 3661–3664, 2009.
[8] Ravi B Boppana. Eigenvalues and graph bisection: An average-case analysis. In Proc. of the
28th Ann. IEEE Symp. on Foundations of Computer Science (FOCS’87), pages 280–285.
IEEE, 1987.
[9] Charles Bordenave. Personal communication, 2015.
[10] Charles Bordenave. A new proof of Friedman’s second eigenvalue Theorem and its extension
to random lifts. arXiv preprint arXiv:1502.04482, 2015.
[11] Charles Bordenave, Marc Lelarge, and Laurent Massoulié. Non-backtracking spectrum
of random graphs: community detection and non-regular ramanujan graphs. In Proc. of
56rd Ann. IEEE Symp. on Foundations of Computer Science (FOCS’15), pages 1347–1357.
IEEE, 2015.
[12] Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip
algorithms. IEEE/ACM Transactions on Networking (TON), 14:2508–2530, 2006.
[13] Gerandy Brito, Ioana Dumitriu, Shirshendu Ganguly, Christopher Hoﬀman, and Linh V.
Tran. Recovery and rigidity in a regular stochastic block model. In Proc. of the 26th Ann.
ACM-SIAM Symp. on Discrete Algorithms (SODA’15), pages 371–390, 2015.
[14] Luca Cardelli and Attila Csikász-Nagy. The Cell Cycle Switch Computes Approximate
Majority. Scientific Reports, Vol. 2(656), 2012.
[15] F. R. K. Chung. Laplacians of graphs and Cheeger’s inequalities. In Combinatorics, Paul
Erdös is eighty, volume 2, pages 157–172. János Bolyai Math. Soc., 1996.
[16] Amin Coja-Oghlan. Spectral techniques, semidefinite programs, and random graphs. Habilitation thesis, Humboldt University Berlin, 2005.
[17] Amin Coja-Oghlan. Graph partitioning via adaptive spectral techniques. Combinatorics,
Probability and Computing, 19(02):227–284, 2010.
[18] Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová. Asymptotic
analysis of the stochastic block model for modular networks and its algorithmic applications.
Physical Review E, 84(6):066106, 2011.
[19] Morris H DeGroot. Reaching a consensus. Journal of the American Statistical Association,
69(345):118–121, 1974.
[20] David Doty. Timing in chemical reaction networks. In Proc. of 25th Ann. ACM-SIAM
Symp. on Discrete Algorithms (SODA’14), pages 772–784. SIAM, 2014.
13

[21] Martin E. Dyer and Alan M. Frieze. The solution of some random NP-hard problems in
polynomial expected time. Journal of Algorithms, 10(4):451–489, 1989.
[22] David Easley and Jon Kleinberg. Networks, crowds, and markets: Reasoning about a highly
connected world. Cambridge University Press, 2010.
[23] Nigel R. Franks, Stephen C. Pratt, Eamonn B. Mallon, Nicholas F. Britton, and David J.T.
Sumpter. Information ﬂow, opinion polling and collective intelligence in house–hunting
social insects. Philosophical Transactions of the Royal Society of London B: Biological
Sciences, 357(1427):1567–1583, 2002.
[24] Noah E. Friedkin and Eugene C. Johnsen. Social inﬂuence and opinions. The Journal of
Mathematical Sociology, 15(3-4):193–206, 1990.
[25] Joel Friedman and David-Emmanuel Kohler. The relativized second eigenvalue conjecture
of alon. arXiv preprint arXiv:1403.3462, 2014.
[26] Yehuda Hassin and David Peleg. Distributed probabilistic polling and applications to proportionate agreement. Information and Computation, 171(2):248–268, 2001.
[27] Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109–137, 1983.
[28] Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications.
Bulletin of the American Mathematical Society, 43(4):439–561, 2006.
[29] Ori Gurel-Gurevich (http://mathoverﬂow.net/users/1061/ori-gurel gurevich). Expectation
of square root of binomial r.v. MathOverﬂow. URL:http://mathoverﬂow.net/q/121424
(version: 2013-02-10).
[30] Mark Jerrum and Gregory B. Sorkin. The metropolis algorithm for graph bisection. Discrete
Applied Mathematics, 82(1):155–175, 1998.
[31] David Kempe, Alin Dobra, and Johannes Gehrke. Gossip-based computation of aggregate
information. In Proc. of 43rd Ann. IEEE Symp. on Foundations of Computer Science
(FOCS’03), pages 482–491, 2003.
[32] David Kempe and Frank McSherry. A decentralized algorithm for spectral analysis. In
Proc. of the 36th Ann. ACM Symp. on Theory of Computing (STOC’04), pages 561–568,
2004.
[33] Jon M Kleinberg. Authoritative sources in a hyperlinked environment. Journal of the ACM,
46(5):604–632, 1999.
[34] Kishore Kothapalli, Sriram V Pemmaraju, and Vivek Sardeshmukh. On the analysis of a
label propagation algorithm for community detection. In Proc. of the 14th Int. Conf. on
Distributed Computing and Networking (ICDCN’13), pages 255–269, 2013.
[35] Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborová, and Pan Zhang. Spectral redemption in clustering sparse networks. Proceedings of
the National Academy of Sciences, 110(52):20935–20940, 2013.
[36] Cornelius Lanczos. An iteration method for the solution of the eigenvalue problem of linear
differential and integral operators. United States Governm. Press Oﬃce Los Angeles, CA,
1950.
[37] Can M. Le and Roman Vershynin. Concentration and regularization of random graphs.
arXiv:1506.00669 [cs, math, stat], 2015. arXiv: 1506.00669.
14

[38] Xin Liu and Tsuyoshi Murata. Advanced modularity-specialized label propagation algorithm for detecting communities in networks. Physica A: Statistical Mechanics and its
Applications, 389(7):1493–1500, 2010.
[39] David JC MacKay. Information theory, inference and learning algorithms. Cambridge
university press, 2003.
[40] Laurent Massoulie. Community Detection Thresholds and the Weak Ramanujan Property.
In Proc. of the 46th Ann. ACM Symp. on Theory of Computing (STOC’14), pages 694–703,
2014.
[41] Frank McSherry. Spectral partitioning of random graphs. In Proc. of the 42nd IEEE Symp.
on Foundations of Computer Science (FOCS’01), pages 529–537, 2001.
[42] Yves Métivier, John Michael Robson, Nasser Saheb-Djahromi, and Akka Zemmari. An
optimal bit complexity randomized distributed mis algorithm. Distributed Computing, 23(56):331–340, 2011.
[43] Joris M Mooij and Hilbert J Kappen. Suﬃcient conditions for convergence of the sum–
product algorithm. IEEE Transactions on Information Theory, 53(12):4422–4437, 2007.
[44] Elchanan Mossel, Joe Neeman, and Allan Sly. A proof of the block model threshold conjecture. arXiv preprint arXiv:1311.4115, 2013.
[45] Elchanan Mossel, Joe Neeman, and Allan Sly. Reconstruction and estimation in the planted
partition model. Probability Theory and Related Fields, 162(3-4):431–461, 2014.
[46] Elchanan Mossel, Joe Neeman, and Omer Tamuz. Majority dynamics and aggregation of
information in social networks. Autonomous Agents and Multi-Agent Systems, 28(3):408–
429, 2014.
[47] Alex Olshevsky and John N Tsitsiklis. Convergence speed in distributed consensus and
averaging. SIAM Journal on Control and Optimization, 48(1):33–55, 2009.
[48] Usha Nandini Raghavan, Réka Albert, and Soundar Kumara. Near linear time algorithm
to detect community structures in large-scale networks. Physical Review E, 76(3):036106,
2007.
[49] Devavrat Shah. Gossip algorithms. Now Publishers Inc, 2009.
[50] Pete Stewart and Ji-guang Sun. Matrix Perturbation Theory. Academic Press, 1990.
[51] Jukka Suomela. Survey of local algorithms. ACM Comput. Surv., 45(2):24:1–24:40, March
2013.
[52] John Nikolas Tsitsiklis. Problems in decentralized decision making and computation. Technical report, DTIC Document, 1984.
[53] Yair Weiss. Correctness of local probability propagation in graphical models with loops.
Neural computation, 12(1):1–41, 2000.
[54] Lin Xiao, Stephen Boyd, and Seung-Jean Kim. Distributed average consensus with leastmean-square deviation. Journal of Parallel and Distributed Computing, 67(1):33–46, 2007.

15

Appendix
A

Linear algebra toolkit

If M ∈ Rn×n is a real symmetric matrix, then it has n real eigenvalues (counted with repetitions),
λ1 > λ2 > · · · > λn , and we can ﬁnd a corresponding collection of orthonormal real eigenvectors
v1 , . . . , vn such that M vi = λi vi .
P
If x ∈ Rn is any vector, then we can write it as a linear combination x =
i αi vi of
eigenvectors, where the coeﬃcients of the linear combination are αi = hx, vi i. In this notation,
we can see that
X
X
Mx =
λi αi vi , and so M t x =
λti αi vi .
i

i

Lemma A.1 (Cauchy-Schwarz inequality). For any pair of vectors x and y
|hx, yi| 6 kxk · kyk.
Observation A.2. For any matrix A and any vector x
kAxk 6 kAk · kxk,

and

kA · Bk 6 kAk · kBk.

Observation A.3. If G is a (2n, d, b)-clustered regular graph with clusters V1 and V2 and χ =
1V1 − 1V2 is the partition indicator vector, then χ is an eigenvector of the transition matrix P
of G with eigenvalue 1 − 2b/d.
Proof. Every node i has b neighbors j on the opposite side of the partition, for which χ(j) =
−χ(i), and d − b neighbors j on the same side, for which χ(j) = χ(i), so


2b
1
χ(i).
(P χ)i = ((d − b)χ(i) − bχ(i)) = 1 −
d
d
Theorem A.4 (Matrix Bernstein Inequality). Let X1 , . . . , XN be a sequence of independent
n × n symmetric random matrices, such that
PE [X2i] = 0 for every i and such that kXi k 6 L
with probability 1 for every L. Call σ := kE
i Xi k. Then, for every t, we have
!
−t2
X
2 Lt
2σ+ 3
.
P
Xi > t 6 2ne
i

Theorem A.5. (Corollary 4.10 in [50]) Let M1 and M2 be two Hermitian matrices, let λ1 >
λ2 > · · · > λn be the eigenvalues of M1 with multiplicities in non-increasing order, and let
λ′1 > λ′2 > · · · > λ′n be the eigenvalues of M2 with multiplicities in non-increasing order. Then,
for every i,
|λi − λ′i | 6 kM1 − M2 k.
Theorem A.6 (Davis and Kahan, 1970). Let M1 and M2 be two symmetric real matrices, let
x be a unit length eigenvector of M1 of eigenvalue t, and let xp be the projection of x on the
eigenspace of the eigenvectors of M2 corresponding to eigenvalues 6 t − δ. Then
kxp k 6

2
kM1 − M2 k.
δπ

16

B

Length of the projection of x

For the analysis of the Averaging dynamics on both regular and non-regular graphs, it is
important to understand the distribution of the projection of x on 1 and χ, that is (up to
scaling) the distribution of the inner products hx, 1i and hx, χi. In particular we are going to
use the following bound.
Lemma B.1. If we pick x uniformly at random in {−1, 1}2n then, for any δ > 0 and any fixed
vector w ∈ {−1, 1}2n with ±1 entries, it holds


√
P h(1/ 2n) w, xi 6 δ 6 O(δ).

Proof. Since x is a vector of independent and uniformly distributed random variables in {−1, 1},
both hx, χi and hx, 1i have the distribution of a sum
 of 2n Rademacher random variables. Such
a sum takes the value 2k−2n with probability 21n 2n
k , and so every possible value has probability

1 2n
1
√
at most 2n n ≈ 2πn . Consequently, if R is the sum of 2n Rademacher random variables, we
√ 
have P |R| 6 δ 2n 6 O(δ).
Although it is possible to argue that a Rademacher vector has Ω(1) probability of having inner
product Ω(kwk) with every vector w, such a statement does not hold w.h.p. We do have,
however, estimates of the inner product of a vector w with a Rademacher vector x provided
that w is close to a vector in {−1, 1}2n .

Lemma B.2. Let k be a positive integer. For every nk-dimensional vector w such that | {i | |w(i)| > c} | >
n for some positive constant c, if we pick x uniformly at random in {−1, 1}kn , then




√
1
.
P h(1/ kn) w, xi 6 δ 6 O(kδ) + O √
n
Proof. Let S ⊂ {1, . . . , kn} be the set of coordinates i of w such that |w(i)| > c. By hypothesis,
we have |S| > n. Let T := {1, . . . , kn} − S. Now, for every assignment a ∈ {−1, 1}kn , we will
show that


√
P |hw, xi| 6 δ kn | ∀i ∈ T, x(i) = a(i) 6 O(δ),
P
and then the lemma will follow. Call t := i∈T ai zi . We need to show
!
X
√
P |
x(i)w(i) + t| 6 δ kn 6 O(δ).
i∈S

From the Berry-Esseen theorem,
P |

X

√

x(i)w(i) + t| 6 δ kn

i∈S

!




√ 
1
,
6 P |g + t| 6 δ kn + O √
n

P
where g is a Gaussian random variable of mean 0 and variance σ 2 = i∈S (w(i))2 > c2 |S| > c2 n,
so
√
√
Z −t+δ√kn

2
√ 
2kδ
1
2δ kn
− s2
e 2σ ds 6 √
= √ ,
P |g + t| 6 δ kn = √
√
2
2
πc
2σ π −t−δ kn
2πc n

where we used the fact that e−s

2 /2

6 1 for all s.

17

C

Clustered Graphs

Lemma C.1. Assume we run the Averaging dynamics in a (2n, d, b)-clustered regular graph
G (see Definition 3.1) with any initial vector x ∈ {−1, 1}2n . If λ < 1 − 2b/d then there are reals
α1 , α2 such that at every round t we have
x(t) = α1 1 + α2 λt2 χ + e(t)

where

e(t)

∞

√
6 λt 2n .

Proof. Since x(t) = P t x we can write
P tx =

X
i

λti hx, vi ivi ,

where 1 = λ1 > λ2 = 1 − 2b/d > λ3 > · · · > λ2n are the eigenvalues of P and v1 =
v2 =

√1 χ,
2n

√1 1,
2n

v3 , . . . , v2n are a corresponding sequence of orthonormal eigenvectors. Hence,
2n

x(t) =

X
1
1
λti αi vi
hx, 1i · 1 + λt2 hx, χi · χ +
2n
2n
i=3

= α1 1 + α2 λt2 · χ +
where we set α1 =
2n
X
i=3

1
2n h1, xi

λti αi vi

6
∞

and α2 =
2n
X

1
2n hχ, xi.

λti αi vi

i=3

2

2n
X

λti αi vi ,

i=3

We bound the ℓ∞ norm of the last term as

v
v
u 2n
u 2n
uX
uX
√
tt
t
2t
2
=
λi αi 6 λ
α2i = λt kxk = λt 2n.
i=3

i=1

Lemma C.2. Let G be a connected (2n, d, b, γ)-clustered graph (see Definition 4.1) with γ 6
1/10. If λ3 < ν then
λ2 > ν − 10γ

D 1/2 χ − β2 w2 6

and

44 γ √
2nd,
ν − λ3

where β2 = χ⊺ D 1/2 w2 .
Proof. For every node v, let us name av and bv the numbers of neighbors of v in its own cluster
and in the other cluster, respectively, and dv = av + bv its degree. Since from the deﬁnition of
(2n, d, b, γ)-clustered graph it holds that (1 − γ)d 6 dv 6 (1 + γ)d and b − γd 6 bv 6 b + γd, it
is easy to check that
|av − bv − νdv | 6 4d γ
for any node v. Hence,
kAχ − νDχk2 =
=

X

v∈[2n]

X

v∈[2n]

=

X

v∈[2n]




X

w∈Neigh(v)

2

χ(w) − νdv χ(v)

(av χ(v) − bv χ(v) − νdv χ(v))2
(av − bv − νdv )2 6 32nd2 γ 2 .

18

Thus,
N D 1/2 χ − νD 1/2 χ = D −1/2 Aχ − νD 1/2 χ = D −1/2 (Aχ − νDχ)
√
2 √
6 D −1/2 · kAχ − νDχk 6 √ · 2n4d γ = 8 2nd γ.
d

(7)

Observe that w1 is parallel to D 1/2 1 and we have that
|1⊺ Dχ| =

X

v∈[2n]

χ(v)dv 6 (1 + γ)dn − (1 − γ)dn = 2nd γ.

(8)

Hence, if we name y the component of D 1/2 χ orthogonal to the ﬁrst eigenvector, we can write
it as
1⊺ Dχ
D 1/2 χ =
D 1/2 1 + y.
(9)
kD 1/2 1k2
Thus,




1⊺ Dχ
1⊺ Dχ
1/2
1/2
1/2
D 1 −ν D χ−
D 1
kD 1/2 1k2
kD 1/2 1k2
|1⊺ Dχ|
6 N D 1/2 χ − νD 1/2 χ +
N D 1/2 1 − νD 1/2 1
kD 1/2 1k2
|1⊺ Dχ| 2b
= N D 1/2 χ − νD 1/2 χ +
kD 1/2 1k d
√
√
6 8 2nd γ + 4 2nd γ,


kN y − νyk = N D 1/2 χ −

(10)

where in the last inequality we used (C) and (C) and the facts that b 6 d/2 and D 1/2 1 >
√
(1/2) 2nd. From (C) it follows that
kyk > D 1/2 χ −

√
√
√
√
1⊺ Dχ
>
(1
−
γ)
2nd
−
4γ
2nd
=
(1
−
5γ)
2nd
>
(1/2)
2nd.
D 1/2 1

(11)

Now, let us we write y as a linear combination of the orthonormal eigenvectors of N , y =
β2 w2 + · · · + βn wn (recall that y⊺ w1 = 0 by deﬁnition of y in (C)). From (C) and (C), it follows
that
2
n
n
X
X
2
2
2
(λi − ν)2 βi2 .
(12)
(λi − ν)βi wi =
100γ kyk > kN y − νyk =
i=2

i=2

Moreover, from hypothesis λ3 < ν we have that

n
n
n
X
X
X
βi2 = (λ3 − ν)2 ky − β2 w2 k2 .
(λi − ν)2 βi2 > (λ3 − ν)2
(λi − ν)2 βi2 >
i=3

i=3

i=2

(13)

Thus, by combining together (C) and (C) we get
ky − β2 w2 k 6

10 γ
kyk
ν − λ3

⊺
where β2 = y⊺ w2 = D 1/2 χ w2 .
As for the ﬁrst thesis of the lemma, observe that if λ2 > ν then the ﬁrst thesis is obvious.
Otherwise, if λ2 < ν, then (λ2 − ν)2 6 (λ3 − ν)2 6 · · · 6 (λn − ν)2 . Thus, the ﬁrst thesis follows
from (C) and the fact that
n
n
X
X
2 2
2
βi2 = (λ2 − ν)2 kyk2 .
(λi − ν) βi > (λ2 − ν)
i=2

i=2

19

As for the second thesis of the lemma, we have
1⊺ Dχ
D 1/2 1 + y − β2 w2
kD 1/2 1k2
√
|1⊺ Dχ|
10 γ
+ ky − β2 w2 k 6 4 γ 2nd +
kyk
6
1/2
ν − λ3
kD 1k
√
20 γ √
44 γ √
6 4 γ 2nd +
2nd 6
2nd,
ν − λ3
ν − λ3

D 1/2 χ − β2 w2 =

1

1

where in the last inequality we used that y is the projection of D 2 χ on D 2 1, and thus kyk 6
√
1
kD 2 χk 6 2 2nd.

C.1

Proof of Theorem 4.3

From Lemma 4.2 it follows that for every node u at any round t we have
(t−1)
x(t−1) (u) − x(t) (u) = α2 λt−1
(u) − e(t) (u).
2 (1 − λ2 ) (χ(u) + z(u)) + e

Hence, for every node u such that |z(u)| < 1/2 (we choose 1/2 here for readability sake, how
ever any other constant smaller than 1 works as well) it holds that sgn x(t−1) (u) − x(t) (u) =
sgn (α2 χ(u)) whenever
1
(t−1)
α2 λt−1
(u) − e(t) (u) .
2 (1 − λ2 ) > e
2
√
From Lemma 4.2 we have that e(t) (u) 6 4λt 2n, thus (C.1) is satisﬁed for all


√
2n
log |α216|(1−λ
2)
t−1>
.
log (λ2 /λ)

(14)

(15)

The right-hand side in the above formula is O(log n) w.h.p., because of the following three
points:
• From Cheeger’s inequality (see e.g. [15]) and the fact that the graph is connected it follows
that 1 − λ2 > 1/(2n4 );
• λ2 > (1 + δ)λ by hypothesis;
• It holds |α2 | > n−c for some large enough positive constant c w.h.p., as a consequence of
the following equations that we prove below:

 ⊺ 1
√ !




w2 D 2 x
1
2
d
1
1
⊺
1/2
.
P |α2 | 6 c = P 
6 c  6 P w2 D x 6 c−1/2 6 O √ (16)
1
n
n
n
n
w⊺ D 2 χ
2

1

1

In the ﬁrst equality of (C.1) we used that, by deﬁnition, |α2 | = |w2⊺ D 2 x|/|w2⊺ D 2 χ|. In
1
⊺ 1
the
√ ﬁrst inequality we used that, by the Cauchy-Schwarz inequality, |w2 D 2 χ| 6 kD 2 χk 6
2 dn. In order to prove the last inequality of (C.1), we use that from Lemma C.2 it holds
D 1/2 χ − β2 w2

2

= D 1/2 χ

2

+ kβ2 w2 k2 − 2hD 1/2 χ, β2 w2 i 6 2

442 γ 2
nd,
(ν − λ3 )2

that is
hD

1/2

χ, β2 w2 i = hD

1/2

1
χ, w2 i >
2
2

20



D

1/2

2

χ


442 γ 2
nd
−2
nd >
.
2
(ν − λ3 )
3

(17)

Since w2 is normalized the absolute value of its entries is at most 1, which toghether with
(C.1) implies that at least a fraction 12/13 of its entries have an absolute value greater
than 1/12. Thus, we can apply Lemma B.2 and prove the last inequality of (C.1) and,
consequently, the fact that (C.1) is O(log n).
Finally, from Lemma 4.2 we have
kzk 6

88 γ √
2n .
ν − λ3

Thus the number of nodes u with z(u) > 1/2 is O(nγ 2 /(ν − λ3 )2 ).

D
D.1

Stochastic Block Models
Regular stochastic block model

Lemma D.1. Let G be a graph sampled from the regular stochastic block model with internal
and external degrees a and b respectively. W.h.p., it holds that
2 √
λ6
( a + b − 1 + on (1))
a+b
Proof. The lemma follows from the general results of Friedman and Kohler [25], recently simpliﬁed by Bordenave [10]. If G is a multigraph on n vertices, then a random degree k lift of G is
a distribution over graphs G′ on kn vertices sampled as follows: every vertex v of G is replaced
by k vertices v1 , . . . , vk in G′ , every edge (u, v) in G is replaced by a random bipartite matching
between u1 , . . . , uk and v1 , . . . , vk (if there are multiple edges, each edge is replaced by an independently sampled matching) and every self loop over u is replaced by a random degree-2 graph
over u1 , . . . , uk which is sampled by taking a random permutation π : {1, . . . , k} → {1, . . . , k}
and connecting ui to uπ (i) for every i.
For every lift of any d-regular graph, the lifted graph is still d-regular, and every eigenvalue
of the adjacency matrix of the base graph is still an eigenvalue of the lifted graph. Friedman and
Kohler [25] prove that, if d > 3, then with probability 1 − O(1/k) over the choice of a random
lift
√ of degree k, the new eigenvalues of the adjacency matrix of the lifted graph are at most
2 d − 1 + ok (1) in absolute value. Bordenave [10, Corollary 20] has considerably simpliﬁed the
proof of Friedman and Kohler; although he does not explicitly state the probability of the above
event, his argument also bound the failure probability by 1/k Ω(1) [9].
The lemma now follows by observing that the regular stochastic block model is a random
lift of degree n of the graph that has only two vertices v1 and v2 , it has b parallel edges between
v1 and v2 , and it has a/2 self-loops on v1 and a/2 self-loops on v2 .

D.2

Proof of Lemma 4.4

Lemma D.2. If a(n), b(n) are such that d := a + b > log n, then w.h.p. √
(over the choice of
G ∼ G2n, a , b ), if we let A be the adjacency matrix of G, then kA − Bk 6 O( d log n) w.h.p.
n n
P
Proof. We can write A − B as {i,j} X {i,j} , where the matrix X {i,j} is zero in all coordinates
except (i, j) and (j, i), and, in those coordinates,
− B. Then we see that the
 {i,j}  it is equal to A
{i,j}
{i,j}
matrices X
are independent, that E X
= 0, that kX
k 6 1, because every row
containsPat most one non-zero element, and that element is at most 1 in absolute value, and
that E[ {i,j} (X {i,j} )2 ] is the matrix that is zero everywhere except for the diagonal entries (i, i)
2 and B
2
and (j, j), in which we have Bi,i − Bi,i
j,j − Bj,j respectively. It follows that
X
kE[
(X {i,j} )2 ]k 6 d.
{i,j}

21

Putting these facts together,
and applying the Matrix Bernstein Inequality (see Theorem A.4 in
√
Appendix A) with t = 6d log n, we have
9d log n


p
−
9d log n
2√
P kA − Bk > 9d log n 6 2ne 2d+ 3 9d log n 6 2ne− 4d 6 2n−1 ,

where we used d > log n.

Lemma D.3. Let G be a (2n, d, b, γ)-clustered graph such that ν = 1 − 2b
d > 12γ and such that
its adjacency matrix A satisfies kA − Bk 6 γd. Then for every i ∈ {3, . . . , 2n}, |λi | 6 4γ and
λ2 > (1 + δ)λ3 for some constant δ > 0.
Proof. The matrix B has a very simple spectral structure: 1 is an eigenvector of eigenvalue d, χ
is an eigenvector of eigenvalue a − b, and all vectors orthogonal to 1 and to χ are eigenvectors of
eigenvalue 0. In order to understand the eigenvalues and eigenvectors of N , and hence the eigenvalues and eigenvectors of P , we ﬁrst prove that A approximates B and that N approximates
(1/d)A, namely kdN − Ak 6 3γd.
To show that dN approximates A we need to show that D approximates dI. The condition
on the degrees immediately gives
has degree
√ d
√i in the√range
√ us kD−dIk 6 γd. Since every vertex √
d ± γd, then the square root di of each vertex must be in the range [ d − γ d, d + γ d], so
we also have the spectral bound:
√
√
kD 1/2 − dIk 6 γ d.
(18)
We know that kDk 6 d + γd < 2d and that kN k = 1, so from (D.2) we get
kA − dN k = kD 1/2 N D 1/2 − dN k
√
√
6 kD 1/2 N D 1/2 − dN D 1/2 k + k dN D 1/2 − dN k
√
√
√
= k(D 1/2 − dI) · N D 1/2 k + k dN · (D 1/2 − dI)k
√
√
√
6 kD 1/2 − dIk · kN k · kD 1/2 k + d · kN k · kD 1/2 − dIk 6 3γd.

(19)

By using the triangle inequality and (D.2) we get
kN − (1/d)Bk 6 kN − (1/d)Ak + (1/d) · kA − Bk 6 4γ.

(20)

Finally, we use Theorem A.5 (See Appendix A), which is a standard fact in matrix approximation
theory: if two real symmetric matrices are close in spectral norm then their eigenvalues are close.
From (D.2) and the fact that all eigenvalues of (1/d)B except for the ﬁrst and second one are
0, for each i ∈ {3, . . . , 2n} we have
1
|λi | = |λi − 0| 6 kN − Bk 6 4γ.
d

(21)

Similarly, from the fact that the second eigenvalue of (1/d)B is 1 − 2b/d we get
1
|λ2 − (1 − 2b/d)| 6 kN − Bk 6 4γ,
d
that is, from hypothesis ν > 12γ and (D.2), λ2 > (1 + δ)λ3 for some constant δ > 0. This
concludes the proofs of Lemma D.3 and Theorem 4.4.

22

D.3

Proof of Lemma 4.6

Let G be a randomly-generated graph according to G2n,p,q with a = pn, b = qn and d = a + b.
Recall the deﬁnitions of A, D, N , P , λi and wi (i ∈ {1, . . . , 2n}) in Section 2, and let B be
deﬁned as in Section D.2. Let us denote with Ai (i ∈ {1, 2}) the adjacency matrix of the
subgraph of G induced by community Vi , with AB = {Au,v−n }u∈V1 ,v∈V2 the matrix whose entry
(i, j) is 1 iﬀ there is an edge between the i-th node of V1 and the j-th node of V2 , then


A1 AB
.
A=
A⊺B A2
We need the following technical lemmas.
√
Lemma D.4. If d > 5 log n then for some positive constant c3 it holds kA − Bk 6 c3 d w.h.p.
Proof. The lemma directly follows from Theorem 2.1 in [37] with d′ = 2d and the observation
that, from the Chernoﬀ bounds, all degrees are smaller than 2d w.h.p.
Lemma D.5. If d > 5 log n then for some constant c4 > 0 it holds w.h.p.
√
kdN − Bk 6 c4 d.
The idea for proving Lemma D.5 is to use the triangle inequality to upper bound kdN − Bk
in terms of kA − Bk, which we can bound
with Lemma D.4,
and kB − 1/dD 1/2 BD 1/2 k, which
√
√
we can upper bound by bounding k d1 − D 1/2 1k and k dχ − D 1/2 χk where 1 and χ are
the eigenvector corresponding to the only two non-zero eigenvalues of B. The
proof
√ complete
1/2 1k =
d1
−
D
of√Lemma D.5 is deferred
to
Section
D.4.
As
for
the
required
bound
on
k
√
p
P
k dχ − D 1/2 χk = j∈V | d − dj |2 , we provide it in the following lemma, whose proof is also
deferred to Section D.5.
1

Lemma D.6. If 5 log n < d < n 3 −c5 for any constant c5 > 0, it holds w.h.p.
X √
p
| d − dj |2 6 2n and
j∈V

X

j∈V

|d − dj |2 6 2dn.

√
By combining Lemma D.5 and Theorem A.5 we have |λi − λ′i | 6 kN − d−1 Bk = O(1/ d), where
λ′1 = 1, λ′2 = 1 − 2b/d and λ′i = 0 for i ∈ {3, . . . , 2n} are the eigenvalues of d−1 B. This proves
the ﬁrst two part of Lemma 4.6.
As for the third part, let us write w2 = w1 + wχ + w⊥ where w1 and wχ are the projection
of w2 on 1 and χ respectively, and w⊥ is the projection of w2 on the space orthogonal to 1 and
χ.
Observe that the only non-zero eigenvalues of (1/d)B are 1 and (a−b)/d. Thus, from Lemma
D.5 and the Davis-Kahan theorem (Theorem A.6) with M1 = N , M2 = d1 B, t = λ2 , x = w2
and δ = λ2 /2, we get
√ !


1
4
1
d
=O
kw⊥ k 6
N− B 6O √
.
(22)
λ2 π
d
a
−
b
dλ2
As for w1 , we know that hw2 , D −1/2 1i = 0, thus
1
1
1
1
1
1
1
kw1 k = √ hw2 , 1 − d− 2 D 2 1i 6 √ kw2 kk1 − d− 2 D 2 1k 6 √ ,
2n
2n
d

23

(23)

where in the last inequality we used Lemma√D.6.
By the law of cosines and the fact that 1 − x > 1 − x for x ∈ [0, 1] we have that
1
w2 − √ χ
2n

2

2
1
1
= kw2 k2 + √ χ − 2hw2 , √ χi = 2 − 2kwχ k
2n
2n

p

= 2 − 2 1 − kw1 k2 + kw⊥ k2 6 2 kw1 k2 + kw⊥ k2 = O

(24)
d
(a − b)2



,

where in the last inequality we used (D.3) and (D.3). (D.3) implies that, with the exception of
a set S of at most O(nd/(a − b)2 ) nodes, we have
√

2nw2 (i) − χ(i) 6

1
,
201

for each i ∈ V /S. From the Chernoﬀ bound, we also have that w.h.p.
Thus, (D.3) and the last fact imply that for each i ∈ V /S it holds w.h.p.
√

1

2ndD − 2 w2 (i) − χ(i) 6

(25)
p

d/di = 1 ± 1/201.

1
,
100

concluding the proof.
Remark 1. After looking at Lemma 4.6, one may wonder whether it could be enough to generalize
Deﬁnition 4.1 to include “quasi-(2n, d, b, γ)-clustered graph”, i.e. graphs that are (2n, d, b, γ)clustered except for a small number of nodes which may have a much higher degree. In fact,
this would be rather surprising: This higher-degree nodes may connect to the other nodes in
such a way that would greatly perturb the eigenvalues and eigenvectors of the graph. In G2n,p,q ,
besides the fact that the nodes with degree much larger than d are few, it is also crucial that
they are connected in a non-adversarial way, i.e. randomly.

D.4

Proof of Lemma D.5

A simple application of the Chernoﬀ bound and the union bound shows that w.h.p.
!
r
√
log
n
dkD −1/2 k 6 1 + O
,
d

(26)

hence
√
√
kdN − Bk = k( dD −1/2 )A( dD −1/2 ) − Bk
√
√
1
1
6 k dD −1/2 k A − √ D 1/2 B √ D 1/2 k dD −1/2 k
d
d
√
1 1/2
6 A − D BD 1/2 k dD −1/2 k2
d
!!
r


1 1/2
log n
1/2
6 kA − Bk + B − D BD
1+O
.
d
d

(27)

√
d). Hence, in order to conclude the proof, it
Thanks to Lemma D.4, it holds kA − Bk = O( √
−1
1/2
1/2
remains to show that kB − d D BD k = O( d). We do that by observing that
1
1
1
1
B − D 1/2 BD 1/2 6 B − √ BD 1/2 + √ BD 1/2 − D 1/2 BD 1/2 ,
d
d
d
d

24

(28)

and by upper-bounding the two terms on the right hand side. The two only non-zero eigenvalues
of B are a + b and a − b, with corresponding eigenvectors (2n)−1/2 1 and (2n)−1/2 χ, therefore
we can write B = d/(2n) 11⊺ + (a − b)/(2n) χχ⊺ , which implies that
√
√
d √
a−b
1
1/2
1 ( d 1 − D 1/2 1)⊺ + √
B − √ BD
=
χ ( d χ − D 1/2 χ)⊺ .
2n
d
d 2n
It follows that, for an arbitrary unitary vector x it holds
√


√
d √
a−b
1
1/2
1 ( d 1 − D 1/2 1)⊺ x + √
χ ( d χ − D 1/2 χ)⊺ x
(29)
x 6
B − √ BD
2n
d
d 2n
√
√
√
d
a−b
k1k |( d 1 − D 1/2 1)⊺ x| + √
=
kχk |( d χ − D 1/2 χ)⊺ x|
2n
d 2n
√
√
√
d
a−b √
d 1 − D 1/2 1 · kxk + √
d χ − D 1/2 χ · kxk 6 2 d,
6√
2n
2dn
√
where we used the triangle inequality, the fact that k1k = kχk = 2n, the Cauchy-Schwartz
inequality, Lemma D.6 and a − b < d. As for the other term on the r.h.s. of (D.4), we have that
w.h.p.
!!
r
√
log n
1 1/2
1
1
1 1/2
1/2
1/2
1/2
√ BD − D BD
6 B − √ D B √ kD k 6 2 d 1 + O
(30)
,
d
d
d
d
d
where in the last inequality we used (D.4) and that for any matrix M it holds kM k = kM ⊺ k.
Finally, (D.4) and (D.4) togheter implies the desired upper bound on (D.4) and thus (D.4),
concluding the proof.

D.5

Proof of Lemma D.6

Each degree di has the distribution of a sum of n Bernoulli random variables of expectation p
plus a sum of n Bernoulli random variables of expectation q. Thus, each di satisﬁes E [di ] = d
and Var (di ) 6 d.


First, we consider the random variables |d − dj |2 . Their expectation is E |d − dj |2 6 d
(the variance of the random variable dj ). Let eu,v is the variable that is 1 iﬀ the edge (u, v) is
included in the graph. Observe that
X
X
X
|d − dj |4 = |d −
ej,v |4 = |a −
ej,v + b −
ej,v |4
v∈V

= |a −

X

v∈Vi

v∈Vi

ej,v |4 + |b −

+ 4(a −

X

v∈Vi

v∈V3−i

X

v∈V3−i

ej,v ) (b −

ej,v |4 + 6|a −

X

v∈V3−i

X

v∈Vi

ej,v )3 + 4(a −

ej,v |2 |b −

X

v∈Vi

X

v∈V3−i

ej,v )3 (b −

ej,v |2

X

ej,v ),

v∈V3−i

and


E (a −


X

v∈Vi

E (a −

ej,v )3 (b −
X

v∈Vi

X

v∈V3−i

ej,v )(b −





ej,v ) = E (a −

X

v∈V3−i





X

v∈Vi

ej,v )3  = E (a −
25





ej,v )3  E (b −
X

v∈Vi





X

v∈V3−i

ej,v ) E (b −



ej,v ) = 0,

X

v∈V3−i



ej,v )3  .

Hence, since the fourth central moment of a binomial with parameters n and p is np(1 − p)4 +
np4 (1 − p) + 3n(n − 1)p2 (1 − p)2 6 4(np)2 , if we let i ∈ {1, 2} be the index of the community of
j we have that the expectation of the square of |d − dj |2 (which is the fourth central moment of
dj ) is




X
X


E |d − dj |4 = E |a −
ej,v |4  + E |b −
ej,v |4 
v∈Vi



v∈V3−i

X

+ 6E |a −

v∈Vi





ej,v |2  E |b −

X

v∈V3−i



ej,v |2  6 4a2 + 4b2 + 6ab 6 4d2 .

P
In order to apply Chebyshev’s inequality, we need to bound the variance of j |d − dj |2 . As for
the second moment of their sum, we have
X
X
X
E[(
|d − dj |2 )2 ] =
E[|d − dj |4 ] + 2
E[|d − di |2 · |d − dj |2 ]
i

i

16i<j62n

2

6 8d n + 2

X

16i<j62n

E[|d − di |2 · |d − dj |2 ].

(31)

To upper bound the terms E[|d − di |2 · |d − dj |2 ], since the stochastic dependency between di
and dj is due only to the edge (i, j), let us write
di =

X

u∈N (i)
(j)

where di

X

ei,u = ei,j +

(j)

ei,u = ei,j + di ,

u∈N (i)/{j}

is the sum of all the edges incident to i except for (i, j). We have
(j)

(i)

|d − di |2 · |d − dj |2 = |d − di + ei,j |2 · |d − dj + ei,j |2

(32)

(j)
(j)
(i)
(i)
=(|d − di |2 + ei,j + 2ei,j (d − di ))(|d − dj |2 + ei,j + 2ei,j (d − dj ))
(j)
(i)
(i)
(j)
(i)
= |d − di |2 |d − dj |2 + ei,j |d − dj |2 + 2ei,j (d − di )|d − dj |2
(j)
(j)
+ |d − di |2 ei,j + ei,j + 2ei,j (d − di )
(i)
(j)
(i)
(j)
(i)
+ 2ei,j (d − dj )|d − di |2 + 2ei,j (d − dj ) + 4ei,j (d − di )(d − dj ),

where we used that, since ei,j is an indicator variable, it holds e2i,j = ei,j . Taking the expectation
of (D.5) we thus get
E[|d − di |2 · |d − dj |2 ]
(j)

(i)

(i)

(j)

(i)

= E[|d − di |2 |d − dj |2 + ei,j |d − dj |2 + 2ei,j (d − di )|d − dj |2
(j)

(j)

+ |d − di |2 ei,j + ei,j + 2ei,j (d − di )
(i)

(j)

(i)

(j)

(i)

+ 2ei,j (d − dj )|d − di |2 + 2ei,j (d − dj ) + 4ei,j (d − di )(d − dj )]
(j)

(i)

(i)

(j)

(i)

= E[|d − di |2 ]E[|d − dj |2 ] + E[ei,j ]E[|d − dj |2 ] + 2E[ei,j ]E[(d − di )]E[|d − dj |2 ]
(j)

(j)

+ E[ei,j ]E[|d − di |2 ] + E[ei,j ] + 2E[ei,j ]E[(d − di )]
(i)

(j)

(j)

(i)

(i)

+ 2E[ei,j ]E[(d − dj )]E[|d − di |2 ] + 2E[ei,j ]E[(d − dj )]

+ 4E[ei,j ]E[(d − di )]E[(d − dj )]
(j)

(i)

6 E[|d − di |2 ]E[|d − dj |2 ] +

d3
d2
d
d2
d3
d2
d3
d2
+2 2 +
+ +2 2 +2 2 +2 2 +4 3
n
n
n
n
n
n
n
n
26

(j)

(i)

6 E[|d − di |2 ]E[|d − dj |2 ] + 15

d2
,
n

(33)

where in the inequalities we used that E[ei,j ] 6 d/n, that
(j)

(j)

X

E[d − di ] 6 E[ei,j ] + E[

E[ei,u ] − di ] 6

u∈N (i)/{j}

and that
(j)

(j)

E[|d − di |2 ] 6 E[ei,j ] + E[|d − E[ei,j ] − di |2 ] 6
By combining (D.5) and (D.5) we get
X
E[(
|d − dj |2 )2 ] 6 8d2 n + 2
i

d
+ d − 1 6 d.
n

(j)

X

16i<j62n

d
,
n

(34)

(i)

E[|d − di |2 ]E[|d − dj |2 ] + 60d2 n,

(35)

As for the square of the average, we have
X
X
X
(E[
|d − di |2 ])2 =
E[|d − di |2 ]2 + 2
E[|d − di |2 ]E[|d − dj |2 ]
i

i

i6=j

X

>2

2

16i<j62n

E[|d − di | ]E[|d − dj |2 ],

and
E[|d − di |2 ]E[|d − dj |2 ]

(i)

(j)

= E[|d − di − ei,j |2 ]E[|d − dj − ei,j |2 ]

(i)

(j)

(j)

= (E[|d − di |2 ] + E[ei,j ] − 2E[ei,j ]E[(d − di )]) · (E[|d − dj |2 ]
(i)

+ E[ei,j ] − 2E[ei,j ]E[(d − dj )])

(i)

(i)

(j)

(j)

> (E[|d − di |2 ] − 2E[ei,j ]E[(d − di )]) · (E[|d − dj |2 ] − 2E[ei,j ]E[(d − dj )])
(j)

(i)

> E[|d − di |2 ]E[|d − dj |2 ] − 4

d3
,
n2

(36)
(j)

where we used, again, that E[ei,j ] 6 d/n and that E[|d − di |2 ] 6 d (see (D.5)).
Combining (D.5) and (D.5) together we get
X
X
X
Var[
|d − di |2 ] = E[(
|d − di |2 )2 ] − E[
|d − di |2 ]2
i

i

i

2

2

3

6 8d n + 60d n + 16d = 84d2 n

Finally, by Chebyshev’s inequality we have


X
21
,
P 
|d − dj |2 > 2dn 6
n
j

which proves the second part of the lemma. √
p
We now consider the sum of the variables | d − dj |2 . We have
X
X
X √
√ Xp
p
d+
di − 2 d ·
| d − dj |2 =
dj
j∈V

i∈V

i∈V

6 2dn +

X
i∈V

27

j∈V

√ Xp
di − 2 d ·
dj .
j∈V

(37)

From the Chernoﬀ bound we have that for some positive constant c6 it holds w.h.p.
X
X
X
p
2eu,v +
eu,v 6 2dn + c6 dn log n 6 4dn + n,
dj =
j∈V

u∈V

u,v∈V
u6=v

where we are using the hypothesis d = o(n/ log n). We will now prove that
Xp
√
n
dj > 2n d − √ ,
d
j∈V
which together with (D.5) implies that
X √
p
| d − dj |2 6 4n,
j∈V

concluding the proof of the lemma.
Observe that if x > 0, we have

√

x>1+

x − 1 (x − 1)2
−
2
2

so that if X is a non-negative random variable of expectation 1 we have9
E

h√ i
Var (X)
.
X >1−
2

By applying the above inequality to dj /d we get
 
"r #
dj
Var
d
Var (dj )
1
dj
>1−
E
=1−
>1−
2
d
2
2d
2d
and
E

hp i √
1
dj > d − √ .
2 d

(38)

p
P
dj is concentrated around its expectation by using Chebyshev’s
We will show that
j∈V
10
inequality . In order to do that, we will bound their covariance as
E

hp

By the law of total probability

q

q

hp i
(j)
(j)
E
di = P (ei,j ) E
di + 1 + (1 − P (ei,j ))E
di

and
E

i
hp i hp i 8d2
.
di dj − E
di E
dj 6
n

hp

dj di

i

 q

q  q
q

(j)
(i)
(i)
(j)
di + 1 E
dj + 1 + (1 − P (ei,j ))E
dj E
di ,
= P (ei,j ) E

which imply that
i
hp i hp i
hp
di dj − E
di E
dj
E
9

This argument is due to Ori Gurel-Gurevich (see [29]).
5
A stronger bound which doesn’t require the hypothesis d 6 n1/3−c
p may be obtained with some concentration
techniques compatible with the stochastic dependence among the dj s.
10

28

q
 q

q  q

(j)
(i)
(i)
(j)
di + 1 E
dj + 1 + (1 − P (ei,j ))E
dj E
di
 q
q

q  q

(i)
(i)
(j)
(j)
2
dj + 1 E
di + 1 − P (ei,j ) (1 − P (ei,j ))E
dj E
di + 1
− P (ei,j ) E
 q

q  q

q
(i)
(j)
(i)
(j)
2
dj + 1 E
di − (1 − P (ei,j )) E
dj E
di
− P (ei,j ) (1 − P (ei,j ))E












q
q
q
q
q
q

(j)
(i)
(i)
(j)
(i)
(j)
= p(1 − p) E
di + 1 E
dj + 1 + E
dj E
di + E
dj E
di + 1

= P (ei,j ) E

+E

q

 q

8d2
(i)
(j)
dj + 1 E
di
,
6
n

(39)

where in the last inequality we used that by the Chernoﬀ bound w.h.p. it holds E
√
2d, and that p(1 − p) < p < d/n. From (D.5) it then follows that


Xp
n2
.
Var 
dj  6 2nd + 32d2 n <
dnc5

q

(j)
di



<

(40)

j∈V

Finally, by combining (D.5) and (D.5) with Chebyshev’s inequality we get




hXp i
Xp
Xp
√
1
n
n
dj < 2n d − √  6 P 
dj − E
dj > √  6 c5 .
P
n
d
d
j∈V
j∈V
j∈V

D.6

Proof of Theorem 4.7

For any vector x, we can write
(t)

x

t

=P x=

2n
X

ai λti D −1/2 wi = α1 1 + a2 λt2 D −1/2 w2 + e(t) ,

i=1

where α1 = 1⊺ Dx/kD 1/2 1k and ke(t) k 6 4λt kxk.
From√Lemma 4.6 (Claim 3) we have that for at least 2n−O(nd/(a−b)2 ) entries i of D −1/2 w2 ,
1
we get | 2nd(D −1/2 w2 )(i) − χ(i)| 6 100
, that is
99
√
if i ∈ V1 ∩ S and
100 2nd
99
√
(D −1/2 w2 )(i) 6 −
if i ∈ V2 ∩ S.
100 2nd
(D −1/2 w2 )(i) >

Thus, we get
−1/2
x(t) − x(t−1) = a2 λt−1
w2 + e(t) + e(t−1)
2 (λ2 − 1)D
−1/2
6 a2 λt−1
w2 + e(t) − e(t−1)
2 (λ2 − 1)D

and, when t − 1 > log




 
√
λ2
16 2n
/
log
λ ,
|a2 |(1−λ2 )

(x(t) − x(t−1) )(i) >

from (D.6) it follows that

99
√
a2 λt−1
2 (λ2 − 1)
200 2nd
29

if i ∈ Vj ∩ S and

(41)

(x(t) − x(t−1) )(i) 6 −

99
√
a2 λt−1
2 (λ2 − 1)
200 2nd

if i ∈ V3−j ∩ S.

either for j = 1 or for j = 2. Since |S| > n − O(nd/(a − b)2 ), we thus get a O(d/(a − b)2 )-weak
reconstruction.

E

More communities

Recall the deﬁnition of negative and positive type in Section 5. In this section we prove Theorem
5.1. The proof is divided in the following two lemmas.
Lemma E.1. Pick x ∼ {−1, 1}kn u.a.r. Then, with high probability, the vertices of V1 are either
all of positive type or all of negative type. Furthermore, the two events have equal probability.
Proof. We will write
x = x1 + xV1 + x⊥1 + x⊥ ,
where x1 is the component of x parallel to 1, xV1 is the component parallel to the vector
1V1 − k−1 1V , x⊥1 is the component in the eigenspace of λ2 and orthogonal to 1V1 − k−1 1V , and
x⊥ is the component orthogonal to 1 and to the eigenspace of λ2 .
For the above the make sense, 1V1 − k−1 1V must be an eigenvector of λ2 , which is easily
veriﬁed because its entries sum to zero and they are constant within components.
An important observation, and the reason for picking the above decomposition, is that x⊥1
is zero in V1 . The reason is that x⊥1 has to be orthogonal to 1V and to 1V1 − k−1 1V so from
hx⊥1 , 1V i = hx⊥1 , 1V1 − k−1 1V i = 0,
we deduce
hx⊥1 , 1V1 i = 0.
Thus, the entries of x⊥1 sum to zero within V1 , but, being in the eigenspace of λ2 , the entries
of x⊥1 are constant within components, and so they must be all zero within V1 .
Now we have
P t x = x1 + λt2 xV1 + λt2 x⊥1 + P t x⊥ ,
and so, for each v ∈ V1 it holds
(P t+1 x)v − (P t x)v = λt2 · (1 − λ2 )(xV1 )v + ((P t+1 − P t )x⊥ )v .

(42)

For t > T , the hypothesis λ < (1 − ε)λ2 implies that
|(P t x⊥ )v | 6 ||P t x⊥ ||∞ 6 ||P t x⊥ || 6 λt ||x⊥ || 6

√

n · λt 6

1 t
λ .
n1.5 2

Moreover, for each v ∈ V1 we have

|(xV1 )v | = k1V1 − k−1 1V k−2 hx, 1V1 − k−1 1V i 1 − k−1






X
X
X
X
xi  k − 1
xi 
1
k

xi −
xi −
,
= 
=
(k − 1)n
k
k
n
k
i∈V1

and

i∈V

hx, 1V1 − k−1 1V i
=
||xV1 || =
k1V1 − k−1 1V k

i∈V1

s

30

i∈V



X xi
X
k

,
xi −
(k − 1)n
k
i∈V1

i∈V

(43)

which imply that
|(xV1 )v | =

p

(1 − 1/k)/n kxV1 k.

1
n ||x||

(44)
p

> k/n.
Finally, note that by Lemma B.2 it holds w.h.p. ||xV1 || >
The latter fact together with (E) and (E) imply that w.h.p. the sign of (E) is the same as
the sign of (xV1 )v , which is the same for all elements of V1 and is equally likely to be positive or
negative.
Of course the same statement is true if we replace V1 by Vi for any i = 1, . . . , k; by a union
bound, it is also true for all i simultaneously with high probability.
1
) such
Lemma E.2. Pick x ∼ {−1, 1}kn u.a.r. There is an absolute constant p (e.g., p = 100
that, with probability at least p, all vertices of V1 have the same type, all vertices of V2 have the
same type, and the types are different.

Proof. This time we write
x = x1 + xV1+2 + xV1−2 + x⊥1,2 + x⊥
where
• x1 is the component parallel to 1V ,
• xV1+2 is the component parallel to 1V1 + 1V2 − k2 1V ,
• xV1−2 is the component parallel to 1V1 − 1V2 ,
• x⊥1,2 is the component in the eigenspace of λ2 and orthogonal to xV1+2 and xV1−2 ,
• x⊥ is the rest.
Similarly to the proof of Lemma E.1, the important observations are that xV1+2 and xV1−2 are
in the eigenspace of λ2 , and that x⊥1,2 is zero in all the coordinates of V1 and of V2 .
Thus, for each v ∈ V1 ∪ V2 we have
(P t+1 x)v − (P t x)v = λt2 (1 − λ2 )(xV1+2 + xV1−2 )v + ((P t+1 − P t )x⊥ )v .

(45)

From (E) it is easy to see that if x is such that, for every v ∈ V1 ∪ V2 , we have the two conditions
3
|(xV1+2 )v | 6 |(xV1−2 )v | and
4
1
|((P t+1 − P t )x⊥ )v | 6 λt2 · (1 − λ2 ) · |(xV1−2 )v |,
8

(46)
(47)

then such an x satisﬁes the conditions of the Lemma, that is all the elements in V1 have the
same type, all the elements of V2 have the same type, and the types are diﬀerent. Now note
that, since


X
2X 
1 X
xi
xi −
|(xV1+2 )v | =
xi +
and
2n
k
i∈V
i∈V1
i∈V1


X
X
1 
xi  ,
xi −
|(xV1−2 )v | =
2n
i∈V2

i∈V1

if x satisﬁes

X
√
√
xv 6 3 n,
2 n6
v∈V1

31

(48)

X
√
√
xv 6 − n and
−2 n 6

(49)

v∈V2

06

X

xv 6

v∈V /(V1 ∪V2 )

1√
kn,
10

(50)

then (E) is satisﬁed, and note that (E), (E) and (E) are independent and each happens with
constant probability.
Finally, observe that if (E) holds then (E) is satisﬁed with high probability when t > T .
It is enough to pick ℓ = log(3n) to have, with high probability, that the signatures are well
deﬁned and they are the same within each community and diﬀerent between communities. The
ﬁrst lemma guarantees that, with high probability, for all ℓ vectors, all vertices within each
community have the same type. The second lemma guarantees that, with high probability, the
signatures are diﬀerent between communities.

32

