Luca Becchetti
email: becchetti@dis.uniroma1.it

Andrea Clementi
email: clementi@mat.uniroma2.it

Francesco Pasquale
email: pasquale]@mat.uniroma2.it

AND Luca Trevisan
email: l.trevisan@unibocconi.it

FIND YOUR PLACE: SIMPLE DISTRIBUTED ALGORITHMS FOR COMMUNITY DETECTION *

Keywords: Distributed Algorithms, Averaging Dynamics, Community Detection, Spectral Analysis, Stochastic Block Models

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) reects 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 which is non-trivial even in a centralized setting.

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.

Besides the general motivations described above, the major theoretical goal of this work is to show, in a rigorous and well-established framework, that the algorithm above turns out to be one of the few examples of a dynamics [START_REF] Angluin | A Simple Population Protocol for Fast Robust Approximate Majority[END_REF][START_REF] Afek | A biological solution to a fundamental distributed computing problem[END_REF][START_REF] Doty | Timing in chemical reaction networks[END_REF][START_REF] Mossel | Majority dynamics and aggregation of information in social networks[END_REF] 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 denition 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 1 or the median it sees in its neighborhood, 2 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 denition, 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 denition of dynamics, since it assigns roles to 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 is not [START_REF] Boyd | Randomized gossip algorithms[END_REF][START_REF] Shah | Gossip algorithms[END_REF]. Important applications of linear dynamics have been proposed in the recent past [START_REF] Kempe | Gossip-based computation of aggregate information[END_REF][START_REF] Aysal | Broadcast gossip algorithms for consensus[END_REF][START_REF] Tsitsiklis | Problems in decentralized decision making and computation[END_REF][START_REF] Kleinberg | Authoritative sources in a hyperlinked environment[END_REF], for example to perform basic tasks such as self-stabilizing consensus in faulty distributed systems [START_REF] Bénézit | Interval consensus: from quantized gossip to voting[END_REF][START_REF] Xiao | Distributed average consensus with least-mean-square deviation[END_REF][START_REF] Olshevsky | Convergence speed in distributed consensus and aver-aging[END_REF]. The convergence time of the Averaging dynamics is the mixing time of a random walk on G [START_REF] Shah | Gossip algorithms[END_REF]. It is logarithmic in |V | if the underlying graph is a good expander [START_REF] Hoory | Expander graphs and their applications[END_REF], while it is slower on graphs that exhibit sparse cuts.

While previous work on applications of linear dynamics has focused on tasks that are specic 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 Averaging dynamics is able to address community detection, that is, it identies a partition (V 1 , V 2 ) of a clustered graph G = ((V 1 , V 2 ), 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). Let A denote its adjacency matrix and D the diagonal matrix such that D u,u is the degree of node u. We show that if a partition (V 1 , V 2 ) of G exists such that 1 V1 -1 V2 is 3 (or is close to) 1 Given a node v ∈ V , the plurality is dened as the most frequent state among those taken on by the neighbors of v (with ties broken by some xed rule).

2 When states correspond to rational values. 3 As explained in more detail later, 1 V i is the vector with |V | components, such that the j-th component is 1 if j ∈ V i and is 0 otherwise. a right eigenvector of the second largest eigenvalue of the graph's transition matrix 4 P = D -1 A of G, and the gap between the second and the third largest eigenvalues is suciently large, our algorithm recovers (V 1 , V 2 ), or a close approximation thereof, in a logarithmic number of rounds. Though the algorithm we propose does not entail any explicit eigenvector computation, it does exploit the spectral structure of the underlying graph, based on the intuition that our dynamics is a distributed version of the power method [START_REF] Abbe | Community detection and stochastic block models: Recent developments[END_REF].

Our approach and analysis present a few novelties. Among these are the completely local and decentralized criterion whereby nodes assign themselves to clusters, and the spectral bounds we prove for certain graph classes. A conceptual contribution is to have each node, at each round t, assign itself to a cluster (nd its place) according to the dierence between its values at rounds t and t -1. Globally, this criterion amounts to removing the component of the state vector in the eigenspace of the rst eigenvalue, without computing it. This idea presents two advantages: it results in a particularly simple algorithm, and it gives a running time that depends on the gap between the second and third eigenvalues of the transition matrix of the graph.

In graphs consisting of two expanders connected by a sparse cut, the corresponding running time only depends on the intra-cluster expansion (i.e., on the gap between the second and third eigenvalues of the transition matrix), and it can be O(log |V |), while the mixing time of the overall graph (that depends on the gap between the rst and the second eigenvalues) can be Ω(|V | α ), for some constant α > 0. To the best of our knowledge, this is the rst distributed block reconstruction algorithm that, in the above specied graphs, converges faster than the mixing time of the underlying random walk.

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 communities and (ii) the gap between the second and third eigenvalues is suciently 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, including 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 = ((V 1 , V 2 ), E) is a connected graph over the vertex set V 1 ∪ V 2 , with |V 1 | = |V 2 | = n, adjacency matrix A, and such that every node has degree d and (exactly) b neighbors outside its cluster. If the two subgraphs induced by V 1 and V 2 are good expanders and b is suciently 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 5 ): 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 4 This is the transition matrix of a simple random walk over G (see Subsection 2.2 for more on the properties of P ). 5 We 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.

node can apply a simple and completely local clustering rule at each round, which eventually results in a strong reconstruction (Theorem 3.3).

We then show that, under mild assumptions, a graph selected from the regular stochastic block model [START_REF] Brito | Recovery and rigidity in a regular stochastic block model[END_REF] is a (2n, d, b)-clustered regular graph that satises 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 polynomial-time centralized algorithms [START_REF] Mossel | Reconstruction and estimation in the planted partition model[END_REF][START_REF] Brito | Recovery and rigidity in a regular stochastic block model[END_REF] (Section 1.2 and Corollary 3.6).

We further show that a natural extension of our algorithm, in which nodes maintain an array of values and an array of colors, correctly identies 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.2).

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 the second and third eigenvalues of the transition matrix P (Theorem 4.7). As an application, we further prove that these conditions are met by the stochastic block model [START_REF] Abbe | Exact recovery in the stochastic block model[END_REF][START_REF] Coja-Oghlan | Graph partitioning via adaptive spectral techniques[END_REF][START_REF] Decelle | Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications[END_REF][START_REF] Dyer | The solution of some random NP-hard problems in polynomial expected time[END_REF][START_REF] Holland | Stochastic blockmodels: First steps[END_REF][START_REF] Jerrum | The metropolis algorithm for graph bisection[END_REF][START_REF] Mcsherry | Spectral partitioning of random graphs[END_REF], a random graph model that oers a popular framework for the probabilistic modelling of graphs that exhibit good clustering or community properties. We here consider its simplest version, with two equal-sized communities, dened as follows.

Definition 1.1. The random graph G 2n,p,q consists of 2n nodes and the following edge probability: The node set is partitioned into two subsets V 1 and V 2 , 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 dierent partitions appear with probability q = q(n) < p. In the remainder, we let a = pn and b = qn respectively denote the expected inner degree and the expected outer degree of a node.

In this paper, we prove that graphs sampled from G 2n,p,q satisfy the above approximate regularity and spectral gap conditions, w.h.p., whenever a-b > c (a + b) • log n, for a suitable, absolute constant c > 0 (Theorem 4.10).

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 rened, ad-hoc analysis of the Averaging dynamics for the G 2n,p,q model, showing that this protocol achieves weak reconstruction, correctly classifying a 1ε fraction of vertices, in logarithmic time whenever a -b > Ω( (a + b)) and the expected degree d = a + b grows at least logarithmically (notice that the factor hidden in the notation Ω(•) depends on ε -see Theorem 4.12). This rened analysis requires a deeper understanding of the eigenvectors of the transition matrix of G.

Coja-Oghlan [START_REF] Coja-Oghlan | Graph partitioning via adaptive spectral techniques[END_REF] dened 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 sucient conditions under which a right eigenvector of the second largest eigenvalue of the transition matrix of a graph approximately identies the hidden partition. We give a tight analysis of the spectrum of the transition matrix of graphs sampled from the stochastic block model in Subsection 4.3. 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.

Final remarks. While we do think that improving performance is an important goal, this was not the main driver behind this work. Rather, we believe the main contribution of this paper is providing rigorous evidence for the eectiveness of completely decentralized and elementary dynamics in addressing important mining tasks, such as community detection in clustered non-dense graphs. The complexity of such a task appears to lie far beyond the tasks to which this kind of dynamics have been applied in the area of distributed computing (for example, consensus problems).

Related work.

Dynamics for block reconstruction. Dynamics received considerable attention in the recent past across dierent research communities, both as ecient distributed algorithms [START_REF] Angluin | A Simple Population Protocol for Fast Robust Approximate Majority[END_REF][START_REF] Bénézit | Interval consensus: from quantized gossip to voting[END_REF][START_REF] Olshevsky | Convergence speed in distributed consensus and aver-aging[END_REF][START_REF] Métivier | An optimal bit complexity randomized distributed mis algorithm[END_REF] and as abstract models of natural interaction mechanisms inducing emergent behavior in complex systems [START_REF] Afek | A biological solution to a fundamental distributed computing problem[END_REF][START_REF] Cardelli | The Cell Cycle Switch Computes Approximate Majority[END_REF][START_REF] Doty | Timing in chemical reaction networks[END_REF][START_REF] Franks | Information ow, opinion polling and collective intelligence in househunting social insects[END_REF][START_REF] Mossel | Majority dynamics and aggregation of information in social networks[END_REF]. For instance, simple averaging dynamics have been considered to model opinion formation mechanisms [START_REF] Degroot | Reaching a consensus[END_REF][START_REF] Friedkin | Social inuence and opinions[END_REF], while a number of other dynamics have been proposed to describe dierent social phenomena [START_REF] Easley | Networks, crowds, and markets: Reasoning about a highly connected world[END_REF]. Label propagation algorithms [START_REF] Raghavan | Near linear time algorithm to detect community structures in large-scale networks[END_REF] are dynamics based on majority updating rules [START_REF] Angluin | A Simple Population Protocol for Fast Robust Approximate Majority[END_REF] and have been applied to some computational problems including clustering. Several papers present experimental results for such protocols on specic classes of clustered graphs [START_REF] Barber | Detecting network communities by propagating labels under constraints[END_REF][START_REF] Liu | Advanced modularity-specialized label propagation algorithm for detecting communities in networks[END_REF][START_REF] Raghavan | Near linear time algorithm to detect community structures in large-scale networks[END_REF]. The only available rigorous analysis of label propagation algorithms on planted partition graphs is the one presented in [START_REF] Kothapalli | On the analysis of a label propagation algorithm for community detection[END_REF], where the authors propose and analyze a label propagation protocol on G 2n,p,q for dense topologies. In particular, their analysis considers the case where p = Ω(1/n 1/4-ε ) and q = O(p 2 ), 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.

Belief propagation algorithms. Because of their relevance for the reconstruction problem, we also briey discuss the class of belief propagation algorithms, whose simplicity is close to that of dynamics. These algorithms are best known as messagepassing algorithms for performing inference in graphical models [START_REF] Mackay | Information theory, inference and learning algorithms[END_REF]. Belief propagation cannot be considered a dynamics: At each round, every node sends dierent messages to each neighbor. As a result, the update rule is not symmetric w.r.t. the neighbors, requiring thus port numbering [START_REF] Suomela | Survey of local algorithms[END_REF], while the required amount of local memory grows linearly in the degree of the node. There is non-rigorous, strong supporting evidence that some belief propagation algorithms might be optimal for the reconstruction problem [START_REF] Decelle | Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications[END_REF]. A rigorous analysis is 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 [START_REF] Weiss | Correctness of local probability propagation in graphical models with loops[END_REF][START_REF] Mooij | Sucient conditions for convergence of the sumproduct algorithm[END_REF]. A complex algorithm based on belief propagation has been presented in [START_REF] Mossel | Belief propagation, robust reconstruction and optimal recovery of block models[END_REF] by Mossel et al.: Among other results, they show that this algorithm achieves a weak reconstruction for G 2n,p,q which is optimal for certain parameters.

General algorithms for block reconstruction. 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 with the second eigenvalue of the adjacency matrix A of G, or the eigenvector corresponding to the largest eigenvalue of the matrix A -d n J [START_REF] Boppana | Eigenvalues and graph bisection: An average-case analysis[END_REF][START_REF] Coja-Oghlan | Spectral techniques, semidenite programs, and random graphs[END_REF][START_REF] Coja-Oghlan | Graph partitioning via adaptive spectral techniques[END_REF][START_REF] Mcsherry | Spectral partitioning of random graphs[END_REF] 6 , since these are correlated with the hidden partition. More recently spectral algorithms have been proposed [START_REF] Abbe | Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures, acyclic bp, and the information-computation gap[END_REF][START_REF] Coja-Oghlan | Graph partitioning via adaptive spectral techniques[END_REF][START_REF] Bordenave | Non-backtracking spectrum of random graphs: community detection and non-regular ramanujan graphs[END_REF][START_REF] Mossel | A proof of the block model threshold conjecture[END_REF][START_REF] Krzakala | Spectral redemption in clustering sparse networks[END_REF][START_REF] Peng | Partitioning well-clustered graphs: Spectral clustering works![END_REF] 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 [START_REF] Kempe | A decentralized algorithm for spectral analysis[END_REF] 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 eective concept from Hassin and Peleg in [START_REF] Hassin | Distributed probabilistic polling and applications to proportionate agreement[END_REF], such algorithms are not even light-weight :

