Connected Components at Scale via Local Contractions
Jakub Łącki Vahab Mirrokni Michał Włodarczyk


Analysing dissipative effects in the ΛCDM model
    Diego Sáez-Chillón Gómez
    December 30, 2023
===============================================


As a fundamental tool in hierarchical graph clustering, computing connected components has been a central problem in large-scale data mining. While many known algorithms have been developed for this problem, they are either not scalable in practice or lack strong theoretical guarantees on the parallel running time, that is, the number of communication rounds. So far, the best proven guarantee is (log n), which matches the running time in the PRAM model. 

In this paper, we aim to design a distributed algorithm for this problem that works well in theory and practice. In particular, we present a simple algorithm based on contractions and provide a scalable implementation of it in MapReduce. On the theoretical side, in addition to showing (log n) convergence for all graphs, we prove an (loglog n) parallel running time with high probability for a certain class of random graphs. We work in the MPC model that captures popular parallel computing frameworks, such as MapReduce, Hadoop or Spark.

On the practical side, we show that our algorithm outperforms the state-of-the-art MapReduce algorithms. To confirm its scalability, we report empirical results on graphs with several trillions of edges.




§ INTRODUCTION

Given the popularity and ease-of-use of MapReduce-like frameworks, developing practical algorithms with good theoretical guarantees for basic graph algorithms is of great importance. An algorithm runs efficiently in a MapReduce framework if it executes few rounds, has low communication complexity, and good load-balancing properties. These features are reflected in the Massively Parallel Computation (MPC) model <cit.>, which provides an abstraction on the popular parallel computing platforms such as MapReduce, Hadoop, or Spark.

Designing efficient MPC algorithms for graph problems has received considerable attention in recent years. The ultimate goal is usually to give an algorithm that runs in o(log n) rounds, while keeping the space per machine (n)[We use the standard notation to denote the numbers of vertices and egdes respectively by n and m.] <cit.>.


While several algorithms and techniques have been developed for computing connected components in a distributed setting, they have shortcomings from theoretical or practical standpoint. For example, some of previously studied practical algorithms satisfy suboptimal theoretical guarantees <cit.> or lack scalability, requiring each connected component to be small enough to fit in memory of each machine <cit.>. The best proven guarantee for the number of rounds is (log n), which matches the running time in the PRAM model. However, the (log n) bound on round complexity is unsatisfactory in relation to practical applications for two reasons:


  * Even a trivial distributed algorithm for finding connected components runs in (d) rounds, where d is the diameter of a graph (one example is Hash-Min <cit.>). On the other hand, in the real-world graphs we often have d ≈log n, which makes the (log n) bound as good as the trivial (d) bound.

  * The (log n) bound does not explain the practical performance of existing algorithms, as they run in just a few rounds even on graphs with billions of vertices.


In this paper, we aim to design scalable distributed algorithms for MPC model with improved theoretical guarantees and practical implementations in a MapReduce-like framework.



 §.§ Our contributions

We introduce a new simple distributed algorithm for finding connected components, that we call LocalContraction. By taking advantage of its simple definition, we can easily show it converges in (log n) rounds and the communication in each round is only (m). More notably, we can show that for random graphs, a slightly modified version of LocalContraction converges in only (loglog n) rounds, even though the diameter of a graph is Ω(log nloglog n) with high probability. This gives a theoretical explanation for the very good practical round complexity of the algorithm observed on real-world graphs.



We note that under a popular conjecture <cit.> achieving o(log n) rounds for general graphs is impossible. The conjecture states that even distinguishing between a graph that is a cycle on 2n vertices and a graph consisting of two cycles of lengths n requires Ω(log n) rounds, if the space per each machine is (n^1-ϵ) and the total space of all machines is (m). 

Moreover, we evaluate the algorithm empirically and run it successfully on several large-scale graphs, including a graph with 854 billion vertices and 6.5 trillion edges, the largest graph that has ever been tested by distributed connected components algorithms. In almost all experiments, LocalContraction turns out to be faster than the best known MapReduce algorithm for computing connected components <cit.>. While the theoretical upper bound on the total communication complexity of our algorithm is (m log n), the experiments indicate that for real-world graphs the communication complexity is only (m).
In our experiments, in each phase of the algorithm the number of edges that are processed decreases at least 10 times.
We believe that this is one of the reasons of the good practical performance of the algorithm.




 §.§ Related work


As a fundamental problem in large-scale data mining, computing connected components has been studied extensively in the 
literature <cit.>.
To the best of our knowledge, none of previously studied (practical) algorithms provide a sublogarithmic round complexity (for a general class of graphs). 
In fact, it has been recently shown that under certain complexity assumptions, achieving (1ϵ) rounds is impossible <cit.>, if the space per machine is limited to (n^ϵ). 

As for algorithms with (log n) number of rounds, algorithms have been developed even in CRCW and CREW  PRAM models <cit.>. While CRCW algorithms can be ported in MapReduce to give a (logn) round algorithm in theory <cit.>, they require the original graph to be persisted and used in each graph iteration.  CREW PRAM algorithms can be simulated in MapReduce using the result of <cit.>, but they would require (n^2) communication per MapReduce iteration on a star graph. Previous work in <cit.> compared the state of the art (logn) time algorithm with a simpler algorithm called Hash-to-Min, and showed that the latter outperforms the former despite the theoretical guarantees. 

Distributed algorithms achieving o(log n) round complexity either require n^1+Ω(1) space per machine <cit.> (which is often an unrealistic assumption) or only apply to very special classes of graphs and are very hard to implement in MapReduce <cit.>.

The best currently known practical MapReduce algorithm for computing connected components is Cracker <cit.>.
It has been shown to require (log n) rounds, but the best known upper bound on the amount of communication is as high as (mn / log n), which is very far from what one observes in experiments.

Recently two algorithms for finding connected components in the BSP model <cit.> have been proposed <cit.>.
The BSP paradigm is used by recent distributed graph processing systems like Pregel <cit.> and Giraph <cit.>. While BSP is generally considered more efficient for graph processing, in congested grids, where fault-tolerance against preemptions is more important, MapReduce has certain advantages <cit.>.
The BSP algorithms can usually be relatively easily implemented in MapReduce, but the fact that MapReduce reshuffles the entire graph between machines in each round means that MapReduce implementations of BSP algorithms do not perform well in practice.



 §.§ Organization of the paper

We begin with introducing the notation and the theoretical model in Section <ref>.
Then we introduce two algorithms based on contraction in Section <ref>.
Section <ref> comprises main guarantees on the algorithms' behavior for general graphs and  Section <ref> contains the proof of (loglog n) convergence for random graphs.

In Section <ref> we present an empirical evaluation of our algorithms on real-world graphs.
Finally, in Section <ref> we complete the theoretical analysis of algorithms by giving Ω(log n) lower bounds on round complexity in general graphs.



























































§ PRELIMINARIES

Throughout the paper we use G to denote a graph, V(G) to denote its set of vertices, E(G) to denote its edges, n = |V(G)| and m = |E(G)|.
For a vertex v ∈ V(G) we define N(v) to be the set of all neighbors of v in G together with v.
For a set U ⊆ V(G) the set N(U) is a union of (N(v))_v∈ U.
Moreover, by E(X, Y) we denote a set of edges that have one endpoint in X and the other endpoint in Y.
We define weakly connected components of a directed graph G to be connected components of a graph G' obtained from G by making each edge undirected.







For an equivalence relation r ⊆ V × V we define the contraction of G with respect to r, denoted G / r, to be a graph obtained from G by merging vertices G that are in relation r.
We refer to vertices of G / r as nodes to avoid confusion.



 §.§ Massively Parallel Computation Model


The class MPC() is parameterized by a space exponent ∈ [0,1].
Let N denote the data size in bits and p be the number of machines.
At the beginning the data is divided over N/p machines
and in a single round each machine can perform arbitrary computations over its data.
Then the machines exchange information between each other with a restriction that each machine can receive at most (N/p^1-) bits in total in a single round.
Therefore the model allows data replication of order (p^).
The main measure of effectiveness is the number of computation-communication rounds of the algorithm.

There are some differences in defining the model details among various authors.
For example, <cit.> allow unlimited computational power of each machine, whereas <cit.> require them to run in polynomial time and space proportional to the local input size.
Our algorithms work in the stronger model with = 0 since the time and space complexities are nearly linear with respect to the local input size.

In some of our algorithms we additionally extend the MPC model with a distributed hash table (key-value store) <cit.>.
In each round all other machines can send messages of total size (n) that define the stored key-value pairs.
In the following round, all machines can query the distributed hash table a total of (n) time, and for each query the value corresponding to a key is returned immediately.



§ OUR ALGORITHMS


We use the term phase to denote a logical part of an algorithm, and round to denote a single MapReduce computation.
Both algorithms sample a random ordering of vertices in the beginning of each phase.
This is implemented by assigning each vertex a random hash chosen uniformly from [0, 1] – this induces a random ordering on each connected component independently and we will focus on a single  component in the analysis.
Note that with this approach we can only compare the priorities of vertices and we cannot access their exact positions in the ordering.




  
LocalContraction
Each phase starts with sampling a random ordering ρ : V(G) → [n].
Then, each vertex v computes a label ℓ_ρ(v), which is the smallest priority assigned to one of vertices in N(N(v)).
Finally, we merge vertices with the same label to a single node and obtain a smaller graph, which is used as an input to the following phase.
Technically speaking, the process of merging is not necessarily a contraction, since two vertices may have the same label even if there is no edge connecting them.
The procedure terminates when each connected component gets reduced to a single node, or, equivalently, the resulting graph has no edges.



  
Lazy Local Contraction
This is a modification of Local Contraction with a property that each vertex will be merged with at least one with constant probability.
This can be enforced by resetting the label to itself with probability 1/2, independently for each vertex.




  
TreeContraction
Similarly to LocalContraction, at the beginning of each phase each vertex receives a random priority.
Let (v) be the vertex with the lowest hash among N(v) ∖{v}.
This mapping induces a directed graph H.
Assume r is a relation such that two vertices are in relation r if and only if they are in the same weakly connected component of H.
In one phase, TreeContraction contracts G with respect to r.

Observe that this time each contracted node is guaranteed to originate from a connected subgraph, so we obtain a minor of the original graph.
Again, the following phase processes the contracted graph and we terminate when each connected component gets reduced to a single node.


The contraction step in both algorithms can be implemented in MPC(0) in (1) rounds.



