# Distributed Graph Diameter Approximation
## 7 Experiments  
We implemented our algorithms with Rust 1.41.0 (based on LLVM 9.0) on top of Timely Dataflow ([[https://github.com/TimelyDataflow/timelydataflow](https://github.com/TimelyDataflow/timelydataflow)]([https://github.com/TimelyDataflow/timelydataflow](https://github.com/TimelyDataflow/timelydataflow))) (compiled in _release_ mode, with all available optimizations activated). Our implementation, which is publicly available ([[https://github.com/Cecca/diameter-flow/](https://github.com/Cecca/diameter-flow/)]([https://github.com/Cecca/diameter-flow/](https://github.com/Cecca/diameter-flow/))), has been run on a cluster of 12 nodes, each equipped with a 4 core I7-950 processor clocked at a maximum frequency of 3.07 GHz and 18 GB RAM, connected by a 10 Gbit Ethernet network. We configured Timely Dataflow to use 4 threads per machine. We implemented the diameter-approximation algorithm as described in Section 5 (referred to as ClusterDiameter in what follows), by running several instances of RandCluster, each parametrized by a different value of \(r\), until a clustering is found whose corresponding auxiliary graph fits into the memory of a single machine. In order to speed up the computation of the diameter of the auxiliary graph, rather than executing the classical exact algorithm based on all-pairs shortest paths, we run two instances of [PERSON]'s algorithm: the first from an arbitrary node, the second from the farthest reachable node, reporting the largest distance found in the process. We verified that this procedure, albeit providing only a 2-approximation in theory, always finds a very close approximation to the diameter in practice, in line with the findings of [6], while being much faster than the exact diameter computation. The only other deviation from the theoretical algorithm concerns the initial value of \(r\), which is set to the average edge weight (rather than \(w_{min}\)) in order to save on the number of guesses. We compared the performance of our algorithm against the 2-approximation algorithm based on \(\Delta\)-stepping [20], which we implemented in the same Rust/Timely Dataflow framework. In what follows, we will refer to this implementation as DeltaStepping. For this algorithm, we tested several values of \(\Delta\), including fractions and multiples of the average edge weight, reporting, in each experiment, the best result obtained over all tested values of \(\Delta\). We experimented on three graphs: a web graph (sk-2005), a social network (twitter-2010), (both downloaded from the WebGraph collection [35; 36]: [[http://law.di.unimi.it/datasets.php](http://law.di.unimi.it/datasets.php)]([http://law.di.unimi.it/datasets.php](http://law.di.unimi.it/datasets.php))) and a road network (USA, downloaded from [[http://users.diag.uniroma1.it/challenge9/download.shtml](http://users.diag.uniroma1.it/challenge9/download.shtml)]([http://users.diag.uniroma1.it/challenge9/download.shtml](http://users.diag.uniroma1.it/challenge9/download.shtml))). Since both sk-2005 and twitter-2010 are originally unweighted graphs, we generated a weighted version of these graphs by assigning to each edge a random integer weight between 1 and \(n\), with \(n\) being the number of nodes. Also, since the road network USA, on the other hand, is small enough to fit in the memory of a single machine, we inflated it by generating the cartesian product of the network with a linear array of \(S\) nodes and unit edge weights, for a suitable scale parameter \(S\). In the reported experiments we used \(S=5,10\). The rationale behind the use of the cartesian product was to generate a larger network with a topology similar to the original one. For each dataset, only the largest connected component was used in the experiments. Table 1 summarizes the main characteristics of the (largest connected components of the) above benchmark datasets.