Dierent and non-simple operations are executed at dierent rounds, nodes have identities, messages are treated dierently 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 [START_REF] Lanczos | An iteration method for the solution of the eigenvalue problem of linear differential and integral operators[END_REF] as a subroutine to compute the eigenvector associated with the second eigenvalue of the adjacency matrix of G.

Notice that the mixing time of graphs sampled from G 2n,p,q is at least of the order of a+b 2b : Hence, it can be super-logarithmic and even n Ω (1) .

In general, the reconstruction problem has been studied extensively using a multiplicity of techniques, which include combinatorial algorithms [START_REF] Dyer | The solution of some random NP-hard problems in polynomial expected time[END_REF], belief propagation [START_REF] Decelle | Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications[END_REF] and variants of it [START_REF] Mossel | Belief propagation, robust reconstruction and optimal recovery of block models[END_REF], spectral-based techniques [START_REF] Mcsherry | Spectral partitioning of random graphs[END_REF][START_REF] Coja-Oghlan | Graph partitioning via adaptive spectral techniques[END_REF], Metropolis approaches [START_REF] Jerrum | The metropolis algorithm for graph bisection[END_REF], and semidenite programming [START_REF] Abbe | Exact recovery in the stochastic block model[END_REF], among others.

Stochastic Block Models have been studied in a number of areas, including computer science [START_REF] Boppana | Eigenvalues and graph bisection: An average-case analysis[END_REF][START_REF] Mcsherry | Spectral partitioning of random graphs[END_REF][START_REF] Massoulie | Community Detection Thresholds and the Weak Ramanujan Property[END_REF], probability theory [START_REF] Mossel | Reconstruction and estimation in the planted partition model[END_REF], statistical physics [START_REF] Decelle | Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications[END_REF], and social sciences [START_REF] Holland | Stochastic blockmodels: First steps[END_REF]. Unlike the distributed setting, where the existence of light-weight protocols [START_REF] Hassin | Distributed probabilistic polling and applications to proportionate agreement[END_REF] is the main issue (even in non-sparse regimes), in centralized settings, strong attention has been devoted to establishing sharp thresholds for weak and strong reconstruction. Dene 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. [START_REF] Decelle | Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications[END_REF]

√ a + b + log n [2].
Versions of the stochastic block model in which the random graph is regular have also been considered [START_REF] Mossel | Reconstruction and estimation in the planted partition model[END_REF][START_REF] Brito | Recovery and rigidity in a regular stochastic block model[END_REF]. In particular, Brito et al. [START_REF] Brito | Recovery and rigidity in a regular stochastic block model[END_REF] show that strong reconstruction is possible in polynomial time when a -b > 2

√ a + b -1.
1.3. Roadmap. The rest of this paper is organized as follows. In Section 2, we formalize the main concepts concerning block reconstruction and the Averaging dynamics. Section 3 is devoted to the analysis of our protocol in the case of regular graphs with two communities. This analysis is then generalized in Section 4 for the case of almost-regular graphs with two communities. In particular, the important case of the stochastic block model is described in Subsections 4.2 and 4.3. In Section 5, we show how our analysis and the consequent weak reconstruction can be extended to the case of regular graphs having more communities. Some useful but standard results in linear algebra and probability are deferred to the Appendix.

Preliminaries.

2.1. Distributed block reconstruction. The block reconstruction of a clustered graph is a two-coloring of the nodes that separates the hidden communities, and it can be dened in two versions depending on whether a small fraction of outliers is allowed or not.

Definition 2.1. Let G = ((V 1 , V 2 ), E) be a graph with V 1 ∩ V 2 = ∅. An ε-weak reconstruction is a map f : V 1 ∪ V 2 → {red, blue} such that there are two subsets W 1 ⊆ V 1 and W 2 ⊆ V 2 with |W 1 ∪ W 2 | (1 -ε)|V 1 ∪ V 2 | and f (W 1 ) ∩ f (W 2 ) = ∅.
When ε = 0 we say that f is a strong reconstruction.

Given a graph G = ((V 1 , V 2 ), E), the block reconstruction problem requires computing an ε-reconstruction of G. In this paper, we propose the following distributed protocol for this problem. 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 u ∈ V independently samples its initial value from {-1, +1} uniformly at random; Updating rule: At each subsequent round t 1, every node u ∈ V 1. (Averaging dynamics) Updates its value x (t) (u) to the average of the values of its neighbors at the end of the previous round, 2. (Coloring) If x (t) (u) x (t-1) (u) then u sets color (t) (u) = blue; otherwise, u sets color (t) (u) = red.

Distributed implementation of Averaging protocol and its properties. The protocol above can be implemented in the popular synchronous local communication model [START_REF]Locality in distributed graph algorithms[END_REF], where nodes share a global clock that is initialized at the beginning of the execution. At each round determined by the global clock, every node can perform local computations and send/receive one message of arbitrary length to/from each of its neighbors. We assume that there is no fault or message corruption: If a message is sent at round t, then it arrives safely before round t + 1 begins.

However, we remark that the Averaging protocol requires no unique labeling of the nodes, and it 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.

Finally, we remark that the clustering criterion is completely local, in the sense that a decision is individually and independently made by each node at 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 supercially so. Despite being local, the clustering criterion uses information that reects the global structure of the network, since nodes' values are related to the second eigenvector of the network's transition matrix.

Notational remark. In the remainder of the paper, we use x (t) to denote the vector of values collectively held by the nodes at the end of round t and, for simplicity of notation, we use x (0) = x to denote the vector of binary values held upon initialization.

2.2. 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 on G, which are best studied using tools from linear algebra that we briey summarize below.

Let G = (V, E) be an undirected graph (possibly with multiple edges and self loops), A its adjacency matrix and d u the degree of node u. The transition matrix of (the random walk on) G is the matrix P = D -1 A, where D is the diagonal matrix such that D u,u = d u . The entry P u,v = (1/d u ) • A u,v thus corresponds to the probability of going from u to v in one step of the random walk on G. So P operates as the random walk process on G by left multiplication, and as the Averaging dynamics by right multiplication. Definition 2.2. For i = 1, 2, dene 1 Vi as the |V |-dimensional vector, whose

u-th component is 1 if u ∈ V i and is 0 otherwise. If (V 1 , V 2 ) is a bipartition of the nodes with |V 1 | = |V 2 | = n, we dene the partition indicator vector χ = 1 V1 -1 V2 .
It is easy to show that, after t rounds of the Averaging dynamics, the vector of values at time t can be written as

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 exploit in the next section. In what follows we always denote by

λ 1 λ 2 • • • λ 2n
the eigenvalues of P . Recall that P is a stochastic matrix, hence λ 1 = 1 and λ 2n -1.

Moreover, for all graphs that are connected and not bipartite, λ 2 < 1 and λ 2n > -1. We denote by λ the largest, in absolute value, among all but the rst two eigenvalues, namely λ = max {|λ i | : i = 3, 4, . . . , 2n} .

Unless otherwise specied, the norm of a vector x is the 2 norm x = i (x(i)) 2 , and the norm of a matrix A is the spectral norm

A = sup x: x =1

Ax .

For a diagonal matrix, this is the largest diagonal entry in absolute value.

Cuts and conductance. The notion of conductance plays an important role in the convergence results we prove in Section 4, in particular in the proofs of Theorems 4.7 and 4.12.

Let G = (V, E) be an undirected graph with |E| = m and consider a subset S ⊆ V . Then, the corresponding cut (S, V -S) is dened as the subset of the edges of the graph with one endpoint in S and the other in V -S. The volume vol(S) of a subset S ⊆ V is dened as vol(S) = u∈S d u .

Definition 2.3. Given a graph G = (V, E) and a subset S ⊆ V , we dene the

associated conductance Φ G (S) as Φ G (S) = |(S, V -S)| vol(S) .
The conductance of G is dened as

Φ G = min S:vol(S) m/2
Φ G (S) .

We simply write Φ in the remainder, whenever G is clear from context. 73. Strong reconstruction for regular graphs. If the graph G is d-regular, then P = (1/d)A is a real symmetric matrix, P and A have the same set of eigenvectors, and 1 is an eigenvector with eigenvalue 1. We denote by

v 1 = (1/ √ 2n)1, v 2 , . . . , v 2n
a basis of orthonormal eigenvectors, where each v i is the eigenvector associated with eigenvalue λ i . Then, we can write a vector x as a linear combination x = i α i v i , and the averaging process, starting from x, can be described as

P t x = i λ t i α i v i = 1 2n i x(i) 1 + 2n i=2 λ t i α i v i ,
which implies that x (t) = P t x tends to α 1 v 1 as t → ∞, that is, it converges to the vector that has the average of x in every coordinate.

We say that a d-

regular graph G is (2n, d, b)-regular if a partition of the nodes (V 1 , V 2 ) exists such that every node in V 1 has b neighbors in V 2 and every node in V 2 has b neighbors in V 1 . Fact 1. If G is a (2n, d, b)-regular graph then the partition indicator vector χ = 1 V1 -1 V2 is an eigenvector of the transition matrix P of G with eigenvalue 1 -2b/d.
Proof. Every node u has b neighbors w on the opposite side of the partition, for which χ(w) = -χ(u), and d -b neighbors w on the same side, for which χ(w) = χ(u),

so (P χ)(u) = 1 d ((d -b)χ(u) -bχ(u)) = 1 - 2b d χ(u) .
We next show that, if the regular graph is well clustered, then the Averaging

G = ((V 1 , V 2 ), E) is a (2n, d, b)-regular graph such that 1 -2b/d is the second largest eigenvalue of P , that is, λ 2 = 1 -2b/d and λ < λ 2 .
We also call a = d -b the inner degree of each node.

In the next lemma, we show that, after t rounds of the Averaging dynamics over a (2n, d, b)-clustered regular graph, the conguration x (t) is close to a linear combination of 1 and χ.

Lemma 3.2. Assume that we run the Averaging dynamics on a (2n, d, b)-clustered regular graph G with an arbitrary initial vector x ∈ {-1, 1} 2n . Then there are reals α 1 , α 2 such that, at every round t 0, (3.1)

x (t) = α 1 1 + α 2 λ t 2 χ + e (t)
, where e (t) ∞ λ t √ 2n .

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

P t x = i λ t i x, v i v i , where 1 = λ 1 > λ 2 = 1 -2b/d > λ 3 • • • λ 2n are the eigenvalues of P and v 1 = 1 √ 2n 1, v 2 = 1 √ 2n χ, v 3 , . . . , v 2n are a corresponding sequence of orthonormal eigenvectors. Hence, x (t) = 1 2n x, 1 • 1 + λ t 2 1 2n x, χ • χ + 2n i=3 λ t i α i v i = α 1 1 + α 2 λ t 2 • χ + 2n i=3 λ t i α i v i ,
where we set α 1 = 1 2n 1, x and α 2 = 1 2n χ, x . We bound the ∞ norm of the last term as

2n i=3 λ t i α i v i ∞ 2n i=3 λ t i α i v i 2 = 2n i=3 λ 2t i α 2 i λ t 2n i=1 α 2 i = λ t x = λ t √ 2n .
Informally speaking, the equation above naturally suggested the choice of the coloring rule in the Averaging protocol, once we considered the dierence of two consecutive values of any node u, that is, (3.2)

x (t-1) (u) -x (t) (u) = α 2 λ t-1 2 (1 -λ 2 )χ(u) + e (t-1) (u) -e (t) (u) .
Intuitively, if λ is suciently small, we can exploit the bound on e (t)

∞ in (3.1)
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. Proof. From (3.2) we have that sgn

Theorem 3.3 (Strong reconstruction). Let G = ((V 1 , V 2 ), E) be a connected
x (t-1) (u) -x (t) (u) = sgn (α 2 χ(u)) when- ever (3.3) α 2 λ t-1 2 (1 -λ 2 ) > e (t-1) (u) -e (t) (u) .
From (3.1) we have that e (t) (u)

λ t √ 2n, thus (3.3) is satised for all t such that (3.4) t -1 log 2 √ 2n |α 2 |(1 -λ 2 ) • 1 log (λ 2 /λ) .
Next, note that the right-hand side of (3.4) can be upper bounded as follows:

