Fast computation of empirically tight bounds for the diameter of massive graphs

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.

REFERENCES

• 1: D. Aingworth , C. Chekuri , R. Motwani, Fast estimation of diameter and shortest paths (without matrix multiplication), Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.547-553, January 28-30, 1996, Atlanta, Georgia, United States
• 2: N. Alon , Z. Galil , O. Margalit , M. Naor, Witnesses for Boolean matrix multiplication and for shortest paths, Proceedings of the Proceedings., 33rd Annual Symposium on Foundations of Computer Science, p.417-426, October 24-27, 1992 [doi>10.1109/SFCS.1992.267748]
• 3: Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.309-320, June 2000
• 4: Timothy M. Chan, All-pairs shortest paths for unweighted undirected graphs in o(mn) time, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.514-523, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109614]
• 5: Victor Chepoi , Feodor F. Dragan, A Linear-Time Algorithm for Finding a Central Vertex of a Chordal Graph, Proceedings of the Second Annual European Symposium on Algorithms, p.159-170, September 26-28, 1994
• 6: Derek G. Corneil , Feodor E. Dragan , Michel Habib , Christophe Paul, Diameter determination on restricted graph families, Discrete Applied Mathematics, v.113 n.2-3, p.143-166, October 15, 2001 [doi>10.1016/S0166-218X(00)00281-X]
• 7: Corneil, D., Dragan, F., and Köhler, E. 2003. On the power of bfs to determine a graph's diameter. Networks 42 (4).
• 8: Dor, D., Halperin, S., and Zwick, U. 1997. All pairs almost shortest paths. ECCC 4, 040.
• 9: Feodor F. Dragan , Falk Nicolai , Andreas Brandstädt, LexBFS-Orderings and Power of Graphs, Proceedings of the 22nd International Workshop on Graph-Theoretic Concepts in Computer Science, p.166-180, June 12-14, 1996
• 10: Feodor F. Dragan, Estimating all pairs shortest paths in restricted graph families: a unified approach, Journal of Algorithms, v.57 n.1, p.1-21, September 2005 [doi>10.1016/j.jalgor.2004.09.002]
• 11: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 12: Tomás Feder , Rajeev Motwani, Clique partitions, graph compression and speeding-up algorithms, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.123-133, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103424]
• 13: Handler, G. 1973. Minimax location of a facility in an undirected tree graph. Transportation Science 7 (3).
• 14: Latapy, M. and Magnien, C. 2008. Complex network measurements: Estimating the relevance of observed properties. To appear in the proceedings of ieee infocom.
• 15: Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081893]
• 16: Michal Parnas , Dana Ron, Testing the diameter of graphs, Random Structures & Algorithms, v.20 n.2, p.165-183, March 2002 [doi>10.1002/rsa.10013.abs]
• 17: Raimund Seidel, On the all-pairs-shortest-path problem, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.745-749, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129784]
• 18: Watts, D. and Strogatz, S. 1998. Collective dynamics of small-world networks. Nature 393.
• 19: Uri Zwick, Exact and Approximate Distances in Graphs - A Survey, Proceedings of the 9th Annual European Symposium on Algorithms, p.33-48, August 28-31, 2001

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms

Keywords:
Diameter bounds, graph diameter