We assume that we have already assigned labels to vertices – for LocalContraction it is straightforward and for TreeContraction it is described in Theorem <ref>.
The vertices are then assigned to machines without replication.
In case a neighborhood of some vertex is too large to fit into single machine's memory, it is divided among several machines and only the label gets replicated.

For each vertex v and edge uv a mapper sends a key-value pair (u,ℓ(v)), where ℓ(v) stands for the label of v.
These messages are grouped again by vertices and the label mapping is applied to u.
In the end a new edge (ℓ(u),ℓ(v)) is generated and potential duplicates are being removed in a standard way.





§ MAIN PROPERTIES OF THE ALGORITHMS









In this section we show that both algorithm behave in a sensible way on any input.
For LocalContraction the argument for convergence relies on a fact that each vertex has a big chance of seeing a neighbor with low priority.


LocalContraction terminates after (log n) phases with high probability.




Recall that in each phase of the algorithm, each vertex v computes a label ℓ_ρ(v) and the vertices with equal labels are merged.
We show that the expected number of distinct labels computed in each step is at most 3n/4.

Consider a vertex w satisfying ρ(w) ≥n/2.
As long as the component of w has not been reduced into a single node, we can fix a neighbor u of w.
The value of ρ(u) is a uniformly random variable from [1, n] ∖{ρ(w) }.
In particular ρ(u) < n/2≥1/2.
Let Z_w be a binary random variable indicating whether ρ(ℓ_ρ(w)) < n/2.
We can see that Z_w≥1/2 and, by the linearity of expectation, ∑_v : ρ(v) ≥n/2 Z_v≥n/4.

We can now bound the number of distinct labels computed in the first phase, which we denote by X_1.
Since ρ(ℓ_ρ(v)) ≤ρ(v), vertices v with ρ(v) ≤n/2 are assigned labels that are not greater than n/2.
Moreover, in expectation at least n/4 vertices with ρ(v) ≤n/2 are assigned labels not greater than n/2.
This implies X_1≤3n/4.

Let X_k denote the number of vertices after k phases of the algorithm or 0 if the algorithm has terminated.
We have X_k≤(3/4)^k n and for k = (1+c)·log_4/3 n the expected number of vertices is at most n^-c.
By Markov's inequality we get X_k ≥ 1≤ n^-c, what finishes the proof.
Observe that for each vertex v its label stays f_ρ(v) and the label of f_ρ(v) is reset to itself with probability 1/4.
Let random variable X_v equal 1/|C(v)|, where C(v) is the set of vertices sharing the same label as v.
Since X_v ≤1/2 with probability 1/4,
we have X_v≤7/8.
Clearly, the size of the merged graph equals X = ∑_v ∈ V X_v,
which is at most 7n/8 in expectation.

Let T(n) denote the expected number of rounds required to process a graph with n vertices.
It satisfies recursive formula T(n) = 1 + T(X).
We assume inductively T(k) ≤log_4/3 k for k < n (X < n with probability 1) and, since logarithm is concave, we check 


    T(n) = 1 + T(X)≤ 1 + log_4/3 X≤ 1 + log_3/4 (X) ≤ 1 + log_4/33n/4 = log_4/3 n.




Since all operations within each phase of LocalContraction are local, the above lemma immediately implies the following.


LocalContraction can be implemented to run in (log n) MapReduce rounds with high probability.


To bound the number of phases executed by TreeContraction it suffices to observe that all contracted sets contain at least two vertices.


TreeContraction terminates after (log n) phases.



Since f_ρ(v)  v, each cluster consists of at least two vertices
and the number of vertices drops by at least a factor of two in each phase.
Therefore, the worst case number of contraction phases is (log n).



We also need to handle each phase efficiently.
In order to do so, we analyze the structure of paths induced by the mapping f_ρ.
In particular, we show that all paths stabilize after relatively few steps.


Let ρ : V → [n] be a one-to-one function.
Let (v) be the vertex with the smallest value of ρ among N(v) ∖{v}.
Then, for each v there exists an integer d(v), such that for each i ≥ d(v), ^i(v) = ^i+2(v).[Here, ^i denotes the i-th functional power of .]




Since  is defined on a finite domain, there exists d(v) such that the sequence ^d(v)(v), ^d(v)+1(v), ^d(v)+2(v), … is periodic.
Let r be the vertex from this sequence with the smallest value of ρ(r).
We show that ((r)) = r.
Clearly, ρ(((r))) ≥ρ(r) from the choice of r.
On the other hand, r is a neighbor of (r), so ρ(((r))) ≤ρ(r).
Hence ρ(((r))) = ρ(r), which implies ((r)) = r.
This implies ^i(v) = ^i+2(v) for each i ≥ d(v).




Let us define ρ,  and d as in the statement of Lemma <ref>.
Moreover, assume that ρ is chosen uniformly at random from all one-to-one functions mapping V to [n].
Then, max_v∈ V d(v) = (log n) with high probability.



Let us define p(v, i) := (^i(v)) if i ≤ d(v) and p(v, i) = 0 for i > d(v).
In particular p(v, 0) = ρ(v).

