The diameter of a graph, i.e. the maximal distance between all pairs of vertices, is among its most basic parameters; it is moreover a key issue to compute it for massive graphs in the context of complex network analysis. However, known algorithms, including the ones producing approximate values, have too high a time and/or space complexity to be used in such cases.
We propose in Fast Computation of Empirically Tight Bounds for the Diameter of Massive Graphs, by Clémence Magnien, Matthieu Latapy and Michel Habib (ACM JEA 13, 2009) a new approach relying on very simple and fast algorithms that compute (upper and lower) bounds for the diameter.
This page provides the program and data used in this paper. The program is provided 'as is', with absolutely no warranty. It is written in C, designed for use on Unix/Linux systems, but it should be easily portable to any platform.
You may use and distribute this code, provided that you cite the paper above and this web page. You may also write us an e-mail (clemence.magnien at lip6.fr) if you find it useful, if you find a bug, or have any improvement.
Download: