Fast computation of empirically tight bounds for the diameter of massive graphs
- 23 February 2009
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Journal of Experimental Algorithmics
- Vol. 13, 10
- https://doi.org/10.1145/1412228.1455266
Abstract
The diameter of a graph is among its most basic parameters. Since a few years ago, it moreover became 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 here a new approach relying on very simple and fast algorithms that compute (upper and lower) bounds for the diameter. We show empirically that, on various real-world cases representative of complex networks studied in the literature, the obtained bounds are very tight (and even equal in some cases). This leads to rigorous and very accurate estimations of the actual diameter in cases which were previously untractable in practice.Keywords
This publication has 12 references indexed in Scilit:
- Complex Network Measurements: Estimating the Relevance of Observed PropertiesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2008
- Graphs over timePublished by Association for Computing Machinery (ACM) ,2005
- On the power of BFS to determine a graph's diameterNetworks, 2003
- Diameter determination on restricted graph familiesDiscrete Applied Mathematics, 2001
- Graph structure in the WebComputer Networks, 2000
- On power-law relationships of the Internet topologyPublished by Association for Computing Machinery (ACM) ,1999
- Collective dynamics of ‘small-world’ networksNature, 1998
- On the all-pairs-shortest-path problemPublished by Association for Computing Machinery (ACM) ,1992
- Clique partitions, graph compression and speeding-up algorithmsPublished by Association for Computing Machinery (ACM) ,1991
- Minimax Location of a Facility in an Undirected Tree GraphTransportation Science, 1973