log 2 √ 2n |α 2 |(1 -λ 2 ) • 1 log (λ 2 /λ) = log d √ 2n b|α 2 | • 1 log (λ 2 /λ) < log d √ 2n b|α 2 | • 1 log (1 + δ) 2 δ log n √ 2n |α 2 | , (3.5)
where the rst equality follows since λ 2 = 1 -2b/d in the (2n, d, b)-clustered regular case, the second inequality follows from the hypothesis on the spectral gap between λ 2 and λ, while the third inequality follows since log(1 + δ) δ/2, for a suciently small δ, and from the trivial bound d/b n.

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 dierence between the two partial averages in the two communities, that is |α 2 |, is suciently large, w.h.p. More precisely, from Lemma B.1, if R is the sum of 2n Rademacher random variables, for every 0 < η < 1,

P |R| η √ 2n O(η) .
Since α 2 = 1 2n χ, x and x is a vector of Rademacher random variables, the previous inequality implies that

|α 2 | = 1 2n χ, x n -γ ,
for some positive constant γ, w.h.p. In this case, we can upper bound (3.5) as follows:

2 δ log n √ 2n |α 2 | 2 δ log √ 2n γ+3/2 .
Hence, for some positive γ, w.h.p. (3.3) is satised whenever

(3.6) t -1 2 δ log √ 2n γ+3/2 = 2 δ γ + 3 2 log n + 2 δ log √ 2 .
As for the communication complexity of the protocol, we observe that, at every round, every node receives one message (i.e., its current state) from each neighbor.

So, since we proved that the completion time is w.h.p. O(log n), the overall number of messages is O(m log n), w.h.p. Finally, in order to correctly apply the coloring rule, the values x (t) (u) must be encoded with Θ(log n) bits.

Not surprisingly, a typical case in which the spectral condition required by Theorem 3.3 is satised is when the input graph consists of two regular expanders connected by a sparse regular cut. This is formalized in the next corollary. Proof. We can write the transition matrix as P = (1/d)(M + E) where

Corollary 3.4. Let G = ((V 1 , V 2 ), E) be a (2n
M = A 1 0 0 A 2 , E = 0 B B 0 ,
and B is a matrix with exactly b non-zero entries in each row and in each column, and each non-zero entry being 1. Observe that for every i = 1, . . . , 2n (see e.g.

Corollary 4.10 in Chapter IV in [START_REF] Stewart | Matrix Perturbation Theory[END_REF])

(3.7) |λ i (M + E) -λ i (M )| E 2 . Since λ 1 (A 1 ) = λ 1 (A 2 ) = a, we also have that λ 1 (M ) = λ 2 (M ) = a and λ 3 (M ) = max{λ 2 (A 1 ), λ 2 (A 2 )} = λ A (notice that a value µ is an eigenvalue of M if and only if µ is an eigenvalue of A 1 or an eigenvalue of A 2 ). Hence, λ 3 (P ) (1/d)(λ 3 (M ) + E 2 ) λ A + b d 1 1 + δ • a -b d = 1 1 + δ λ 2 ,
where in the rst inequality we used (3.7), in the second one we used λ 3 (M ) = λ A and E 2 b, and in the third inequality we used the hypothesis a -b Given two parameters a(n) and b(n) (internal and external degrees, respectively), partition the vertices into two equal-sized subsets V 1 and V 2 and then sample a random a(n)-regular graph over each of V 1 and V 2 and a random b(n)-regular graph between V 1 and V 2 . This model can be instantiated in dierent 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) [START_REF] Mossel | Reconstruction and estimation in the planted partition model[END_REF][START_REF] Brito | Recovery and rigidity in a regular stochastic block model[END_REF]. We here consider a regular stochastic block model obtained as random lift [START_REF] Amit | Random graph coverings I: General theory and graph connectivity[END_REF].

(1 + δ)(λ A + b).
If G is a multigraph on n vertices, then a random 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 v 1 , . . . , v k in G , every edge (u, v) in G is replaced by a random bipartite matching between u 1 , . . . , u k and v 1 , . . . , v k (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 u 1 , . . . , u k which is sampled by taking a random permutation π : {1, . . . , k} → {1, . . . , k} and connecting u i to u π(i) for every i. The regular stochastic block model we consider here is a random n-lift of the graph that has only two vertices v 1 and v 2 : it has b parallel edges between v 1 and v 2 , and it has a/2 self-loops on v 1 and a/2 self-loops on v 2 .

If G is a graph sampled according to any random regular stochastic block model with internal and external degrees a and b respectively (notice that those sampled according to random lifts are, in general, multi-graphs), then G 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. By using a general result of Friedman and Kohler [START_REF] Friedman | The relativized second eigenvalue conjecture of Alon[END_REF] on random k-lifts of a graph, 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 χ. Then, w.h.p.,

λ 2 a + b ( √ a + b -1 + o(1)) . (3.8)
Proof. The lemma is a consequence of the following general results of Friedman and Kohler [START_REF] Friedman | The relativized second eigenvalue conjecture of Alon[END_REF] (see also Bordenave [START_REF] Bordenave | A new proof of Friedman's second eigenvalue Theorem and its extension to random lifts[END_REF]).

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. Our base graph consists of only two nodes and it has two eigenvalues, that is, 1 and 1 -2b/d. When we consider the random n-lift, the obtained multi-graph has 2n -2 new eigenvalues. In this setting, Friedman and Kohler [START_REF] Friedman | The relativized second eigenvalue conjecture of Alon[END_REF] prove that, if d 3, then with probability 1 -O(1/n) over the choice of a random n-lift, the new eigenvalues of the adjacency matrix of the lifted graph are at most 2

√ d -1 + o(1) in absolute value. 8
Since λ 2 = a-b a+b , using (3.8) in Theorem 3.3 for clustered regular multigraphs (see Remark 1), we get a strong reconstruction for the regular stochastic block model. Proof. The hypothesis on a -b implies that (3.9)

λ 2 = a -b a + b > 2(1 + η) √ a + b .
On the other hand, for suciently large n,

(3.10) λ 2 a + b ( √ a + b -1 + o(1)) < 2 √ a + b .
Together, (3.9) and (3.10) imply λ 2 > (1+η)λ. Then, the claim follows from Theorem 3.3. In particular, plugging δ = η into (3.6),

t -1 2 η γ + 3 2 log n + 2 η log √ 2 .
The Averaging process on non-regular graphs. The results of Section 3 rely on very clear spectral properties of regular, clustered graphs, immediately reecting their underlying topological structure. If G is not regular then the 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. We consider the normalized adjacency

matrix of G N = D -1/2 AD -1/2 = D 1/2 P D -1/2 .
Notice that N is symmetric, and P and N have the same eigenvalues λ 1 , . . . , λ 2n . We also recall that λ is dened as the largest, in absolute value, among all but the rst two eigenvalues, namely

λ = max {|λ i | : i = 3, 4, . . . , 2n} .
Moreover, v is an eigenvector of P if and only if D 1/2 v is an eigenvector of N . Finally, P = N when G is regular. Let w 1 , . . . , w 2n be a basis of orthonormal eigenvectors of the normalized adjacency matrix N of G, with w i dened as the eigenvector associated with the eigenvalue λ i , for each i. Notice that

w 1 = D 1/2 1 D 1/2 1 . If we set v i = D -1/2 w i ,
we obtain a set of eigenvectors for the transition matrix P , and we can express the initial vector as a linear combination of them, i.e., (4.1)

x = i αi v i .
Then, the Averaging process can again be described by the following linear equation (4.2)

x (t) = P t x = i λ t i αi v i = α1 v 1 + 2n i=2 λ t i αi v i .
We remark that (4.1) uniquely denes the coecients αi , and, since P is not symmetric, they cannot be written as simple inner products. The next lemma summarizes some useful properties of the Averaging process for general graphs. Lemma 4.1. Let G be connected and not bipartite and let x be any initial vector.

Then 1. The coecients in the spectral decomposition of x in (4.1) are αi = w i D 1/2 x = v i Dx , for i = 1, . . . , 2n.

2. For every t 1, the dierence between vector x (t) in (4.2) in two consecutive rounds is

(4.3) x (t-1) -x (t) = α2 (1 -λ 2 )λ t-1 2 v 2 + e (t-1) -e (t)
, where e (t) = 2n i=3 λ t i αi v i .

3. For every t 0, the norm of vector e (t) in (4.3) is bounded by

(4.4) e (t) d max d min λ t x = λ t d max d min 2n .
where d max and d min are the maximum and minimum degree of the nodes, respectively.

Proof. The rst claim follows from the denition of the αi 's. Indeed, since x =

i αi v i , D 1/2 x = i αi D 1/2 v i = i αi w i .
On the other hand, w i 's are orthonormal, so αi is the projection of D 1/2 x along w i , i.e., αi = w i D 1/2 x .

As for the second claim, (4.3) follows straightforwardly from (4.2), when one considers

x (t-1) -x (t) .
As for the third claim,

e (t) 2 = 2n i=3 αi λ t i D -1/2 w i 2 D -1/2 2 2n i=3 αi λ t i w i 2 = D -1/2 2 2n i=3 α2 i λ 2t i D -1/2 2 λ 2t 2n i=3 α2 i D -1/2 2 λ 2t D 1/2 x 2 D -1/2 2 D 1/2 2 λ 2t x 2 d max d min λ 2t x 2 = d max d min λ 2t 2n,
where the last equality follows since, by denition, x 2 = 2n. Let G be connected and not bipartite, and let x be any initial vector. If α2 = 0, then, for every component (i.e., node) u such that v 2 (u) = 0,

(4.5) sgn(x (t-1) (u) -x (t) (u)) = sgn(α 2 v 2 (u)) , whenever t -1 log 2 √ 2n(dmax/dmin) | α2|•|v2(u)|(1-λ2) log(λ 2 /λ) .
Proof. From Claim 3 of Lemma 4.1 (in particular, using (4.4)),

|e (t-1) (u) -e (t) (u)| e (t-1) -e (t) e (t-1) + e (t) < 2 d max d min λ t-1 x .
Hence, (4.3) implies that sgn(x (t-1) (u) -

x (t) (u)) = sgn(α 2 v 2 (u)), whenever |α 2 v 2 (u)|λ t-1 2 (1 -λ 2 ) 2 d max d min λ t-1 x , that is, whenever λ 2 λ t-1 2 2n(d max /d min ) |α 2 | • |v 2 (u)|(1 -λ 2 )
.

Taking logarithms of both sides yields (4.5).

The result stated by Corollary 4.2 will be leveraged in the following subsections to prove weak reconstruction for the following class of clustered, almost regular graphs.

Definition 4.3 (Clustered γ-regular graphs). A (2n, d, b, γ)-clustered graph G = ((V 1 , V 2 ), E) is a graph over the vertex set V = V 1 ∪ V 2 , where |V 1 | = |V 2 | = n such that: i) every node u ∈ V has degree d u = d ± γd, and ii) every node in V 1 has b ± γd neighbors in V 2 , and every node in V 2 has b ± γd neighbors in V 1 .
We observe that, in any (2n, d, b, γ)-clustered graph, the ratio d max /d min is upper bounded by (1 + γ)/(1 -γ). Moreover, since

D 1/2 1 = D 1/2 χ = u∈[2n] d u ,
from the denition of (2n, d, b, γ)-clustered graph, (4.6)

(1 -γ)2nd D 1/2 1 = D 1/2 χ (1 + γ)2nd .
In what follows we will also name ν the quantity

ν = 1 - 2b d ,
since it will appear several times in the remainder of this section. 9

Conductance and Cheeger's inequalities. Cheeger's inequalities are a key result in spectral graph theory, relating the second eigenvalue of N to the conductance Φ of a graph G (see Denition 2.3). In particular, we will make use of the following version of them.

Theorem 4.4 ([21, 22, 39]). Let G = (V, E) be a graph. Then (4.7)

Φ 2 2 1 -λ 2 2Φ .
Roadmap of Section 4. The rest of this section in organized as follows: In Subsection 4.1 we show that the Averaging dynamics produces a weak reconstruction for the family of (2n, d, b, γ)-clustered graphs (see Theorem 4.7). In Subsection 4.2 we show that graphs sampled according to the stochastic block model G 2n,p,q belong to the above family, w.h.p., for large ranges of the parameters p and q (see Theorem 4.10). In Section 4.3 we provide an ad-hoc analysis for G 2n,p,q over a parameter range that matches the weak reconstruction threshold (up to a constant factor) in the case of logarithmic node degree (see Theorem 4.12).

Analysis of the Averaging dynamics on almost-regular clustered

graphs. In this subsection, we generalize (3.1) to (2n, d, b, γ)-clustered graphs, showing that for this class, x (t) is still close to a linear combination of 1 and χ. This is the key ingredient to prove weak reconstruction for this class (see Theorem 4.7).

Dierently from the regular case, however, the partition indicator vector χ no longer is an eigenvector of P . As a consequence, the argument needed to prove the above result is considerably harder than in the regular case. In the following Lemma 4.5 we prove that D 1/2 χ is close to its projection on w 2 . We will use this fact in Lemma 4.6, to prove that χ is close to its projection on the second eigenvector v 2 of P . 9 Recall from Fact 1 that λ 2 = ν in clustered regular graphs.

