# Distributed Graph Diameter Approximation
## 7 Experiments
### Strong Scaling  
In this section we investigate the _strong scaling_ properties of ClusterDiameter, varying the number of machines employed while maintaining the input instance fixed. The results are reported in Figure 7, where, for each graph, we report results starting from the minimum number of machines for which we were able to complete the experiment successfully, avoiding running out of memory.  
We observe that, in general, our implementation of ClusterDiameter scales gracefully with the number of machines employed. It is worth discussing some phenomena that can be observed in the plot, and that are due to peculiarities of our hardware experimental platform. Specifically, on twitter-2010 we observe a very large difference between the running times on 4 and 6 machines. The reason for this behaviour is that for this dataset, on our system, when using 4 machines our implementation incurs a heavy use of swap space on disk when building the clustering. Interestingly, the slightly larger graph sk-2005 does not trigger this effect. This difference is due to the fact that twitter-2010 exhibits faster expansion (the median number of hops between nodes is 5 on twitter-2010, and 15 on sk-2005), therefore on twitter-2010 the implementation needs to allocate much larger buffers to store messages in each round. From 6 machines onwards, the scaling pattern is similar to the other datasets, as detailed in the smaller inset plot. Similarly, on USA-x5, the scaling is very smooth except between 4 and 6 machines, where the improvement in performance is more marked. The reason again is that on 2 and 4 machines the implementation makes heavy use of swap space on disk during the construction of the auxiliary graph.  
Figure 6: Scalability with respect to the size of the graph for algorithms ClusterDiameter DeltaStepping, and a Sequential approximation obtained running [PERSON]’s algorithm. The \(x\) axis reports the _scale_ of the graph, that is the number of layers used to inflate the original dataset. For USA-x10 (rightmost point), the sequential algorithm could not load the entire graph in memory, whereas DeltaStepping timed out after five hours.  
We remark that the experimental evaluation reported in this section focus exclusively on weighted graphs. A set of experiments, omitted for the sake of brevity, has shown that, on unweighted graphs of small diameter, a distributed implementation of BFS is able to outperform our algorithm, due to its smaller constant factors, while for unweighted graphs of higher diameter we obtained results consistent with those reported in this section for the weighted USA dataset.  
Conceptualization, M.C., A.P., G.P. and E.U.; methodology, M.C., A.P., G.P. and E.U.; software, M.C., A.P., G.P. and E.U.; validation, M.C., A.P., G.P. and E.U.; formal analysis, M.C., A.P., G.P. and E.U.; investigation, M.C., A.P., G.P. and E.U.; resources, M.C., A.P., G.P. and E.U.; data curation, M.C., A.P., G.P. and E.U.; writing-original draft preparation, M.C., A.P., G.P. and E.U.; writing-review and editing, M.C., A.P., G.P. and E.U.; visualization, M.C., A.P., G.P. and E.U.; funding acquisition, M.C., A.P., G.P. and E.U. All authors have read and agreed to the published version of the manuscript.  
This research was funded in part by MIUR, the Italian Ministry of Education, University and Research, under PRIN Project n. 20174 LF378 AHeAD (Efficient Algorithms for Harmessing Networked Data), and grant L. 232 (Dipartimenti di Ecolenza), and by the University of Padova under project \"SID 2020: Resource-Allocation Tradeoffs for Dynamic and Extreme Data\", and by NSF awards CCF 1740741 and IIS 181344.  
The authors wish to thank the anonymous referees for their constructive criticisms which helped improve the quality of the paper.  
The authors declare no conflict of interest. The funders had no role in the design of the study; in the collection, analyses, or interpretation of data; in the writing of the manuscript, or in the decision to publish the results.