# Distributed Graph Diameter Approximation
## 1 Introduction
### Our Contribution  
This paper extends and improves on earlier conference papers on unweighted [21] and weighted [22] graphs. In this work, we present a simpler algorithm that can handle both weighted and unweighted cases. The high level idea of our algorithm is the following. Given a (weighted) graph \(G\), we construct in parallel a smaller _auxiliary graph_, whose size is tuned to fit into the local memory of a single machine. To this purpose, first the input graph is partitioned into clusters grown around suitably chosen _centers_. Then, the auxiliary graph is built by associating each node with a distinct center, and defining edges between nodes corresponding to centers of adjacent cluster, with weights upper bounding the distance between the centers. The approximation of the diameter of \(G\) is then obtained as a simple function of the exact diameter of the auxiliary graph, which can be computed efficiently because of its reduced size.  
For a (weighted) graph \(G\) with \(n\) nodes and \(m\) edges we prove that our algorithm attains an \(O(\log^{3}n)\) approximation ratio, with high probability. Moreover, we show how the algorithm can be implemented in the MapReduce model with \(O(n^{\epsilon})\) local memory available at each machine, for any fixed \(\epsilon\in(0,1)\), and \(\Theta(m)\) aggregate memory. The number of rounds is expressed as a function of \(\epsilon\), \(n\) and the maximum number of edges in the simple paths that are traversed to connect the nodes of \(G\) to the centers of their respective clusters. We also analyze the round complexity in terms of the doubling dimension \(D\) of \(G\)[23], a notion which broadly corresponds to the Euclidean dimension with respect to the metric space on the nodes induced by the shortest-path distances in the graph (see Section 2.2 for a formal definition). In particular, we show that on graphs of bounded doubling dimension (an important family including, for example, multidimensional arrays) and with random edge weights, if the local memory available to each processor is \(\Theta(n^{\epsilon})\), then the round complexity of our algorithm becomes asymptotically smaller than the unweighted diameter of the graph by a factor \(\Theta(n^{\epsilon/(2D)}/\mathrm{polylog}(n))\). This is a substantial improvement with respect to the MapReduce implementation of \(\Delta\)-stepping whose round complexity, as observed before, is linear in the diameter when linear overall space is targeted.  
As a proof of concept, we complement our theoretical findings with an experimental analysis on large benchmark graphs. The experiments demonstrate that when the input graph is so large that does not fit into the memory of a single machine, our algorithm attains substantial improvements in terms of the running time compared to \(\Delta\)-stepping, while featuring, in practice, a similar approximation ratio, which turns out to be much better than what predicted by the analysis. The experiments also show that our algorithm features a good scalability with respect to the graph size.  
The novelties of this paper with respect to our two conference papers [21; 22] are the following: the presentations of the algorithms for the unweighted and weighted cases have been unified; a novel and simpler clustering strategy has been adopted (adapting the analysis accordingly); and a novel set of experiments has been carried out using a more efficient implementation of our algorithm devised on the Timely Dataflow framework [24].