λ 3 < ν then D 1/2 χ -β 2 w 2 52 γ ν -λ 3 √ 2nd ,
where β 2 = χ D 1/2 w 2 is the length of D 1/2 χ's projection onto w 2 .

Proof. For every node v, we denote by a v and b v the numbers of v's neighbors in its own cluster and in the other cluster, respectively, so that its degree is

d v = a v + b v .
From the denition of (2n, d, b, γ)-clustered graphs, we know that

(1 -γ)d d v (1 + γ)d and b -γd b v b + γd .
Then, for any node v, we get

(4.8) |a v -b v -νd v | = 2b d v d -2b v |2b(1 + γ) -2(b -γd)| 4γd .
Using the above inequality, we obtain

Aχ -νDχ 2 = v∈[2n]   w∈Neigh(v) χ(w) -νd v χ(v)   2 = v∈[2n] (a v χ(v) -b v χ(v) -νd v χ(v)) 2 = v∈[2n] (a v -b v -νd v ) 2 (from (4.8))
32nd 2 γ 2 .

(4.9) Thus,

N D 1/2 χ -νD 1/2 χ = D -1/2 Aχ -νD 1/2 χ = D -1/2 (Aχ -νDχ) D -1/2
|1 Dχ| = v∈[2n] χ(v)d v (1 + γ)dn -(1 -γ)dn = 2nd γ .
Hence, if we name y the component of D 1/2 χ orthogonal to the rst eigenvector, we can write (4.12)

D 1/2 χ = 1 Dχ D 1/2 1 2 D 1/2 1 + y .
From (4.12) and triangle inequality we get

D 1/2 χ -β 2 w 2 = 1 Dχ D 1/2 1 2 D 1/2 1 + y -β 2 w 2 |1 Dχ| D 1/2 1 + y -β 2 w 2 . (4.13)
As for the rst term in (4.13), from (4.11) and the lower bound on D where the second inequality above holds since γ 1/10.

Then N y -νy = N D 1/2 χ - 1 Dχ D 1/2 1 2 D 1/2 1 -ν D 1/2 χ - 1 Dχ D 1/2 1 2 D 1/2 1 N D 1/2 χ -νD 1/2 χ + |1 Dχ| D 1/2 1 2 N D 1/2 1 -νD 1/2 1 = N D 1/2 χ -νD 1/2 χ + |1 Dχ| D 1/2 1 2b d 8 √ 2nd γ + 4 √ 2nd γ , (4.16)
where: in the rst equality we used (4.12), in the second inequality we used the triangular inequality, the third equality follows by the denition of ν, and in the last inequality we used (4.10), (4.14), and (4.15).

We can now bound y as follows.

y D 1/2 χ - 1 Dχ D 1/2 1 (1 -γ) √ 2nd -2γ √ 2nd = (1 -3γ) √ 2nd > (1/2) √ 2nd , (4.17)
where: in the rst equality we used (4.12) and the triangular inequality, in the second inequality we used (4.6) and (4.14), while the fourth inequality follows from the hypothesis γ 1/10. Now, let us write y as a linear combination of the orthonormal eigenvectors of N

y = β 2 w 2 + • • • + β 2n w 2n
(recall that y w 1 = 0 by denition of y in (4.12)). By comparing (4.16) and (4.17),

(4.18) (24γ) 2 y 2 N y -νy 2 = 2n i=2 (λ i -ν)β i w i 2 = 2n i=2 (λ i -ν) 2 β 2 i .
Moreover, from the hypothesis λ 3 < ν,

(4.19) 2n i=2 (λ i -ν) 2 β 2 i 2n i=3 (λ i -ν) 2 β 2 i (λ 3 -ν) 2 2n i=3 β 2 i = (λ 3 -ν) 2 y -β 2 w 2 2 .
Thus, by combining (4.18) and (4. [START_REF] Brito | Recovery and rigidity in a regular stochastic block model[END_REF]), (4.20)

y -β 2 w 2 24 γ ν -λ 3 y , where β 2 = y w 2 = D 1/2 χ w 2 .
Then, since y is the projection of D

1 2 χ on D 1 2 1, (4.21)
y D

1 2 χ 2 √ 2nd .
Finally, from (4.13),

D 1/2 χ -β 2 w 2 |1 Dχ| D 1/2 1 + y -β 2 w 2 4γ √ 2nd + 24 γ ν -λ 3 y 4 γ √ 2nd + 48 γ ν -λ 3 √ 2nd 52 γ ν -λ 3 √ 2nd ,
where the second inequality follows from (4.14) and (4.20), in the third inequality we use (4.21), and the last inequality follows since ν -λ 3 < 2.

The next lemma essentially states that the second eigenvector v 2 of P is almost parallel to χ, up to an additive error which is comparatively small in norm. Lemma 4.6. Let G be a connected (2n, d, b, γ)-clustered graph with γ 1/10 and let x = i αi v i be the decomposition of an arbitrary initial vector x, according to the basis {v i } i of eigenvectors of the transition matrix P . If λ < ν then

α2 v 2 = α 2 (χ + z) ,
where we set

α 2 = α2 β 2 = w 2 D 1/2 x w 2 D 1/2 χ , and z 104 γ ν -λ 3 √ 2n .
Proof. We can write

α2 v 2 = α2 β 2 β 2 v 2 = α2 β 2 (χ + (β 2 v 2 -χ)) = α 2 (χ + z) with z = β 2 v 2 -χ.
As for the norm of z observe that

D 1/2 z = β 2 D 1/2 v 2 -D 1/2 χ = β 2 w 2 -D 1/2 χ .
Thus, from Lemma 4.5

z = D -1/2 D 1/2 z D -1/2 • D 1/2 z 2 √ d • 52 γ ν -λ 3 √ 2nd = 104 γ ν -λ 3 √ 2n .
The above lemma allows us to generalize our approach to achieve ecient, weak reconstruction in clustered, almost regular graphs. Proof. From (4.3) in Lemma 4.1

x (t-1) (u) -x (t) (u) = α2 λ t-1 2 (1 -λ 2 )v 2 (u) + e (t-1) (u) -e (t) (u) = α 2 λ t-1 2 (1 -λ 2 ) (χ(u) + z(u)) + e (t-1) (u) -e (t) (u),
where the second equality follows from Lemma 4.6. Corollary 4.2 (in particular, (4.5))

implies that, for every initial state x such that α2 = 0 and for every node u such that v 2 (u) = 0,

(4.23) sgn x (t-1) (u) -x (t) (u) = sgn (α 2 v 2 (u)) , whenever t -1 log 2 √ 2n(1+γ)/(1-γ) | α2|•|v2(u)|(1-λ2) log(λ 2 /λ) .
We next prove the following three claims:

1. For constant ĉ = 208γ ν-λ3 2 < 1, a subset S of
S = {u ∈ V : |z(u)| < 1 -ε}, for some 0 < ε < 1/2, and h = |V \ S| we get (1 -ε) 2 h z 2 2c 2 n .
Thus, h 2ĉn, where

ĉ = c2 (1 -ε) 2 = 112γ (1 -ε)(ν -λ 3 ) 2 208γ ν -λ 3 2 . Finally, observe that |β 2 v 2 (u) -z(u)| = 1 for all nodes u, since β 2 v 2 = χ + z. Hence, |β 2 v 2 (u)| > ε for each node u with |z(u)| < 1 -ε.
Thus, for all nodes u ∈ S, 10 Consistently, Theorem 3.3 is a special case of this one when γ = 0.

(a) |v 2 (u)| ε |β2| ε √ (1+γ)2nd = ε √ 2nd , where ε = ε/ √ 1 + γ < ε 1/2. (b) sgn ( α2 v 2 (u)) = sgn (α 2 (χ(u) + z(u))) = sgn (α 2 ) sgn (χ(u))
where in the rst equality we used Lemma 4.6 and in the second one the fact that |z(u)| 1 -ε < 1.

Proof of Claim 2. We rely on Lemma B.

(1+γ)(2-ε) (1-γ)ε , k = 1/(1-ĉ), km = 2n,
and δ = 1-ĉ 2n . We then obtain

P | (1/ √ km)y, x | δ = P | y, x | 1 - ĉ 2n 2n 1 -ĉ = P (| y, x | 1) 2k π • δ r + 4c √ m = O 1 d √ n + O 1 n = O 1 √ n .
Next, we have:

|α 2 | = |v 2 Dx| = |(χ + z) Dx| |β 2 | ,
where the rst equality follows from Claim 1 of Lemma 4.1, while the second equality follows from (4.22). As for β 2 , recall that

|β 2 | = |w 2 D 1/2 χ| D 1/2 χ = 2n i=1 d i (1 + γ)nd,
where the second step follows from Cauchy inequality and w 2 = 1, while the last inequality follows from the denition of (2n, d, b, γ)-clustered graphs. As a consequence, we have

|α 2 | 1 √ (1+γ)nd
, w.h.p. over the randomness of x.

Proof of Claim 3. The third claim follows directly from Cheeger's inequalities and connectedness of the graph. In particular, from (4.7) we have 1 -λ 2 Φ 2 2 . Connect- edness in turn implies that, for every subset S of the vertices, the corresponding cut is crossed by at least one edge, so that its conductance is at least 1/vol(S). These considerations immediately imply that φ G

1 (1+γ)dn , whenever G is (2n, d, b, γ)-clustered.
This proves the third claim and thus the theorem.

Finally, observe that we can perform the same analysis of the communication cost we made in the proof of Theorem 3.3, thus leading to the same bounds.

Roughly speaking, the above theorem states that the quality of block reconstruction depends on the regularity of the graph (through the parameter γ) and conductance within each community (here represented by the dierence |ν -λ 3 |). In what follows, we will often use the following parameters of the model: expected inner degree a = pn , expected outer degree b = qn, and d = a + b .

We need two preliminary lemmas. In the rst one, since G is not regular and random, we derive some spectral properties of its adjacency matrix A by considering a more tractable matrix, namely the expected matrix (4.24)

B = E [A] = pJ qJ qJ pJ ,
where J is the matrix with all entries equal to 1, so B i,j is the probability that the edge (i, j) exists in a random graph G ∼ G 2n,p,q . The matrix B has a very simple spectral structure, summarized in the following fact, which will be useful in the following.

Fact 2. If B is dened as in (4.24), then 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 detail, the rst lemma claims that G is likely to have an adjacency matrix A close to B in spectral norm.

Lemma 4.8. Let A be the adjacency matrix of a random graph sampled from G 2n,p,q with d > 5 log n. Then there is a large enough absolute constant c 1 > 0 such that, w.h.p.,

A -B c 1 √ d .
Proof. The lemma directly follows from Theorem 2.1 in [START_REF] Le | Concentration and regularization of random graphs[END_REF] with d = 2d and the observation that, from the Cherno bounds, all degrees are smaller than 2d, w.h.p.

The second lemma states that every clustered graph whose adjacency matrix is close to B has the properties required in the analysis of the Averaging dynamics. Lemma 4.9. Let G be a (2n, d, b, γ)-clustered graph such that: (i) ν = 1 -2b/d > 12γ and (ii) the adjacency matrix A of G satises A -B γd. Then λ 4γ and λ 2 2λ 2λ 3 .

Proof. Recall Fact 2. 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 dN -A 3γd. To show that dN approximates A we need to prove that D approximates dI. The condition on the degrees immediately gives us D -dI γd. Since every vertex v has degree d v in the range d ± γd, the square root

√ d v must be in the range [ √ d -γ √ d, √ d + γ √ d]
, so we also have the spectral bound:

(4.25) D 1/2 - √ dI γ √ d .
We know that D d + γd < 2d and that N = 1, so from (4.25)

A -dN = D 1/2 N D 1/2 -dN D 1/2 N D 1/2 - √ dN D 1/2 + √ dN D 1/2 -dN = (D 1/2 - √ dI) • N D 1/2 + √ dN • (D 1/2 - √ dI) D 1/2 - √ dI • N • D 1/2 + √ d • N • D 1/2 - √ dI 3γd .
|λ i | = |λ i -0| N -(1/d)B
4γ, for every i ∈ {3, . . . , 2n} .

Similarly, from the fact that the second eigenvalue of

(1/d)B is ν = 1 -2b/d, (4.29) |λ 2 -ν| N -(1/d)B 4γ .
Now, (4.28) and (4.29) imply that λ 4γ and λ 2 ν -4γ, respectively. The thesis then follows from the hypothesis ν > 12γ.

We can now prove the main result of this subsection. (1 + δ)λ 3 with δ = 1. Given the hypotheses on a and b, we also have that the graph is connected, w.h.p. Moreover, from the hypothesis of the corollary, dν = a -b > 1368

√ d log n. Hence, γ ν -λ 3 = dγ dν -dλ 3 < 6 √ d log n 1368 √ d log n -24 √ d log n = 1 224
, O(log n) rounds, w.h.p.