We now show that for each v ∈ G we have p(v, 2) < p(v, 0)/2.
If ^2(v) = v, this is obvious, as p(v, 2) = 0.
Thus, let us consider the opposite case.
	
    (x) | x = ^2(v), x ≠ v    = (x) | x = _u∈ N((v)) ∖{(v), v}(u)
        = min{(u) | u ∈ N((v)), u ≠(v), u ≠ v}
        = min{(u) | u ∈ N((v)), u ≠(v), ρ(u) < ρ(v)}.


Fix u' such that u' ∈ N((v)), u' ≠(v) and (u') < (v).
Then ρ(u') is a uniformly random number from {1, …, ρ(v)-1}, which implies ρ(u')≤ρ(v)/2.
	By applying an obvious formula min(X_1, X_2, …, X_k)≤X_1, we get:
	
    min{(u) | u ∈ N((v)), u ≠(v), (u) < (v)}≤ρ(u')≤(v) / 2 = p(v, 0) / 2.

By applying the above property, it follows that p(v, 2· i) < p(v, 0)· 2^-i for each v ∈ G and i ≥ 0. This in turn implies that p(v, 2·(2+c)·log n) < p(v, 0) · 2^-(2+c)·log n≤ n^-(1+c).

Hence, d(v) ≥ 2· (2+c)·log n = p(v,(2+c)·log n) ≥ 1≤ n^-(1+c), where the last step follows from Markov's inequality.
By the union bound we get that max d(v) ≥ 2· (2+c)·log n≤ n^-c.





Let us define ρ,  and d as in the statement of Lemma <ref>.
Let H be the directed graph defined by the mapping .
	Then, two vertices u and w belong to the same weakly connected component of H if and only if {^d(u)(u), ^d(u)+1(u)} = {^d(w)(w), ^d(w)+1(w)}.



Clearly, if two vertices do not belong to the same weakly connected components of H, the corresponding sets are different.
It remains to show the converse.

By Lemma <ref>, each i ≥ d(v), ^i(v) = ^i+2(v).
This means that {^d(u)(u), ^d(u)+1(u)} is the set of all vertices that are appear infinitely many times in the sequence v, (v), ^2(v), ….

Let P be a simple path in H connecting u and w.
First assume that P is a directed path, say, from u to w.
Thus, for some j, ^j(u) = w and the lemma follows.

In the remaining case P is not a directed path.
From the fact that each vertex of H has a single outgoing edge, there exists a vertex x on P such that paths from u to x and from w to x are directed.
This implies that for some j and l ^j(u) = ^l(w), which completes the proof.




TreeContraction can be implemented to run in (log n loglog n) MapReduce rounds with high probability.
Moreover, in the MapReduce model with a distributed hash table TreeContraction can be implemented to run in (log n) rounds.



Let us define ρ, , d and H as in the statement of Lemma <ref>.
In order to implement TreeContraction, for each vertex we need to compute a label, such that two vertices have the same label if they belong to the same weakly connected component of H.
By Lemma <ref> it suffices to compute ^d(v)(v) for each v.
By Lemma <ref> this can be computed once we know ^j(v) for a single value j ≥ d(v).

Having an access to a distributed hash table one can compute ^d(v)(v) in using (d(v)) queries to the hash table.
Moreover, d(v) = (log n) with high probability by Lemma <ref>.
This means that computing the labels can be done in one round.
After that the graph can be contracted in a constant number of rounds. 

In order to compute representatives without the hash table we take advantage of the pointer jumping technique.
Consider a subroutine in which after the i-th step we have a mapping from each vertex v to ^2^i(v).
In the i-step v queries w = ^2^i(v) for ^2^i(w) and computes ^2^i+1(v) = ^2^i(w) = ^2^i(^2^i(v)).

The subroutine requires logmax_v∈ V d(v) steps, which is (loglog n) w.h.p. due to Lemma <ref>.



TreeContraction terminates after at most d phases in the worst case.


Recall that TreeContraction does not reshuffle the ordering but each contracted node inherits the lowest hash of its cluster.
Let ρ(v_1) = 1  and w be an arbitrary vertex.
Consider a path v_1, v_2, …, v_k, where v_1 is as defined above, v_k = w, and k ≤ d.
Wherever v_i sees the lowest hash in its neighborhood it must gets contracted with the corresponding vertex.
By an inductive argument v_i is contracted to the same node as v_1 after at most i phases.
The claim follows.





§ (LOGLOG N) ROUND CONVERGENCE IN RANDOM GRAPHS


In this section we give a (loglog n) upper bound on the number of rounds of LocalContraction on a certain class of random graphs.
We believe that this provides some explanation for the low number of rounds of the algorithm that we observe in practice.

Recall that probability distribution over graphs with n vertices is called G(n,p) is probability of each edge occurrence is p and these events are independent <cit.>.
We relax this restrictive model and allow the occurrences of edges to be at least as likely as in G(n,p).


We say that a probability distribution D over graphs with n vertices belongs to class np if for all u,v ∈ V(G) we have X_uv≤ X'_uv almost surely, where X_uv is a binary random variable s.t. X_uv = 1 if and only if uw ∈ E(G(n,p)), and X'_uv is the counterpart of X_uv for D.


We will use a notation G ∼ n p to indicate that G is sampled from a distribution from the class n p.
Note that the n p model is far less restrictive than G(n, p), as adding any fixed set of edges to G ∼ n p yields a graph from n p.

We will be interested in distributions with p > c·log n/n for some constant c.
Note that a graph sampled from such a distribution is connected with high probability
and for p∼log n/n its diameter is asymptotically log n/loglog n <cit.>.
Note that <cit.> considered a random graph model, but only in the regime when p ≥ n^-3/4.
This is a much easier case, as such graphs have constant diameter with high probability.


For the sake of analysis we introduce an additional step in the algorithm.
Note that it can be implemented in (1) MapReduce rounds.



  
MergeToLarge step
This is a step that is executed at the end of each phase of LocalContraction.
It takes as input the contracted graph computed in this phase.
It is parameterized by sequence (α_i) depending on the graph density.
At the end of the i-th phase we detect large nodes, that is, those created by merging at least α_i vertices.
For each large node we compute its priority, which is the α_i largest hash of the vertices it contains (using the vertex hashes from phase i).
Our goal is to merge each node v with a large node within a two-hop neighborhood of v.
If v has at least one large one in distance at most 2, we merge it with the large node of largest priority.


Suppose G ∼ n α_n/n, where α_n ≥ 4ln n.
Let A = {v ∈ V(G) |(v) ≤n/α_n},  B = V(G) ∖ A.
Then with probability 1 - (n^-3):


  * the number of vertices v ∈ B such that N(v) ∩ A ∅ is at least n/2, and

  * for all  v ∈ A we have N(v) ∩ B ∅.





To prove the first claim we fix v∈ B and bound


    ℓ_ρ(v) ∉A≤∏_u ∈ A uv ∉E(G)≤(1 - α_n/n)^n/α_n < 1/e.



Hence, the expected number of vertices from B having a neighbor in A is at least (1-1/e)·|B| =  (1-1/e)n - o(n).
Since the events of edges occurrences are lower bounded by events from G(n,p) so are events representing having a neighbor is a particular subgraph.
Therefore we can take advantage of Hoeffding's inequality to obtain that the at least n/2 vertices of B have a neighbor in A with probability at least  1 - exp(-Ω(n)).

Now we bound the probability of v ∈ A having no neighbors in B:

    (1 - α_n/n)^n - n/α_n≤(1 - α_n/n)^n/α_n(4ln n - 1) ≤ e/n^4.


Here, the expected number of vertices from A having no neighbor in B is less than e/n^3.
Therefore the probability that there is at least one such vertex is most e/n^3 by Markov's inequality.




Consider a Bernoulli scheme with n trials and probability of success in each trial at least p, where np ≤1/2.
The probability of at least one success in such a scheme is at least np/2.



We begin with a coupling argument so that we can lower bound the probability of at least one success with an analogous probability for a Bernoulli scheme with a single success chance exactly p.
Then we proceed by induction claiming that after k trials the probability of at least one success is between kp/2 and 1/2 – let use denote this event as A_k.
The induction thesis holds for k=1 because p is at most 1/2.
Consider the (k+1)-th trial.
We have A_k+1 = A_k +  A_k· p ≥kp/2 + p/2.
On the other hand A_k+1≤ (k+1)· p ≤ np ≤1/2, what proves the induction thesis.




Suppose G ∼ n α_n/n where α_n ≥ (4+4c)·ln n and α_n = o(n^1/3).

Let H be the graph created after a single round of LocalContraction with MergeToLarge step with parameter α_n/4.
Then with high probability |V(H)| ≤n/α_n and H ∼ m Ω(α^2_n/m)
under condition |V(H)|  = m.



The algorithm consists of two phases, first of which is tree contraction with respect to an arbitrary ordering , that takes (loglog n) rounds due to Lemma TODO.
During the second phase, we detect nodes in G / r_ that have been created by connecting at least α_n / 4 vertices of G, and contract them with nodes at distance at most 2 that do not satisfy this condition.
This can be done in (1) rounds due to Lemma TODO.


Sampling G from distribution of type n α_n/n and then choosing a random ordering is equivalent to fixing the ordering first and then examining existence of each edge independently.
Since we want to claim that the edges in H are distributed (somewhat) independently, in one phase we are going to examine only a subset of edges of G.
We refer to the unexamined edges as tentative and we do not make any assumptions on their existence.

We start with estimating probability of the event (v) = u assuming (u) < (v).
For this to happen, the edge uv must exist and no edge xv can be present for (x) < (u).
Since these event are independent we have

    (v) = u≥uv·∏_x : (x) < (u) xv



Let C_(v) denote the equivalence class of vertex v, i.e., the set of vertices sharing the same label.
As in the statement of Lemma <ref> we define A = {(v) ≤n/α_n : v ∈ V(G)} and B = V(G) ∖ A.
We examine edges from E(A,B) and from now on assume that the conditions from Lemma <ref> hold.
Let  B^* indicate those vertices from B that have a neighbor in A.
We have ℓ_ρ(v) ∈ A for v∈ B^*, and, by Lemma <ref>, |B^*| ≥n  2.
Let R = {v ∈ B^* | |C_(v) ∩ B| ≥α_n  4} – we will also refer to these vertices as red.
Observe that |R| ≥n/4.
Otherwise for at least n 4 vertices v∈ B^* we would have ℓ_ρ(v) ∈ A and |C_(v) ∩ B| < α_n  4.
There can be at most |A| = n/α_n such equivalence classes, therefore |B^* ∖ R| < n/4,
a contradiction.

The nodes created by contracting red vertices are called red nodes.
A node is red iff at least α_n vertices v with ρ(v) > n/α_n are merged when it is created.
This is equivalent to the fact that the α_n-th largest vertex hash of these vertices is greater than n/α_n.
As a result, from the definition of MergeToLarge step it follows that if a node's cluster is smaller than α_n  4 and there is a red node at distance at most 2, they will get merged together.

In order to argue that all vertices end up sufficiently close to a red one we will show that with high probability N(N(R)) = V(G).
and for this purpose we examine edges from E(R, B ∖ R)
(note that they are still tentative).
We have established that |R| ≥n/4 therefore the probability of v ∈ B ∖ R having no neighbors in R is at most

    (1 - α_n/n)^n/4≤ e^-α_n/4≤  e^-(1+c)·ln n = n^-(1+c).

Thus |B ∖ N(R)|≤ n^-c and |B ∖ N(R)| ≥ 1≤ n^-c by Markov's inequality,
so with high probability all vertices in B ∖ R have a neighbor in R.

It remains to handle vertices in A, that is, to show that A ⊆ N(N(R)).
By assumption we know that for each v ∈ A there is u ∈ N(v) ∩ B.
If u belongs to R, then v ∈ N(R)
and if u ∈ N(R), then v ∈ N(N(R)).
In the previous paragraph we have proven that
these are the only possible options.

If there is at least one such u ∈ B,  uv ∈ E(G), it might belong to R,  N(R) ∖ R or B ∖ N(R).
In first two cases v is in distance at most 2 from a red vertex.
By the union bound, the probability of the remaining two cases is at most
(1/n).
Note that R is a sum of equivalence classes of ρ, so G[R / ρ is a subgraph of G / ρ.
We set U_1 = (N(N(G[R]/ ρ)),  U_2 = V(G/ ρ) ∖ U_1 and obtain |U_2| = (1).


All edges in B ∖ R are connected to those in R and those in R are connected to A.
This means that all the labels are below n/α_n
 so clearly m = |V(H)| is at most n/α_n.
In order to estimate to probability of an edge in H being present,
we take advantage of the fact that the edges in G[ R] are still tentative.
Consider a pair of nodes x,y∈ V(H).
By the definition of R sets of vertices contracted to x,y contain at least 
α_n  4 vertices from B each.
We lower bound the probability of x,y being connected by the probability that at least one of these α^2_n  16 pairs admit an edge.
By Lemma <ref>, it is Ω(α^3_n/n) = Ω(α^2_n/m) for α_n = o(n^1/3).
There might be also other edges influencing the graph H, but in order to show that H ∼ m Ω(α^2_n/m it suffices to lower bound corresponding random variables with independent ones with the given probability of occurrences.
The independence of the new edge variables follows from the fact that we examine disjoint sets of edges in G.



Suppose each connected component of G is sampled from n_i p, where n_i ≤ n.
Then after (loglog n) rounds of LocalContraction with MergeToLarge step each  component will get reduced to a single node with high probability.


Note that the algorithm never needs to check the actual position of a node in the ordering and only compares it with other nodes.
This allows us to treat each connected component of G separately and
we apply Lemma <ref> to each of them.

Let α_n,i indicate the parameter describing the component distribution after the i-th round, starting with α_n,0 = α_n = Ω(log _n).
We have α_n,i+1 = Ω(α^2_n,i) as long as α_n,i = o(n^1/3) and
by induction we obtain that  α_n,i = Ω(log^2^in).

Hence, after k = Ω(loglog n) rounds, we get α_n,k = n^Ω(1).
Each following step with high probability decreases the number of vertices by at least a factor of α_n, k.
Thus, the algorithm terminates in (1) rounds afterwards.




§ EMPIRICAL STUDY




In order to evaluate our algorithms empirically we have used five graphs described in Table <ref>.
Orkut and Friendster are social networks from SNAP collection <cit.>.
Clueweb <cit.> is publicly available web-crawl graph.
The two non-public data sets are graphs representing pairs of similar entities in large collections of (a) video segments and (b) webpages.
Note that the webpages graph has more edges and over three times more vertices than the largest graph that has been previously used to test distributed connected components algorithms <cit.>.

We compare our algorithms (LocalContraction and TreeContraction) to three previously known algorithms: Cracker <cit.>, Two-Phase <cit.> and Hash-To-Min <cit.>.
These algorithms have been the state-of-the art MapReduce algorithms for computing connected components in recent years.
We implemented all algorithms ourselves in a MapReduce framework.

The implementations of two algorithms, TreeContraction and Two-Phase, additionally use a distributed hash table.
The implementation of Two-Phase that uses a distributed hash table seems to be most efficient  than in the experiments given in <cit.>.
It allows to execute a sequence of large-star operations followed by a small-star operation in constant number of rounds and thus we count this whole sequence as one phase.

The Cracker algorithm in each phase modifies the edges of the graph and based on the new set of edges deactivates some of the vertices, excluding them from future phases.
We observe that Cracker is equivalent to the following algorithm.
Assume that each node is assigned a random priority.
First, rewire the edges of the graph just as in Hash-To-Min algorithm <cit.>. Then, compute labels ℓ_p(v) = min_w ∈ N(v)ρ(w) and merge together all vertices that have the same label.
This makes it easy to implement the algorithm in a similar way to our algorithms and minimizes the potential differences in the running times caused by using completely different implementations.

For algorithms that contract the graph (LocalContraction, TreeContraction and Cracker) we have introduced two optimizations.
If after some phase the contracted graph is small enough (e.g. has few tens of millions of edges), we send it to one machine that finds its connected components in a single round.
On this machine we use union-find algorithm to find connected components, as it can process incoming edges in a streaming fashion and only use space proportional to the number of vertices.
Note that this optimization does not apply to Two-Phase and Hash-To-Min, which do not modify the set of vertices in the graph.
Moreover, after each phase we can get rid of all isolated nodes from the contracted graph, as their connected component assignment is clear.

The i-th phase of each algorithm takes as input an undirected graph G_i and produces a contracted graph G_i+1 and a mapping c_i : V(G_i) → V(G_i+1) that describes which vertices of G_i got merged into each vertex of G_i+1.

After some number of phases we obtain a graph G_k, whose vertices correspond to the connected components of G_1.
The mappings c_i need then to be composed to obtain a mapping from vertices of G_1 to vertices of G_k (i.e., the connected components).






The experimental results are given in Tables <ref> and <ref>.
When computing running times, we have taken a median from three runs.
The missing entries in both figures correspond to runs that have run out of memory or were timed out.
Due to large resource usage, we only completed one run of Cracker on webpages dataset, and thus we present an approximate result.


The number of phases in LocalContraction, TreeContraction, and Cracker are very similar and do not exceed five, even for graphs with billions of vertices.
However, Cracker is on average slower than LocalContraction.
We believe that this caused by performing more complicated graph transformations in each step.




Finally, Fig. <ref> shows the effect of graph contraction, by showing the numbers of edges at the beginning of each phase for two datasets (for the other datasets the graphs would look similar). In every dataset and each phase of LocalContraction the number of edges decreases by a factor of at least 10.



§ LOWER BOUNDS

The algorithm Hash-to-Min has been conjectured to converge in (log d) rounds and [TODO cite] provided an empirical evidence suggesting that this might hold for binary trees.
We refute this conjecture by showing that processing a binary tree with diameter d requires asymptotically Ω(d) rounds of Hash-to-Min.

At first we compare the number of rounds in the execution of Hash-to-Min with Local Contraction, which is at least the number of rounds of Tree Contraction.
Then we show that Tree Contraction requires Ω(log n) rounds on a tree with n vertices.I don't think this counterexample works anymore


For a given graph G with fixed ordering of vertices, the number of rounds required by Hash-to-Min is at least the number of rounds required by Local Contraction.


Imagine a hypothetical modification of Hash-to-Min that sends additional messages, what can only improve the algorithm.
We do not consider its implementation details since we need it only for running time analysis.
Namely, vertex v still forwards the set C_v to ℓ(v), but when {ℓ(v)}
is sent to other w∈ C_v, we send it also to all the vertices having the same current label ℓ as w.

Let H_i indicate the graph G divided by the relation of sharing the same label ℓ after the i-th round of the algorithm, i.e., we merge vertices having the same minimal element of C_v.
Let h_i(v) denote the node containing v in H_i.
Observe that when u ∈ C_v after the i-th rounds, then h_i(u)h_i(v) ∈ E(H_i).TODO prove the observation by induction
We can assume that if nodes x,y share an edge in H_i, then the algorithm would send at least one message between their cluster, because again sharing more information can only help.
Therefore the graphs H_i retrace execution of Local Contraction on G.



The Hash-to-Min algorithm has been conjectured to run in (log d) rounds <cit.> but
so far no parallel algorithm has been proved to terminate in o(log n) or o(d) rounds for all graphs while keeping moderate communication.
One can achieve (log d) rounds with the  Hash-to-All algorithm <cit.>, but it is burdened with a quadratic communication complexity.

In this section we show that none of the considered algorithms can be proved to work in o(log n) for all graphs.


LocalContraction, Cracker, and Hash-To-Min require Ω(log n) rounds on path of length n.




In a single phase LocalContraction connects vertices at distance at most 4 so it can shorten the path at most 5 times in a phase.
Cracker and Hash-To-Min insert new edges to the graph, however they are constructed by concatenating edges sharing one common endpoint.
By induction one can see that after the k-th round the edges of v are at distance at most 2^k from v.



Lower bound for TreeContraction involves a more sophisticated argument and works only in a randomized setup.
This is inevitable because there is an ordering for which TreeContraction (with a distributed hash table) processes a path in a single round.


TreeContraction requires Ω(log n) phases to process a path of length n with high probability.




Consider a subpath of length 5.
With probability 1/5 the vertex in the middle receives the lowest priority and becomes one of the two vertices that define a contracted weakly connected component.
Let us divide the path into k = n/5≥n/5 - 1 segments and let X_i be a binary random variable indicating whether the middle vertex of the i-th segment becomes a root.

We define X = ∑_i=1^k X_i.
Clearly X_i = 1/5 and X≥n/25 - 1/5.
By Hoeffding's inequality X ≤n/26 = exp(-Ω(n)).
Since the class of paths is closed under taking contractions and X is a lower bound on the length of the contracted path,
we can iterate this argument.
Hence, after log_26 n rounds, the algorithm will be still running with high probability.



Since the number of leaves in any tree is at least n/2, we can
apply Lemma <ref> with N=n/2 to obtain a bound ln(X+1)≥lnn/2 - 1, which will turn out useful soon.

We denote T(n) to be the expected number of rounds required to process a path of length n.
Since the class of paths is closed under taking contractions and X is a lower bound on the length of the contracted path, we can write a recursive formula T(n) ≥ 1 + T(X).
We assume inductively that T(k) ≥ c·ln(k+1) for k < n (X < n almost surely), where constant c will be fixed shortly.
The induction thesis follows from


    T(n)    ≥ 1 + T(X)≥ 1 + c·ln(X+1)Lem <ref>≥ 1 + c·(lnn/2 - 1) 
       = 1 + c·ln n - c·(ln 2 + 1) ≥ c·ln(n+1),


where c must satisfy 1/c -1- ln 2 ≥ 1 ≥ln(1+1/n). This holds for c = 1/3.



In this section we investigate the boundaries of our approach for the case when the graph is sparse.
Since the following theorem works for all trees, it also implies an Ω(d) lower bound when applied to binary trees.


Tree Contraction requires Ω(log n) rounds in expectation on a tree with n vertices.


The idea is to show that after each round the number of vertices decreases only by a constant factor.
Then the claim follows by induction.

Observe that the number of vertices in the contracted graph equals the number of sinks, i.e., vertices that have lower hash than all their neighbors.
Consider the set of leaves of the tree, grouped in sets L_1, L_2, …, L_k, such that the leaves in L_i share a common neighbor u_i.
Let X_i be a random variable indicating the number of sinks among L_i.
Observe that each permutation of L_i ∪{u_i} is equally likely to occur and X_i equals the number of elements in L_i with a hash lower than ρ(u_i).
Therefore X_i is uniformly distributed over [0, |L_i|] and X_i = |L_i|/2.
What is more, the variables X_1, X_2, …, X_k are independent.

Let X = ∑_i=1^k X_i.
Since the number of leaves in any tree is at least n/2, we can
apply Lemma <ref> with N=n/2 to obtain a bound ln(X+1)≥lnn/2 - 1, which will turn out useful soon.

Similarly to the proof of Theorem <ref> we denote T(n) to be the expected number of rounds required to process a tree with n vertices.
Since the class of trees is closed under taking contractions and X is a lower bound on the size of the contracted tree, we can write a recursive formula T(n) ≥ 1 + T(X).
We assume inductively that T(k) ≥ c· ln(k+1) for k < n and constant c will be fixed shortly.
The induction thesis follows from


    T(n)    ≥ 1 + T(X)≥ 1 + c·ln(X+1)Lem <ref>≥ 1 + c·(lnn/2 - 1) 
       = 1 + c·ln n - c·(ln 2 + 1) ≥ c·ln(n+1),


where c must satisfy 1/c -1- ln 2 ≥ 1 ≥ln(1+1/n). This holds for c = 1/3.

Since the priorities are given by a random permutation, then the probability that vertex v is a root equals 1/ v + 1.
Moreover, such events are independent if the distance between vertices is at least 3.
Since f(x)=1/x is convex, by Jensen's inequality we have


    ∑_v ∈ V1/ v + 1≥n^2/∑_v ∈ V v + n = n^2/3n-2≥n/3.


We root the tree in any vertex and divide V into four subsets, depending on the value of (v)  4.
Each of them is a 3-independent set and we define W to be the one with the largest sum 
∑_v ∈ W1/ v + 1.
Therefore we have lower bounded the number of roots by a sum of independent binary variables with sum at least n/12.
Let us denote this variable as X.
TODO estimate log(X) and prove equation T(n) ≥ 1 + T(X) for T(n) = log n.
TODO argue that we can rely on induction even if we do not reshuffle the order after each stepTODO




Let X_1, X_2, …, X_k be independent random variables with X_i being uniformly distributed over {0, 1, …, n_i} and let X = ∑_i=1^k X_i,  N = ∑_i=1^k n_i.
Then ln (X+1)≥ln(N) - 1.


For sake of simplicity we assume w.l.o.g. that n is odd so N/2 < N/2.
Otherwise we modify X_0 by decreasing n_0 by 1 and obtain a new random variable X̃ such that X̃≤ X almost surely.

The variable X is unimodal and symmetric around X = N/2.
The value of ln (X+1) can be expressed as


    ∑_i=0^N/2(ln(i+1) + ln(N - i+1))·X = i



The sequence X = 0, X = 1, …, X = N/2 is non-decreasing.
What is more, the function f(i) = ln(i+1) + ln(N - i+1) is also non-decreasing over [0, N/2] because logarithm is concave.
Therefore the sum (<ref>) can only decrease when one replaces the sequence X = 0, X = 1, …, X = N/2
with a constant sequence of the same sum.
In other words, we compare distribution of X with a uniform distribution over {0,1,…,N} and conclude that


    ln(X+1)   ≥1/N+1∑_i=0^N ln(i+1) ≥1/N+1∫_1^N+1ln(x)dx 
        = (N+1)ln(N+1) - N/N+1≥ln(N+1) - 1.


Because we might have decreased n by 1 in case it was even, we obtain a lower bound of ln (N) - 1 for all N.





§ ACKNOWLEDGMENTS

We would like to thank Stefano Leonardi for helpful discussions, in particular on ideas that led to the proof of Theorem <ref>.

alpha


