# Distributed Graph Diameter Approximation
## 6 Improved Performance for Unweighted Graphs  
We can show that running the MapReduce implementation described in the previous section on unweighted graphs is faster than in the general case. In fact, in the unweighted case, the growing step is very efficient, since once a node is covered for the first time, it is always with the minimum distance from its center, so it will not be further updated. (In fact, in the unweighted case the growing step is conceptually equivalent to one step of a BFS-like expansion). This results in an improvement in the round complexity by a doubly logarithmic factor, as stated in the following corollary to Theorem 4.  
Corollary 2: _Let \(G\) be a connected unweighted graph with \(n\) nodes, \(m\) edges, and doubling dimension \(D\). Also, let \(\epsilon\in(0,1)\) be an arbitrarily fixed constant. With high probability, an estimate \(\Phi_{approx}(G)\) such that \(\Phi(G)\leq\Phi_{approx}(G)=O(\Phi(G)\log^{3}n)\) can be computed in_  
\[O\left(\left\lceil\frac{\Phi(G)}{n^{\epsilon/(2D)}}\right\rceil(\log n)^{1+2/D}\right)\]  
_rounds on the \(MR(M_{L},M_{A})\) model with \(M_{L}=O(n^{\epsilon})\) and \(M_{A}=\Theta(m)\)._  
Proof: The approximation bound is as stated in Theorem 4. For what concerns the round complexity, we first observe that an unweighted graph can be regarded as a weighted graph with unit weights. On such a graph, we have \(\ell_{x}=x\), for every positive integer \(x\). Thus, by Lemma 1, each execution of RandCluster\((G,r)\) can be implemented in \(O(r\log n)\) rounds in the \(MR(M_{L},M_{A})\) model with \(M_{L}=O(n^{\epsilon})\) and \(M_{A}=\Theta(m)\). From the statement of Theorem 4, recall that \(r_{\epsilon}^{*}\) is the minimum radius of any clustering of \(G\) with at most \(n^{\epsilon/2}/\log^{2}n\) clusters. As argued in the proof of that theorem, the round complexity of the algorithm is dominated by the executions of RandCluster, which are performed for geometrically increasing values of \(r\) up to a value at most \(2r_{\epsilon}^{*}\), thus yielding an overall round complexity of \(O(r_{\epsilon}^{*}\log n)\).  
By reasoning as in the proof of Corollary 1 we can show that \(G\) can be decomposed into \(n^{\epsilon/2}/\log^{2}n\) disjoint of radius \(\phi=O(\left\lceil\Phi(G)(\log^{2}n/n^{\epsilon/2})^{1/D}\right\rceil)\), which thus provides an upper bound to \(r_{\epsilon}^{*}\). The corollary follows.  
In the case of unweighted graphs, the most natural competitor for approximating the diameter is a simple BFS, instead of \(\Delta\)-stepping. However, the same considerations made at the end of the previous section apply, since any natural MapReduce implementation of BFS also requires \(\Theta(\Phi(G))\) rounds, similarly to \(\Delta\)-stepping. Another family of competitors is represented by neighbourhood function-based algorithms [10; 12; 15], which we reviewed in Section 1.1. These algorithms, like the BFS, require \(\Theta(\Phi(G))\) rounds, and are therefore outperformed by our approach on graphs with constant doubling dimension.  
As a final remark on our theoretical results for both the weighted and the unweighted cases, we observe that the \(O(\log^{3}n)\) bound on the ratio between the diameter returned by our strategy and the exact diameter may appear rather weak. However, these theoretical bounds are the result of a number of worst-case approximations which, we conjecture, are unlikely to occur in practice. In fact, in the experiments reported in Section 7.1, our strategy exhibited an accuracy very close to the one of the 2-approximation based on \(\Delta\)-stepping. Although to a lesser extent, the theoretical bounds on the round complexities of the MapReduce implementation may suffer from a similar slackness. An interesting open problem is to perform a tighter analysis of our strategy, at least for specific classes of graphs.