where
To achieve this improved analysis, we rst show, in Lemma 4.13 that, under the assumptions of the above theorem, w.h.p

N -B/d O 1 √ d ,
where we recall: B is the expectation of the adjacency matrix

A of G ∼ G 2n, a n , b n and N = D -1/2 AD -1/2
is the normalized adjacency matrix.

As discussed in the previous section, the matrix B has only two non-zero eigenvalues, d and a -b, and the eigenvector of the second eigenvalue is the indicator of the cut. In Lemma 4.15 we use the Davis-Kahan theorem (see Theorem A.4) to argue that, if the distance between N and B/d in spectral norm is smaller than (a -b)/d, then there is a gap between the second and the third eigenvalues of N , and the eigenvector of the second eigenvalue of N is close to the indicator of the cut. Finally, we show that these spectral conditions on N suce for the Averaging dynamics to achieve weak reconstruction, thus proving Theorem 4.12. In Proof. We rst remark that each degree d v 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

d v has expectation E [d v ] d and variance Var (d v ) d.
Let e u,v be the binary random variable that is 1 i the edge (u, v) is included in the graph and dene also d

(u) v
as the sum of all random variables e v,v incident on v except for e v,u .

As for the sum of the variables We will next prove that, w.h.p., (4.32)

√ d - √ d v 2 , v∈V √ d -d v 2 = 2dn + v∈V d v -2 √ d • v∈V d v .
v∈V d v 2n √ d -2 n √ d .
Observe that, by using (4.31) and (4.32) in (4.30),

v∈V √ d -d v 2 5n ,
which concludes the proof of the lemma. So, we will now prove that (4.32) holds (w.h.p.). Observe that if x 0, then

√ x 1 + x -1 2 - (x -1) 2 2 so that if X is a non-negative random variable of expectation 1 then 12 E √ X 1 - Var (X) 2 .
By applying the above inequality to d v /d we get

E d v d 1 - Var dv d 2 = 1 - Var (d v ) 2d 2 1 - 1 2d and (4.33) E d v √ d - 1 2 √ d .
We will now show that v∈V √ d v is concentrated around its expectation by using Chebyshev's inequality [START_REF] Berry | The accuracy of the gaussian approximation to the sum of independent variates[END_REF] . In order to do that, we will bound their covariance as

E d v d u -E d v E d u 8d 2 n .
With a slight abuse of notation, in what follows we use P (e v,u ) to denote P (e v,u = 1).

By the law of total probability

E d v = P (e v,u ) E d (u) v + 1 + (1 -P (e v,u ))E d (u) v and E √ dudv = P (ev,u) E d (u) v + 1 E d (v) u + 1 + (1 -P (ev,u))E d (v) u E d (u) v
.

Then the last two equations above imply that

E √ dvdu -E √ dv E √ du = P (ev,u) E d (u) v + 1 E d (v) u + 1 + (1 -P (ev,u))E d (v) u E d (u) v -P (ev,u) 2 E d (v) u + 1 E d (u) v + 1 -P (ev,u) (1 -P (ev,u))E d (v) u E d (u) v + 1 -P (ev,u) (1 -P (ev,u))E d (v) u + 1 E d (u) v -(1 -P (ev,u)) 2 E d (v) u E d (u) v p(1 -p) E d (u) v + 1 E d (v) u + 1 + E d (v) u E d (u) v 4d 2 n , (4.34)
where in the last inequality we used that E d

(u) v + 1 < √ 2d,
P v∈V d v < 2n √ d -2 n √ d P v∈V d v -E v∈V d v > n √ d = O 1 n 1/4 .
We now can prove Lemma 4.13.

Proof of Lemma 4.13. The main idea is to use the triangle inequality to upper bound N -B/d in terms of A -B and B -dD -1/2 BD -1/2 . The former can be bounded with Lemma 4.8 while the latter can be bounded by bounding

√ d1-D 1/2 1
and √ dχ -D 1/2 χ using Lemma 4.14.

We rst write (4.36)

N -B/d N -D -1 2 BD -1 2 + D -1 2 BD -1 2 -B/d .
We can bound the rst term on the right-hand side as

N -D -1 2 BD -1 2 = D -1 2 (A -B)D -1 2 D -1 2 • A -B • D - 1 2 . (4.37)
A simple application of the Cherno bound and the union bound shows that w.h.p.

D -1/2 2 d . (4.38)
Indeed, by denition D -1/2 = 1/ min i { √ d i }. For every i = 1, . . . , 2n, E [d i ] = d. Therefore, from the Lemma's hypothesis that d > 9 log n and from the fact that the edges are generated independently, a straightforward application of Cherno 's bounds yields:

P d i < d 2 e -d 8 1 n 9/8 .
Applying a union bound on the nodes yields (4.38).

The assumptions of the lemma together with Lemma 4.8 imply that

A -B O( √ d) .
By applying the above bound and (4.38) in (4.37), we conclude

N -D -1 2 BD -1 2 O 1 √ d .
Regarding the second error term in (4.36), we write

D -1 2 BD -1 2 -B/d D -1 2 BD -1 2 -D -1 2 B √ d + D -1 2 B √ d -B/d = D -1 2 B - B √ d D 1 2 D -1 2 + 1 √ d D -1 2 B -D 1 2 B √ d D -1 2 2 • B - B √ d D 1 2 + D -1 2 √ d • B -D 1 2 B √ d O 1 d • B -D 1 2 B √ d , (4.39)
where, in the second-to-last step we used the fact that M = M for every matrix M and the fact that B is symmetric. The last step holds w.h.p.

Recall that

B = d 2n 11 + a -b 2n χχ . So B -D 1 2 B √ d d 2n 11 - √ dD 1 2 2n 11 + a -b 2n χχ - (a -b)D 1 2 2n √ d χχ = √ d 2n ( √ d1 -D 1 2 1)1 + a -b 2n √ d ( √ dχ -D 1 2 χ)χ √ d 2n √ d1 -D 1 2 1 • 1 + √ d 2n √ dχ -D 1 2 χ • χ O( √ d) , (4.40)
where the last step holds w.h.p. and uses the fact that, under our assumptions, Lemma 4.14 implies that w.h.p.

i ( √ d -d i ) 2 O(n) .
Then, for any vector

x ∈ {±1} n , √ dx -D 1 2 x 2 = i (x i √ d -x i √ d i ) 2 = i x 2 i ( √ d -d i ) 2 O(n) , so that √ d1 -D 1 2 1 = | √ dχ -D 1 2 χ = O( √ n) .
From (4.39) and (4.40) it follows that

D -1 2 BD -1 2 -B/d O 1 √ d ,
which concludes the proof.

N τ = (D + τ I) -1 2 A τ (D + τ I) -1 2
be the normalized version of the modied adjacency matrix, and let B τ be the expectation of the modied adjacency matrix

B τ = B + τ 2n J .
Then, with constant probability,

N τ - 1 d + τ B τ O 1 √ d ,
even when a, b, and d are constants. Our Lemma 4.13 above shows that when d is at least order of log n, then the above bound holds without correction, for τ = 0. It would also be possible to modify the proof of Le and Vershynin to work for τ = 0 in the regime of logarithmic or higher degree. Such a proof would be similar to our argument above, but instead of a straightforward reduction to bounding

i ( √ d - √ d i ) 2 , which
requires some work, one would derive a somewhat more complicated reduction to the easier task of bounding

i (d -d i ) 2 .

√

d, where c 2 is the constant of Lemma 4.13. Consider the normalized adjacency matrix N of G. 14 Then the following properties hold w.h.p.:

1. λ 2 1 -2b d -c1 √ d ; 2. λ 2 2λ; 3. A subset of nodes S exists with |S| = 2n 1 -200 2 • (4c 2 + 4) • √ d a-b such that, for every u ∈ S, | √ 2nd(D -1/2 w 2 )(u) -χ(u)| 1 100 . Proof. Recall that B/d is such that its largest eigenvalue is 1, its second largest is (a -b)/d = 1 -2b/d,

√

d. As for the third claim, let us write w 2 = w + w χ + w ⊥ where w and w χ are the projections of w 2 onto 1 and χ respectively, and w ⊥ is the projection of w 2 onto the subspace orthogonal to 1 and χ. We are going to argue that w 2 is close to w χ and hence to χ.

First let us see that w is small. We know that w 2 , D 1/2 1 = 0, thus

w = 1 √ 2n | w 2 , 1 √ d √ d - 1 √ d D 1 2 1 | 1 √ 2nd w 2 1 √ d -D 1 2 1 5 2d 2 √ d ,
where in the second-to-last inequality we used Lemma 4.14.

From (4.41) and the denition of spectral norm,

w 2 N w 2 -w 2 B d w 2 c 2 √ d .
Now let us compute the two quadratic forms in the above expression. We can write

w 2 N w 2 = λ 2 a -b d - c 2 √ d
14 Please refer to the beginning of Section 4 for denition and notation.

w 2 B d w 2 = w 2 + a -b d w χ 2 and, putting it all together, a -b d w χ 2 a -b d -2 c 2 √ d - 2 √ d = a -b -(2c 2 + 2) √ d d , which gives w χ 2 a -b -(2c 2 + 2) √ d a -b = 1 - (2c 2 + 2) √ d a -b . Moreover, (4.42)
w 2 , χ √ 2n = w χ w χ 2 1 - (2c 2 + 2) √ d a -b ,
where we used the fact that w χ 1.

We are now able to bound the distance between w 2 and χ/ √ 2n:

w 2 - 1 √ 2n χ 2 = w 2 2 + 1 √ 2n χ 2 -2 w 2 , 1 √ 2n χ = 2 -2 w χ (4c 2 + 4) √ d a -b , (4.43)
where in the last inequality we used (4.42).

We now dene the set O of outlier nodes u such that

w 2 - 1 √ 2n χ 2 (4c 2 + 4) √ d a b , it follows that |O| 2n • 200 2 • (4c 2 + 4) √ d a -b .
Notice that, from the Cherno bound, w.h.p.

d/d u = 1 ± 1/200, for each u ∈ V . Thus, (4.44) and the last fact imply that, for each u ∈ S = V \ O, w.h.p.

√ 2ndD -1 2 w 2 (u) -χ(u) 1 100 ,
and the third claim of Lemma 4.15 is proved.

We are now ready to show that the Averaging dynamics achieves weak reconstruction when a -b √ d.

Proof of Theorem 4.12. The proof proceeds along the same lines as the one of Theorem 4.7. To begin, recall (4.3) from Lemma 4.1:

x (t-1) (u) -x (t) (u) = α2 λ t-1 2 (1 -λ 2 )v 2 (u) + e (t-1) (u) -e (t) (u).
Moreover, Corollary 4.2 (in particular, (4.5)) ensures that, if α2 = 0, for every u ∈ V such that v 2 (u) = 0,

sgn(x (t-1) (u) -

x (t) (u)) = sgn(α 2 v 2 (u)) , whenever t -1 log 2 √ 2ndmax/dmin | α2|•|v2(u)|(1-λ2) log(λ 2 /λ) .
We next prove the following three claims:

1. Set ĉ = 200 2 • (4c 2 + 4) • √ d a-b ,
(α 2 v 2 (u)) = sgn (α 2 ) sgn (χ) . 2. |α 2 | 1 √ 2nd , w.h.p.
Thus, for the subset S in the previous claim the Averaging protocol produces the right reconstruction.

-ĉ)n entries i of v 2 , | √ 2nd v 2 (i) -χ(i)| 1 100 ,
for a suitable constant ĉ < 1. This is equivalent to:

v 2 (i) 99 100 √ 2nd if i ∈ V 1 ∩ S and v 2 (i) - 99 100 √ 2nd if i ∈ V 2 ∩ S .
This proves Claim 1.

Proof of Claim 2. To begin, recall that α2 =

w 2 D 1/2 x from Claim 1 of Lemma 4.1. Let y = √ 2ndD 1/2 w 2 = √ 2ndDv 2
for the remainder of this proof, so that

|α 2 | = 1 √ 2nd |y x| .
Then, recall that, for every i ∈ S,

| √ 2nd v 2 (i) -χ(i)| 1 100
.

When i ∈ V 1 ∩ S this
(1 + α)d, i ∈ V 1 ∩ S, -101 100 (1 + α)d y(i) -99 100 (1 -α)d, i ∈ V 2 ∩ S .
We can now apply Lemma B. . Then

P |(1/ √ 2n)y x| 1 √ 2n = P |(1/ √ km)y x| δ 2k π • δ r + 4c √ m = O 1 √ n .
Proof of Claim 3. We begin by noting that, from our hypotheses, G is connected w.h.p. In particular, each community induces a random graph with parameter p = a/n d/2n 1.5 log n/n, which is well above the connectivity threshold. Moreover, our assumptions on q imply that the expected number of edges connecting the two communities is at least log n, which in turn implies that at least one such edge will be present, w.h.p. Together, these arguments imply that G is connected, w.h.p.

