# Distributed Graph Diameter Approximation
## 1 Introduction
### Related Work
#### 1.1.2 Approximation Algorithms  
A very simple approximation algorithm, in both weighted and unweighted cases, consists in picking an arbitrary node of the graph, and finding the farthest node from it by solving the Single-Source Shortest Paths problem (SSSP for short). It is easy to see that this is a 2-approximation for the diameter of the graph. This approach has spurred a line of research in which a few SSSP instances are solved, starting from carefully selected nodes, to get a good approximation of the diameter. [PERSON] et al. [6] consider the case of unweighted graphs, and study empirically a simple strategy which achieves very good approximation factors in practice. This algorithm, called 2-Sweep, performs a first BFS from an arbitrary vertex, and a second one from the farthest reachable node, returning the maximum distance found. The theoretical approximation factor achieved by this approach is still 2, like a single BFS, but experiments showed that on some real world graphs the actual value found is much closer to the optimum. Building on this idea, [PERSON] et al. develop IFub algorithm for unweighted graphs [7], and the DiFub algorithm for weighted graphs [8], both of which compute the diameter of a given graph exactly. In the worst case, these algorithms require to solve the APSP problem. However, with an extensive experimental evaluation the authors show that only a small number of BFSs is needed in practice. The drawback affecting these approaches, which are very effective when the graph fits in the memory of a single machine, is the difficulty of parallelizing SSSP computations, especially on loosely coupled architectures such as MapReduce. Another line of research investigates the computation of the _neighbourhood function_ of graphs which can be used, among other things, to approximate the diameter of unweighted graphs. The neighbourhood function \(N_{G}(h)\) of a graph \(G\), also called the _hop plot_[9], is the number of pairs of nodes that are within distance \(h\), for every \(h\geq 0\)[10]. Computing the neighbourhood function exactly requires to store, for each node and each \(h\), the set of nodes reachable within distance \(h\). This results in an overall \(O(n^{2})\) space requirement, which is impractical for large graphs. [PERSON] et al. [10] introduces the _Approximate Neighbourhood Function_ algorithm (abbreviated ANF), where Flajolet-Martin probabilistic counters [11] are used to count the nodes reachable within distance \(h\): each counter requires only \(O(\log n)\) bits, therefore lowering to \(O(n\log n)\) the overall memory requirement. This result is further improved by [PERSON] et al. [12] by replacing Flajolet-Martin counters with HyperLogLog counters [13]. HyperLogLog counters require only \(O(\log\log n)\) bits to count the number of reachable nodes, so the overall memory requirement of the algorithm (called HyperANF) drops to \(O(n\log\log n)\). [PERSON] et al. [14] further extend the algorithm to support the computation of many graph centrality measures. These neighbourhood function approximation algorithms were originally developed for shared memory machines. A MapReduce implementation of ANF, called HADI, is presented by [PERSON] et al. [15]. This MapReduce algorithm suffers mainly of two drawbacks: (a) the memory required is slightly superlinear, and (b) it requires a number of rounds linear in the diameter of the graph. Most importantly, all three of ANF, HyperANF and HADI work _exclusively_ on graphs with unweighted edges. In [14], the HyperANF approach is extended to work for graphs with integer weights on the _nodes_, which are arguably less common than edge-weighted graphs. In the external memory model, where performing even a single BFS has a very high I/O complexity, [PERSON] [16] proposes an approximation algorithm to compute the diameter in the unweighted case in terms of the diameter of an auxiliary graph derived from a clustering of the original graph built around random centers.