Clémence Magnien
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.
- Aingworth, Chekuri, and Motwani. 1996. Fast estimation of diameter and shortest paths (without matrix multiplication). In ACM-SIAM SODA. Google Scholar
Digital Library
- Alon, N., Galil, Z., Margalit, O., and Naor, M. 1992. Witnesses for boolean matrix multiplication and for shortest paths. In IEEE FOCS. Google ScholarDigital Library
- Broder, A., Kumar, S., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., and Wiener, J. L. 2000. Graph structure in the web. Computer Networks 33. Google ScholarDigital Library
- Chan, T. M. 2006. All-pairs shortest paths for unweighted undirected graphs in o(mn) time. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. 514--523. Google ScholarDigital Library
- Chepoi, V. D. and Dragan, F. F. 1994. Linear-time algorithm for finding a central vertex of a chordal graph. In Proceedings of the second Annual European Symposium Algorithms, ESA'94, LNCS. Vol. 855. Google ScholarDigital Library
- Corneil, D., Dragan, F., Habib, M., and Paul, C. 2001. Diameter determination on restricted graph families. Discrete Applied Mathematics 113, 2-3. Google ScholarDigital Library
- Corneil, D., Dragan, F., and Köhler, E. 2003. On the power of bfs to determine a graph's diameter. Networks 42 (4).Google Scholar
- Dor, D., Halperin, S., and Zwick, U. 1997. All pairs almost shortest paths. ECCC 4, 040.Google Scholar
- Dragan, F., Nicolai, F., and Brandstädt, A. 1997. Lexbfs-orderings and powers of graphs. In Proceedings of the 22nd international workshop. Graph-Theoretic Concepts in Computer Science, WG'96, LNCS. Vol. 1197. Google ScholarDigital Library
- Dragan, F. F. 2005. Estimating all pairs shortest paths in restricted graph families: a unified approach. J. Algorithms 57, 1, 1--21.Google ScholarDigital Library
- Faloutsos, M., Faloutsos, P., and Faloutsos, C. 1999. On power-law relationships of the internet topology. In ACM SIGCOMM. Google ScholarDigital Library
- Feder, T. and Motwani, R. 1991. Clique partitions, graph compression, and speeding-up algorithms. In ACM STOC. Google ScholarDigital Library
- Handler, G. 1973. Minimax location of a facility in an undirected tree graph. Transportation Science 7 (3).Google Scholar
- Latapy, M. and Magnien, C. 2008. Complex network measurements: Estimating the relevance of observed properties. To appear in the proceedings of ieee infocom.Google Scholar
- Leskovec, J., Kleinberg, J., and Faloutsos, C. 2005. Graphs over time: Densification laws, shrinking diameters and possible explanations. In ACM SIGKDD. Google ScholarDigital Library
- Parnas, M. and Ron, D. 2002. Testing the diameter of graphs. Random Struct. Algorithms 20, 2, 165--183. Google ScholarDigital Library
- Seidel, R. 1992. On the all-pairs-shortest-path problem. In ACM STOC. Google ScholarDigital Library
- Watts, D. and Strogatz, S. 1998. Collective dynamics of small-world networks. Nature 393.Google Scholar
- Zwick, U. 2001. Exact and approximate distances in graphs—A survey. In ESA. Vol. 2161. Google ScholarDigital Library
Index Terms
- Fast computation of empirically tight bounds for the diameter of massive graphs
Recommendations
Tight conditional lower bounds for approximating diameter in directed graphs
STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of ComputingAmong the most fundamental graph parameters is the Diameter, the largest distance between any pair of vertices in a graph. Computing the Diameter of a graph with m edges requires m2−o(1) time under the Strong Exponential Time Hypothesis (SETH), which ...
A diameter-revealing proof of the Bondy-Lovász lemma
Highlights- The Bondy-Lovász lemma is strengthened with an upper bound on the graph diameter.
AbstractWe present a strengthened version of a lemma due to Bondy and Lovász. This lemma establishes the connectivity of a certain graph whose nodes correspond to the spanning trees of a 2-vertex-connected graph, and implies the k = 2 case of ...
Bounds on the fault-diameter of graphs
Let G be a k+1-connected or k+1-edge-connected graph, where k∈ï ź. The k-fault-diameter and k-edge-fault-diameter of G is the largest diameter of the subgraphs obtained from G by removing up to k vertices and edges, respectively. In this paper we give ...
Comments