Conditioned on this event, the third claim follows directly from Cheeger's inequalities.

In more detail, (4.7) implies 1-λ 2 Φ 2 2 . Connectedness in turn implies that, for every subset S of the vertices, the corresponding cut is crossed by at least one edge, so that its conductance is at least 1/vol(S). But vol(S) |S|•(|S|-1) < n 2 deterministically. This immediately implies 1 -λ 2 > 1 n 4 and thus Claim 3, which completes the proof.

Remark 3. After looking at Lemma 4.15, one may wonder whether it could be enough to generalize Denition 4.3 to include quasi-(2n, d, b, γ)-clustered graphs, that is, 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: These higherdegree nodes may connect to the other nodes in a way that would greatly perturb the eigenvalues and eigenvectors of the graph. In G 2n,p,q , besides the fact that there are few nodes with degree much larger than d, it is also crucial that they are connected in a non-adversarial way, that is, randomly.

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. We formally state the result in Theorem 5.2, and we give a proof in the following subsection.

Let G = (V, E) be a d-regular graph in which V is partitioned into k equal-sized communities V 1 , . . . , V k , while every node in V i has exactly a neighbors within V i and exactly b neighbors in each V j , for j = i. Note that d = a + (k -1) • b. We observe that the transition matrix P of the random walk on G has an eigenvalue 1 -kb/d with multiplicity at least k -1, since all stepwise vectors that are constant within each community V i and whose entries sum to zero are eigenvectors of P with eigenvalue 1 -kb/d. Moreover, if

max{λ k+1 , |λ kn |} < (1 -ε) • 1 - kb d ,
then P has eigenvalues

λ 1 = 1, λ 2 = • • • = λ k = 1 - kb d ,
with all other eigenvalues strictly smaller by a (1 -ε) factor.

The properties discussed above can be leveraged to achieve strong reconstruction in the regular case we consider in this section. In more detail, let x ∈ R V be a vector. We say that a node v is of positive (respectively, negative ) type with respect to x if a threshold T = T (x, v) exists such that the value (P t x)(v) increases (respectively, decreases ) with t, for all t T . Note that, if x were orthogonal to the span of the rst k eigenvectors, we might in principle have nodes of neither type, because (P t x)(v) might not eventually become strictly monotone in t.15 However, if x is chosen uniformly at random, this is unlikely to happen. On the contrary (see Lemma 5.4), w.h.p. x has a suciently large component in the span of the rst k eigenvectors, so that for t max{T (x, v) : v ∈ V }, the vector P t x is nearly contained in the span of the rst k eigenvectors and thus, from the previous paragraphs, up to a small additive error, it can be expressed as a linear combination of vectors that are stepwise constant with respect to the communities. This implies that, for an initial vector x ∈ {-1, 1} |V | chosen uniformly at random, all nodes in the same community are of the same type, w.h.p. (see Lemma 5.4), while nodes from dierent communities are of dierent types, with probability γ (see Lemma 5.5), where γ > 0 is an absolute constant.

We thus consider the parallel procedure where each node initially chooses = Θ(log n) values independently and uniformly at random from {-1, 1} and, to each of them, applies an independent copy of the Averaging protocol in parallel.

In the proof of Theorem 5.2, we will prove that the arguments outlined above imply that, starting from the random initial vectors x 1 , . . . , x , each in {-1, 1} V , the parallel procedure has w.h.p. the following properties: i) every node is either of positive or negative type for each x i ; ii) if we associate a signature to each node, namely, the sequence of types, then nodes within the same V i exhibit the same signature, while nodes in dierent V i , V j have dierent signatures. 5.1. Averaging dynamics for k-clustered regular graphs. For n, d, k ∈ N, we say that a d-regular graph G with kn nodes is (kn, d, b)-regular if a k-partition of the nodes (V 1 , V 2 , . . . , V k ) exists such that, for every i = 1, . . . , k and every j = 1, . . . , k, every node in V i has exactly b neighbors in V j , if j = i, and thus exactly d -(k -1)b neighbors in V i . We name a = d -(k -1)b the inner degree of each node.

For a (kn, d, b)-regular graph G = (V, E) and k-partition (V 1 , . . . V k ) we say that a vector z = (z(u) : u ∈ V ) is stepwise if for every i = 1, . . . , k and for every u, v ∈ V i , z(u) = z(v). Notice that any stepwise vector z such that u∈V z(u) = 0 is an eigenvector of the transition matrix P with eigenvalue (a -b)/d = 1 -kb/d. Then, for = Θ(log n), the Averaging protocol with parallel runs produces a strong reconstruction within O(log n) rounds, w.h.p.

5.2. Proof of Theorem 5.2. We rst give a formal denition of the type of a node with respect to an initial vector x.

Definition 5.3. Let x ∈ R V be a vector. We say that a node v is of positive (respectively, negative) type with respect to x if a threshold T = T (x, v) ∈ N exists such that, for all t T , the value (P t x)(v) increases (respectively, decreases) with t.

From the spectral decomposition of P , it is easy to see that all nodes are either of positive or of negative type with respect to any vector x that is not orthogonal to the span of the rst k eigenvectors of P . In Lemmas 5.4 and 5.5 we show that, for an initial random vector x ∈ {-1, 1} kn , all nodes in the same community have the same type, w.h.p., while nodes in dierent communities have dierent types, with constant probability.

Lemma 5.4. For any i ∈ {1, . . . , k}, if the vector x ∈ {-1, 1} kn is chosen uniformly at random, then the nodes of V i are either all of positive type or all of negative type, w.h.p., with threshold T (x, v) 2 log(n)/ log(λ 2 /λ) for all v ∈ V i . Furthermore, the two events have equal probability.

Proof. We can decompose the vector x as

x = x 1 + x Vi + x ⊥i + x ⊥ ,
where x 1 is the component of x parallel to 1, x Vi is the component parallel to the vector 1 Vi -k -1 1, x ⊥i is the component in the eigenspace of λ 2 orthogonal to 1 Vik -1 1, and x ⊥ is the component orthogonal to 1 and to the eigenspace of λ 2 .

For the above to make sense, 1 Vi -k -1 1 must be an eigenvector of λ 2 , which is easily veried because its entries sum to zero and it is constant within components.

The reason for picking the above decomposition is that x ⊥i is zero in V i . Indeed, since x ⊥i is orthogonal to 1 and to 1 Vi -k -1 1, from x ⊥i , 1 = x ⊥i , 1 Vi -k -1 1 = 0 , it follows that x ⊥i , 1 Vi = 0. Thus, the entries of x ⊥i sum to zero within V i , but, being in the eigenspace of λ 2 , the entries of x ⊥i are constant within components, and so they must be all zero within V i . According to the above decomposition, we have that

P t x = x 1 + λ t 2 x Vi + λ t 2 x ⊥i + P t x ⊥ .
Hence, for each v ∈ V i , (5.1)

(P t+1 x)(v) -(P t x)(v) = λ t 2 • (1 -λ 2 )(x Vi )(v) + ((P t+1 -P t )x ⊥ )(v) .
For large enough t, that is, when λ t 2 > n 2 λ t (where λ = max{λ k+1 , |λ kn |}, as dened in the statement of Theorem 5.2), the hypothesis λ < (1 -ε)λ 2 implies that (5.2)

|(P t x ⊥ )(v)| P t x ⊥ ∞ P t x ⊥ λ t x ⊥ √ n • λ t 1 n 1.5 λ t 2 . Now observe that (5.3) 1 Vi -k -1 1 2 = u∈Vi 1 - 1 k 2 + u∈V \Vi 1 k 2 = k -1 k n = (1 -k -1
)n, whence:

(5.4)

x Vi = | x, 1 Vi -k -1 1 | 1 Vi -k -1 1 = 1 (1 -k -1 )n j∈Vi x(j) - j∈V x(j) k . Thus, for each v ∈ V i , |(x Vi )(v)| = | x, 1 Vi -k -1 1 | 1 Vi -k -1 1 • 1 -k -1 1 Vi -k -1 1 = 1 (1 -k -1 )n j∈Vi x(j) - j∈V x(j) k 1 -k -1 = 1 n j∈Vi x(j) - j∈V x(j) k = 1 -k -1 n x Vi ,
where in the second equality we used (5.3), and in the second-to-last and last steps we used (5.4). Moreover, observe that

x Vi = | x, 1 Vi -k -1 1 | 1 Vi -k -1 1 = 1 (1 -k -1 )n | x, 1 Vi -k -1 1 | = 1 √ kn x, 1 Vi -k -1 1 k -1 (1 -k -1 )
,

where in the second equality we used (5.3). If we let y =

1 V i -k -1 1 √ k -1 (1-k -1 )
, each entry of this vector is either

1 -k -1 k -1 (1 -k -1 ) = √ k -1 (this is the case for all nodes in V i ) or - k -1 k -1 (1 -k -1 ) = - 1 √ k -1 (this is the case for all nodes not in V i )
In particular, for every v,

1 √ k-1 |y(v)| √ k -1. Hence, by applying Lemma B.2 with m = n, r = 1 √ k-1 , c = k -1, and δ = 1 n , we get P x Vi 1 n = P 1 √ kn x, y 1 n 2k π • k -1 n + 4(k -1) √ n = O k √ n .
Hence, w.h.p.

(5.5)

|(x Vi )(v)| 1 -k -1 n 1 n = 1 -k -1 • 1 n .
Using (5.2) and (5.5) in (5.1), we get that (P t+1 x)(v) -(P t x)(v) has the same sign as (x Vi )(v), w.h.p., for all elements of V i simultaneously, and it is equally likely to be positive or negative.

Observe that the above lemma also holds for all i simultaneously, w.h.p., by a union bound.

Lemma 5.5. Let u, v be two nodes in two distinct communities. An absolute constant γ > 0 exists such that, if x ∈ {-1, 1} kn is chosen uniformly at random, then the types of u and v are dierent with probability at least γ and the threshold T = 2 log(n)/ log(λ 2 /λ).

Proof. Without loss of generality, assume u ∈ V 1 and v ∈ V 2 . This time we decompose x as follows

x = x 1 + x V1⊕2 + x V1 2 + x ⊥1,2 + x ⊥ , where • x 1 is the component parallel to 1, • x V1⊕2 is the component parallel to 1 V1 + 1 V2 -2 k 1, • x V1 2 is the component parallel to 1 V1 -1 V2 , • x ⊥1,2 is the component in the eigenspace of λ 2 orthogonal to x V1⊕2 and x V1 2 ,
• x ⊥ is the component of x orthogonal to all the above vectors (i.e., orthogonal to both the eigenspaces of λ 1 and λ 2 ). Similarly to the proof of Lemma 5.4, the important observations are that x V1⊕2 and x V1 2 are in the eigenspace of λ 2 , and that x ⊥1,2 is zero in all the coordinates of V 1 and of V 2 . Thus, for each v ∈ V 1 ∪ V 2 we have that (5.6)

(P t+1 x)(v) -(P t x)(v) = λ t 2 (1 -λ 2 )(x V1⊕2 + x V1 2 )(v) + ((P t+1 -P t )x ⊥ )(v) .
From (5.6) it is easy to see that, if the initial vector x is such that the two following conditions hold for every v ∈

V 1 ∪ V 2 , |(x V1⊕2 )(v)| 1 2 |(x V1 2 )(v)| and (5.7) |((P t+1 -P t )x ⊥ )(v)| 1 8 λ t 2 • (1 -λ 2 ) • |(x V1 2 )(v)| .
(5.8) then for such an initial vector x, all the elements in V 1 have the same type, all the elements of V 2 have the same type, and the two types are dierent. Now observe that

(x V1⊕2 )(v) = 1 2n i∈V1 x(i) + i∈V2 x(i) - 2 k i∈V x(i) (x V1 2 )(v) = 1 2n i∈V1 x(i) - i∈V2 x(i) .
Hence, if the initial vector x satises the following three conditions

2 √ n v∈V1 x(v) 3 √ n, (5.9) -2 √ n v∈V2 x(v) - 4 3
√ n , and

(5.10)

0 v∈V /(V1∪V2) x(v) 1 10
√ kn ,

(5.11)

then 2n(x V1⊕2 )(v) 5 3 √ n and 2n(x V1 2 )(v) 10 3
√ n, and we get (5.7). Finally, observe that, for an initial vector x ∈ {-1, 1} kn chosen uniformly at random, events (5.9), (5.10) and (5.11) are independent, and each one happens with constant probability. Thus, for such a random initial vector x, (5.7) holds with constant probability. Moreover, notice that if (5.7) holds then (5.8)

Follow-up and open questions. The contribution of this paper represents

a rst important step toward a rigorous understanding of the process yielded by an elementary local rule (that is, a dynamics) when it is applied over clustered networks. In particular, our analysis essentially shows that, in this setting, the averaging dynamics possesses a metastable regime where nodes' states well-reect the hidden communities of the network: interestingly enough, we also show that this property can be eciently exploited by a simple and local coloring criterion that allows fully decentralized community detection.

