# Distributed Graph Diameter Approximation
## 3 Clustering Algorithm  
Our algorithm for approximating the diameter of a weighted graph uses, as a crucial building block, a clustering strategy which partitions the graph nodes into subsets, called clusters, of bounded (weighted) radius. The strategy grows the clusters around suitable \"seed\" nodes, called centers, which are selected progressively in batches throughout the algorithm. The challenge is to perform cluster growth by exploiting parallelism while, at the same time, limiting the weight of the edges involved in each growing step, so to avoid increasing excessively the radius of the clusters, which, in turn, directly influences the quality of the subsequent diameter approximation. Specifically, we grow clusters in stages, where in each stage a new randomly selected batch of centers is added, and clusters are grown around all centers (old and new ones) for a specified radius, which is a parameter of the clustering algorithm. The probability that a node is selected as center increases as the algorithm progresses. The idea behind such a strategy is to force more clusters to grow in regions of the graph which are either poorly connected or populated by edges of large weight, while keeping both the total number of clusters and the maximum cluster radius under control. Note that we cannot afford to grow a cluster boldly by adding all nodes connected to its frontier at once, since some of these additions may entail heavy edges, thus resulting in an increase of the weighted cluster radius which could be too large for our purposes. To tackle this challenge, we use ideas akin to those employed in the \(\Delta\)-stepping parallel SSSP algorithm proposed in [20]. In what follows, we describe an algorithm that, given a weighted graph \(G=(V,E,w)\) and a radius parameter \(r\), computes a _\(k\)-clustering_ of \(G\) with radius slightly larger than \(r\), and \(k\) slightly larger than the _minimum_ number of centers of any clustering of \(G\) of radius at most \(r\). For each node \(u\in V\) the algorithm maintains a four-variable _state_\((c_{u},d_{u},g_{u},s_{u})\). Variable \(c_{u}\) is the center of the cluster to which \(u\) currently belongs to, and \(d_{u}\) is an upper bound to the distance between \(u\) and \(c_{u}\). Variable \(g_{u}\) is the _generation_ of the cluster to which \(u\) belongs to, that is, the iteration at which the cluster centerd at \(c_{u}\) started growing. Finally, variable \(s_{u}\) is a Boolean flag that marks whether node \(u\) is _stable_, that is, if the assignment of node \(u\) to the cluster centered at \(c_{u}\) is final. Initially, \(c_{u}\) and \(g_{u}\) are undefined, \(d_{u}=\infty\) and \(s_{u}\) is _false_. A node \(u\in V\) is said to be _uncovered_ if \(c_{u}\) is undefined, and _covered_ otherwise. For a given graph \(G=(V,E,w)\) and integer parameter \(r\), Algorithm \(\textsc{RandCluster}(G,r)\), whose pseudocode is given in Algorithm 1, builds the required clustering in \(\log n\) iterations (Unless  
Figure 1: An example of a MapReduce round, transforming a multiset of 8 key-value pairs (over 3 keys) into a multiset of 7 key-value pairs (over 5 keys). At most \(M_{A}\) memory overall can be employed during the execution. otherwise specified, throughout the paper all logarithms are taken to the base 2. Also, to avoid cluttering the mathematical derivations with integer-rounding notation, we assume \(n\) to be a power of 2, although the results extend straightforwardly to arbitrary \(n\)). In each iteration, all clusters are grown for an extra weighted radius of \(2r\), with new centers also being added at the beginning of the iteration. More specifically, initially all nodes are uncovered. In iteration \(i\), with \(1\leq i\leq\log n\), the algorithm selects each uncovered node as a new cluster center with probability \(2^{i}/n\) uniformly at random (line 4), and then grows both old and new clusters using a sequence of _growing steps_, defined as follows.