We believe that this contribution is important since it can provide reasonable models to study self-organizing properties observed in fully-decentralized Multi-Agent Systems having natural local interaction rules [START_REF] Cruciani | Phase transition of the 2choices dynamics on core-periphery networks[END_REF][START_REF] Cruciani | On the metastability of quadratic majority dynamics on clustered graphs and its biological implications[END_REF][START_REF] Kothapalli | On the analysis of a label propagation algorithm for community detection[END_REF]. In this setting, we emphasize three research directions that have been inspired by the conference version of our paper.

The rst one is to extend the analysis of the (synchronous) Averaging dynamics to more general graph classes and multiple, possibly non-balanced, communities. The general underlying question is whether the temporal evolution of the power method applied to an initial random vector may provide equivalent information as a spectral method, without requiring explicit eigenvector computations. A rst step in this direction was taken by Becchetti et al [START_REF] Becchetti | Step-by-step community detection in volume-regular graphs[END_REF], who extended the analysis presented in Section 5. In particular, they showed that a class of graphs exhibiting a milder form of regularity than the one considered here is the largest class of undirected, possibly weighted graphs that may contain k stepwise eigenvectors in the presence of a hidden k-partition. Graphs belonging to this class need not be regular in general, nor does the hidden partition need to be balanced. In this case, under suitable conditions, running multiple, parallel instances of the Averaging dynamics aords recovery of the hidden partition, w.h.p. These results use a connection between volume regularity and lumpability of Markov chains [START_REF] Tian | Lumpability and commutativity of Markov processes[END_REF]. At the same time, the analysis presented in [START_REF] Becchetti | Step-by-step community detection in volume-regular graphs[END_REF] highlights that simple, sign-like rules applied to the power method are unlikely to distill information equivalent to an explicit eigenvector computation. Apparently, a more sophisticated approach is needed.

The second line of research concerns the analysis of suitable versions of the averaging dynamics that work in well-established asynchronous, sparsied communication models. Indeed, in the Averaging dynamics considered in this paper, every node communicates in parallel with all its neighbors at each round. While this might be too expensive in scenarios characterized by dense topologies, it is simply infeasible in other settings (for instance, the latter is the case when links represent sporadic opportunistic meetings that occur asynchronously). Motivated by the above considerations, a rst line of follow-up work considered sparsied, asynchronous variants of the Averaging protocol that work on the well-known Population Protocol model [START_REF] Becchetti | Average whenever you meet: Opportunistic protocols for community detection[END_REF][START_REF] Mallmann-Trenn | Eigenvector computation and community detection in asynchronous gossip models[END_REF][START_REF] Sun | Distributed graph clustering and sparsication[END_REF]. In the latter model, at every round, the end-points of (only) one method for principal components analysis [START_REF] Oja | Simplied neuron model as a principal component analyzer[END_REF], to derive some asynchronous protocols that approximate the k largest eigenvectors of a graph. Then, they use them to dene a more complex version of the Averaging protocol that gets weak reconstruction over clustered graphs including the G 2n,p,q model for a wide range of parameters p and q.

According to the aim of sparsication discussed above, in [START_REF] Sun | Distributed graph clustering and sparsication[END_REF], Sun and Zanetti propose a distributed synchronous algorithm that takes a clustered graph as input and constructs a static, sparse random subgraph that, under some spectral conditions of the original graph (satised by the stochastic block model), preserves the original community structure. Then they apply a suitable averaging protocol on the output subgraph. The resulting protocol works even in the case of more communities and returns a weak reconstruction within O(polylogn) time and work per-node.

Another interesting direction inspired by our work is the rigorous analysis of well-16 Notice that the opportunistic communication model is sequential so a meaningful comparison with our parallel, synchronous model requires dividing the time bound by a factor of n.

known (non-linear) dynamics based on majority rules, when applied to graphs that exhibit community structure. In [START_REF] Cruciani | Phase transition of the 2choices dynamics on core-periphery networks[END_REF], Cruciani et al. consider the 2-Choices dynamics where, at each round, every node picks two random neighbors and updates its value to the most frequent among its value and those held by its sampled neighbors. They show that if the underlying graph has a suitable core-periphery structure and the process starts in a suitable random conguration, the system reaches a metastable regime that reects the underlying community structure. Similar results have subsequently been obtained for regular clustered graphs with dense communities in [START_REF] Cruciani | On the metastability of quadratic majority dynamics on clustered graphs and its biological implications[END_REF].

Very recently, Shimizu and Takeharu Shiraga [START_REF] Shimizu | Phase Transitions of Best-of-Two and Best-of-Three on Stochastic Block Models[END_REF] consider the 2-Choices and another simple majority dynamics on G 2n,p,q and their ability to compute majority consensus.

In short, they show that this ability undergoes a phase transition depending on the ratio q/p. One major question left open by the above works on non-linear majority dynamics is whether they can be used to get ecient community detection on G 2n,p,q .

Lemma B.1. Let y ∈ {-1, 1} 2n an arbitrary vector with ±1 entries. If we pick x uniformly at random in {-1, 1} 2n then, for any δ > 0,

P (1/ √ 2n) x y δ O(δ) .
Proof. Since x is a vector of independent and uniformly distributed random variables in {-1, 1}, x y is distributed according to a sum of 2n Rademacher random variables. Such a sum takes value 2k -2n with probability 1 Although it is possible to argue that a Rademacher vector has Ω(1) probability of having inner product Ω( y ) with every vector y, such a statement does not hold w.h.p. We do, however, have estimates of the inner product of a vector y with a Rademacher vector x provided that y is close to a vector in {-1, 1} 2n . Lemma B.2. Let k, m ∈ N be two integers and let y be an mk-dimensional vector with real entries. Given two positive real numbers r and c, let S be the subset of coordinates of y whose absolute value is between r and cr, i.e., S = {i ∈ {1, . . . , km} : r |y(i)| cr} .

If |S| m and we pick x uniformly at random in {-1, 1} km , then for every δ > 0

P (1/ √ km) x y δ 2k π • δ r + 4c √ m .
Proof. Let T = {1, . . . , km} -S. In the remainder of this proof, the restriction of x to entries in T will be denoted by x T . Clearly, x T is independent of x(i) for every i ∈ S. Next, we apply the Berry-Esseen theorem A.3, with X i = x(i)y(i), for every i ∈ S. In particular, our hypotheses on y and the fact the the x(i)'s are Rademacher random variables imply: i) E [X i ] = 0, ii) σ 2 i = y(i) where g is a Gaussian random variable of mean 0 and variance σ 2 . Finally:

P -t -δ √ km g -t + δ √ km = 1 √ 2σ 2 π -t+δ √ km -t-δ √ km e -s 2 2σ 2 ds 2δ √ km √ 2πr 2 m = 2k π • δ r ,
where we used the fact that e -s 2 /2σ 2 1 for all s. This concludes the proof. 17 In the following, we use the fact that the constant C 0 > 0 that appears in the claim of Theorem A.3 is less than 2 (see [START_REF] Berry | The accuracy of the gaussian approximation to the sum of independent variates[END_REF]).

  protocol produces a strong reconstruction of the two clusters, w.h.p. By a wellclustered graph we mean a (2n, d, b)-regular graph where (V 1 , V 2 ) represents the unique smallest cut. Definition 3.1 (Clustered regular graphs). A (2n, d, b)-clustered regular graph

(

  2n, d, b)-clustered regular graph with λ 2 = 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. Moreover, the overall number of messages produced by the protocol (until its completion time) is O(m log n) (where m = |E|), and each message has size Θ(log n), w.h.p.

  , d, b)-clustered regular graph and let λ A = max {λ 2 (A 1 ), λ 2 (A 2 )}, where A 1 and A 2 are the adjacency matrices of the subgraphs induced by V 1 and V 2 , respectively. If a-b (1+δ)(λ A +b) then G satises the hypothesis of Theorem 3.3.

Remark 1 .

 1 While we dened (2n, d, b)-clustered regular graphs as simple graphs, Denition 3.1 could be easily extended to include regular multigraphs, where regularity clearly refers to the standard denition of multiedges. Then Theorem 3.3 holds for this class of multigraphs as well.3.1. Regular stochastic block model. We can use Theorem 3.3 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:

Lemma 3 . 5 .

 35 Let G be a graph sampled from the regular stochastic block model with internal and external degrees a and b, respectively, such that a -b > 2 √ a + b + o(1).

Corollary 3 . 6 .

 36 Let η be an arbitrary positive constant and let G be a random graph sampled from the regular stochastic block model with the parameters a and b such that a -b > 2(1 + η) √ a + b. Then the Averaging protocol produces a strong reconstruction in O(log n) rounds, w.h.p.

Lemma 4 . 5 .

 45 Let G be a connected (2n, d, b, γ)-clustered graph with γ 1/10. If

Theorem 4 . 7 (

 47 Weak reconstruction). Let G be a connected (2n, d, b, γ)-clustered graph such that: γ (ν -λ 3 )/208, λ < ν, and λ 2 (1 + δ)λ for an arbitrarily small constant δ > 0. Then the Averaging protocol produces an O(γ 2 /(ν -λ 3 ) 2 )weak reconstruction within O(log n) rounds, w.h.p. 10 Moreover, the overall number of messages exchanged by the protocol (until its completion time) is O(m log n) and each message has size Θ(log n), w.h.p.

2 .

 2 In detail, we apply Lemma B.2 with y = D(χ + z) = β 2 Dv 2 . By denition of S in the proof of the previous claim, |y(u)| = |D(χ + z)(u)| εd u for all u ∈ S, since |z(u)| 1 -ε. For the same reason, we have |y(u)| (2 -ε)d u . These considerations and the fact that G is a (2n, d, b, γ)-clustered graph (see Denition 4.3) imply that, for every u ∈ S we have (1 -γ)εd |y(u)| (1+γ)(2-ε)d. So, we can apply Lemma B.2 with the following setting: y = D(χ+z), S is dened as in Claim 1 above, r = (1-γ)εd, c =

(4. 26 )

 26 By using the triangle inequality and (4.26), (4.27) N -(1/d)B N -(1/d)A + (1/d) • A -B 4γ . Finally, we use Theorem A.2 (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 (4.27) and Fact 2, (4.28)

Theorem 4 .

 4 [START_REF] Becchetti | Find your place: Simple distributed algorithms for community detection[END_REF]. Let G ∼ G 2n,p,q with a -b > 72 √ d log n. Then w.h.p.: i) G is (2n, d, b, 6 log n/d)-clustered, and ii) λ min λ 2 /2 , 24 log n/d . Proof. From the hypothesis d > a-b > 72 2 log n, we get Claim (i) (with probability at least 1 -n -1 ) from an easy application of the Cherno bound with any degree deviation γ 6 (log n)/d. As for Claim (ii), the hypothesis above and Lemma 4.8 allow 11 to apply Lemma 4.9 with γ = 6 (log n)/d. This implies that λ 24 (log n)/d and, moreover, λ λ 2 /2.By combining Theorem 4.10 and Theorem 4.7, we achieve weak reconstruction for the stochastic block model.

Corollary 4 .

 4 11. Let G ∼ G 2n,p,q with a -b > 1368 √ d log n and b = Ω(log n). Then the Averaging protocol produces an O(d log n/(a -b) 2 )-weak reconstruction within O(log n) rounds, w.h.p. Proof. From Theorem 4.10 we get that w.h.p. G is (2n, d, b, γ)-clustered with γ = 6 log n/d, λ 4γ and λ 2

√ d log n and since λ 3 λ 4γ .= 224γ ν -λ 3 4. 3 .

 4γ33 the last inequality follows from the hypothesis a -b > 1368 We can thus apply Theorem 4.7 which guarantees that, w.h.p., the Averaging protocol achieves a ε-weak reconstruction in (2n, d, b, γ)-clustered graphs, with ε Improved analysis for the stochastic block model. In this section we assume again that the underlying graph G is sampled from G 2n,p,q , and we recall that a = pn, b = qn and d = a + b. In Lemma 4.10 we have shown that, when (a -b) > c √ d log n for a suitable absolute constant c, a graph sampled according to G 2n,p,q satises the hypotheses of Theorem 4.7, w.h.p. In this setting, the Averaging protocol thus achieves weak reconstruction in O(log n) rounds.It is known that, when a -b < 2 √ d, weak recovery is impossible for any algorithm[START_REF] Mossel | A proof of the block model threshold conjecture[END_REF][START_REF] Massoulie | Community Detection Thresholds and the Weak Ramanujan Property[END_REF][START_REF] Mossel | Reconstruction and estimation in the planted partition model[END_REF], including centralized algorithms of arbitrarily high running time.How close to this information-theoretic bound does the Averaging protocol get? In this section we provide an analysis specialized to the stochastic model showing that the Averaging protocol achieves weak reconstruction provided that a -b > c • √ d where c is a suciently large constant, and provided that the average degree d is at least logarithmic.

Theorem 4 . 12 . 1 4

 4121 There is an absolute constant c such that the following holds. Let G be sampled from G 2n, a n , b n with 9 log n d < n , b > log n, and a -b > c • √ d. Then the Averaging protocol produces an O(d/(a -b) 2 )-weak reconstruction within

4. 3 . 1 . 1 4

 311 Concentration of the normalized adjacency matrix. In this section we prove the following concentration result for the normalized adjacency matrix of a graph sampled from G 2n, a n , b n . Lemma 4.13. There is an absolute constant c 2 such that, for every 9 log n < d < n , w.h.p.

Lemma 4 . 14 . 1 4

 4141 If 5 log n < d < n then w.h.p.

(4. 30 ) 1 4

 301 From the Cherno bound (and the hypothesis d < n ), w.h.p. (4.31) v∈V d v 2dn + n .

Remark 2 (

 2 Comparison with the work of Le and Vershynin). In [47] Le and Vershynin's show the following result. Let G be sampled from G 2n, a n , b n with average degree d = a + b and adjacency matrix A, and consider the modied matrix A τ = A + τ 2n J, where τ is a parameter of the order of d (for example what we state below holds for τ = 3d), and let

4. 3 . 2 .

 32 Analysis of the Averaging Dynamics. We rst use the Davis-Kahan theorem (Theorem A.4) to infer spectral properties of N based on the fact that N and B/d are close with high probability, as established above.

Lemma 4 . 15 (, with c log n d n 1 4

 4151 Spectral properties of N ). There is an absolute constant c such that the following holds. Let G be a graph sampled from G 2n, a n , b n and a -b > 200 2 (4c 2 + 4)

1 √

 1 Since each node u ∈ O contributes at least 1/(200 2 • 2n) to w 2 -2n χ 2 and, by (4.43),

3. 1 -λ 2 1 n 4

 114 , w.h.p. over the randomness of G. Together with (4.45) and the fact that d max /d min = O(1), w.h.p., these claims imply that weak reconstruction is achieved within O(log n) rounds, w.h.p. Proof of Claim 1. Since v 2 = D -1/2 w 2 and (a -b) 2 > 10 6 c 2 2 d, the third claim of Lemma 4.15 implies that, w.h.p. over the randomness of the graph, for a subset S of at least 2(1

  2 with the following setting: y and S dened above, r = 99 100 (1 -α)d, c = 101 99 1+α 1-α , k = 1/(1 -ĉ), km = 2n and δ = 1 √ 2n

Definition 5 . 1 (

 51 Clustered Regular Graph). A (kn, d, b)-clustered regular graphG = ((V 1 , . . . , V k ), E) is a (kn, d, b)-regular graph such that 1 -kb/d is the second largest eigenvalue of P with multiplicity k -1, that is, λ 2 = • • • = λ k = 1 -kb/d and λ = max{λ k+1 , |λ kn |} < λ k .Theorem 5.2 (More communities). Let G = (V, E) be a (kn, d, b)-clustered regular graph with k = O(n (1/2)-δ ), for an arbitrarily small constant δ > 0, and assume that λ = max{λ k+1 , |λ kn |} < (1 -ε) 1 -kb d , for a suitable constant ε > 0.

  link, chosen uniformly at random, can exchange data. According to this model, nodes are anonymous and cannot use any xed static subgraph of the underlying graph.In more detail, Becchetti et al. in[START_REF] Becchetti | Average whenever you meet: Opportunistic protocols for community detection[END_REF] consider two averaging protocols, working on the Population Protocol model, that approximately recover the community structure in the case of a class of regular clustered graphs having good inner expansion and a sparse cut. Their local clustering criterion is similar to the one we introduce in this paper on top of the Averaging dynamics, that is, it is based on the sign of the nodes' state. Their second-moment analysis show that the protocol converges in O(n log n) time16 and requires a work per node of order O(polylogn), even in the case of dense graphs. For the same restricted class of clustered regular graphs with dense cut (i.e., when the cut between the clusters has size Θ(|E|)), they also derive a more complex second-moment analysis of the Averaging dynamics leading to a somewhat weighted version the Averaging protocol, equipped with a dierent clustering criterion that is based on the uctuations of the nodes' states. This second protocol converges within O(n log n + n/λ 2 ) rounds and requires O(polylogn + 1/λ 2 ) work per node. Inspired by our work and[START_REF] Becchetti | Average whenever you meet: Opportunistic protocols for community detection[END_REF], Mallmann-Trenn et al. in[START_REF] Mallmann-Trenn | Eigenvector computation and community detection in asynchronous gossip models[END_REF] consider Oja's classic iterative

.

  Consequently, if R is the sum of 2n Rademacher random variables, we have P |R| δ √ 2n O(δ).

  Next, we prove that, for any xed a ∈ {-1, 1} |T | , Observe that the lemma is a consequence of the above bound since P |x y| δ √ km = a∈{-1,1} |T | P |x y| δ √ km x T = a P (x T = a) equality follows since the P (x T = a)'s obviously sum to 1. In order to prove (B.1), we dene t = i∈T a(i)y(i) ,and show that, conditioned on x T = a, with a ∈ {-1,1} |T | , P | i∈S x(i)y(i) + t | δ √ km x T = a 2k π )y(i) + t | δ √ km x T = a = = P -t -δ √ km i∈S x(i)y(i) -t + δ √ km x T = a .

  .2. Stochastic block model. In this subsection, we prove that graphs sampled according to the stochastic block model G 2n,p,q , satisfy the hypotheses of Theorem 4.7, w.h.p. and, thus, the Averaging protocol eciently produces a good reconstruction.

Interestingly enough, as long as |ν -λ 3 | = Θ(1), the protocol achieves O(γ 2 )-weak reconstruction on (2n, d, b, γ)-clustered graphs.

4

  AD -1/2 and A/d are also be close to each other. an improvement over the analysis of the previous section. Instead, we are going to use again the fact that A and B are close, and bound D -1/2 AD -1/2 -A/d in terms of D -1/2 BD -1/2 -B/d . Since B only acts on the span of 1 and of χ, which are very smooth vectors in which all coordinates are ±1, the latter term does not depend on the maximum degree but can be bounded in terms of the quantity

	not lead to v ( √ d v -	√	d) 2 . We begin by bounding the latter quantity.
	order to prove that N -B/d ensuring that A/d -B/d O(1/ √ Lemma 4.13, it remains to argue that N -A/d O(1/ √ d), our starting point is Lemma 4.8, d), w.h.p. Thanks to the above result, to prove O(1/ √ d), w.h.p. To this aim, we would like to use the fact that √ d • D -1/2 is close to the identity, so that N =
	D -1/2 Unfortunately, arguing about the spectral norm of	√	dD -1/2 -I does not work,
				log n d	, which would

because it introduces a dependency on the maximum degree of the graph, and the best bound that we would get in this way is A/d-B/d O

  with eigenvector χ, and all other eigenvalues are zero. From

	Lemma 4.13, w.h.p.
				√
	(4.41)	N -B/d	c 2 /	d .
	From Theorem A.2, we have λ 2	1 -2b/d -c 2 / √	d and λ	c 2 /	√	d, which in
	turn implies λ 2 2λ, because a -b 3c 2

  with c 2 the absolute constant appearing in Claim 3 of Lemma 4.15, and notice that ĉ < 1, whenever a -b > 200 2 • (4c 2 + 4) • √ d. From this claim, a subset S of nodes exists, such that |S| 2(1 -ĉ)n and, for each node u ∈ S,

	|v 2 (u)|	99 100 √ 2nd

and sgn

  i ∈ V 1 ∩ S.Next, the assumptions of Theorem 4.12 (in particular, d > 9 log n) imply that, w.h.p., (1 -α)d d u (1 + α)d, for every u ∈ V , with α < 1 a

	Likewise,
	-	101 100	√	2ndv 2 (i) -	99 100	, i ∈ V 2 ∩ S ,
	(small) constant. As a consequence, w.h.p.
	99 100 (1 -α)d y(i) 101 100
	implies
			99 100	√	2ndv 2 (i)	101 100	.

whenever

  is satised, w.h.p., for large enough t: for example, as soon as λ t 2 > n 2 λ t (where λ = max{λ k+1 , |λ kn |}, as dened in the statement of Theorem 5.2).From Lemmas 5.4 and 5.5 it follows that it is enough to pick = (3/γ) log n parallel runs to have that the signatures are well dened and they are the same within each

community and dierent between communities, w.h.p. Indeed, Lemma 5.5 ensures that, for each pair of nodes u, v belonging to distinct communities, the probability that they are of the same type in all runs is smaller than (1 -γ) e γ n -3 . A union bound over all pairs of nodes in distinct communities then proves that all pairs of nodes belonging to distinct communities have distinct type in at least one of the runs, w.h.p. Since, from Lemma 5.4, in each run all nodes in the same community have the same type, w.h.p., it follows that all nodes in the same community have the same type in all the = O(log n) runs, w.h.p.

  2 , iii) ρ i = |y(i)| 3 . Moreover, ρ i /σ 2 i = |y(i)|, so that our hypotheses on y in turn imply max i (ρ i /σ 2 i ) cr. Finally, σ 2 = i σ 2 i mr 2 . As a consequence, we can apply Theorem A.3 to i∈S x(i)y(i), with ψ

	2c √ m	to obtain 17
						√
		P	x(i)y(i) + t	δ	km	x T = a
		i∈S
		P -t -δ	√	km g -t + δ	√	km +	4c √ m	,

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

The notions introduced here refer to unweighted graphs, which are the ones addressed in this paper, but they seamlessly extend to weighted, undirected graphs.

Non-regular graphs.8Bordenave [16, Corollary 21] has considerably simplied the proof of Friedman and Kohler; although he does not explicitly state the probability of the above event, his argument also bounds the failure probability by 1/k Ω(1)[START_REF] Bordenave | [END_REF].

< 1 , from the derivations above and Claim 1 in the proof of Theorem 4.7. This concludes the proof.[START_REF] Becchetti | Step-by-step community detection in volume-regular graphs[END_REF] Notice that Lemma 4.8 would work even for a smaller γ, i.e., for γ = Ω(1/ √ d): However, in this proof, this stronger bound is not useful since, in order to get the rst claim of the theorem, we need γ 6 (log n)/d. The stronger bound will be instead useful in the next subsection.

This argument is due to Ori Gurel-Gurevich (see[38]).

This, for example, might follow from the presence of negative eigenvalues associated with eigen- vectors from the (k + 1)-th onward.

* A preliminary version of this paper has been presented at This work is partly supported by the National Science Foundation under Grants No. CCF 1540685 and CCF 1655215, by the University of Rome Tor Vergata under research programme Mission: Sustainability project ISIDE (grant no. E81I18000110005), by Sapienza University of Rome under research programme Dynamics in complex systems and distributed computing, by ERC Advanced Grants 788893 AMDROMA Algorithmic and Mechanism Design Research in Online Markets and 834861 SOReCoDi Spectral and Optimization Techniques for Robust Recovery, Combinatorial Constructions, and Distributed Algorithms, by the EC H2020RIA project SoBig-Data++ (871042), and by MIUR PRIN project ALGADIMAR Algorithms, Games, and Digital Markets.

Appendix

Appendix A. Linear algebra toolkit.

If M ∈ R n×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 v 1 , . . . , v n such that M v i = λ i v i . Thus, if x ∈ R n is any vector, then we can write it as a linear combination x = i α i v i of eigenvectors, where the coecients of the linear combination are α i = x, v i . In this notation, we can see that

Lemma A.1 (Cauchy-Schwarz inequality). For any pair of vectors x and y

Observation 1. For any matrix A and any vector x

Theorem A.2. (Corollary 4.10 in [START_REF] Stewart | Matrix Perturbation Theory[END_REF]) Let M 1 and M 2 be two Hermitian matrices, let λ 1 λ 2 • • • λ n be the eigenvalues of M 1 with multiplicities in nonincreasing order, and let λ 1 λ 2 • • • λ n be the eigenvalues of M 2 with multiplicities in non-increasing order. Then, for every i,

Theorem A.3 (Berry and Essen, Berry's formulation [START_REF] Berry | The accuracy of the gaussian approximation to the sum of independent variates[END_REF]). Consider n independent random variables X 1 , . . . , X n such that for every i:

Denote by F (x), the cumulative distribution function (for short, c.d.f.) of the variable X = n i=1 X i and by G(x) the c.d.f. of a Gaussian distribution with mean 0 and variance σ 2 . Then there exists an absolute constant C 0 > 0 such that

Theorem A.4 (Davis and Kahan, 1970). Let M 1 and M 2 be two symmetric real matrices, let x be a unit length eigenvector of M 1 of eigenvalue t, and let x p be the projection of x on the eigenspace of the eigenvectors of M 2 corresponding to eigenvalues t -ε. Then

Appendix 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 x, 1 and x, χ . In particular we are going to use the following bound.