Distributed Graph Diameter Approximation
We present an algorithm for approximating the diameter of massive weighted undirected graphs on distributed platforms supporting a MapReduce-like abstraction. In order to be efficient in terms of both time and space, our algorithm is based on a decomposition strategy which partitions the graph into...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-09-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/13/9/216 |
| _version_ | 1827707053666205696 |
|---|---|
| author | Matteo Ceccarello Andrea Pietracaprina Geppino Pucci Eli Upfal |
| author_facet | Matteo Ceccarello Andrea Pietracaprina Geppino Pucci Eli Upfal |
| author_sort | Matteo Ceccarello |
| collection | DOAJ |
| description | We present an algorithm for approximating the diameter of massive weighted undirected graphs on distributed platforms supporting a MapReduce-like abstraction. In order to be efficient in terms of both time and space, our algorithm is based on a decomposition strategy which partitions the graph into disjoint clusters of bounded radius. Theoretically, our algorithm uses linear space and yields a polylogarithmic approximation guarantee; most importantly, for a large family of graphs, it features a round complexity asymptotically smaller than the one exhibited by a natural approximation algorithm based on the state-of-the-art <inline-formula><math display="inline"><semantics><mo>Δ</mo></semantics></math></inline-formula>-stepping SSSP algorithm, which is its only practical, linear-space competitor in the distributed setting. We complement our theoretical findings with a proof-of-concept experimental analysis on large benchmark graphs, which suggests that our algorithm may attain substantial improvements in terms of running time compared to the aforementioned competitor, while featuring, in practice, a similar approximation ratio. |
| first_indexed | 2024-03-10T16:39:09Z |
| format | Article |
| id | doaj.art-cb8ac5b3f70c40c08c2de66f18f0c972 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-10T16:39:09Z |
| publishDate | 2020-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-cb8ac5b3f70c40c08c2de66f18f0c9722023-11-20T12:13:02ZengMDPI AGAlgorithms1999-48932020-09-0113921610.3390/a13090216Distributed Graph Diameter ApproximationMatteo Ceccarello0Andrea Pietracaprina1Geppino Pucci2Eli Upfal3Faculty of Computer Science, Free University of Bozen, 39100 Bolzano, ItalyDepartment of Information Engineering, University of Padova, 35131 Padova, ItalyDepartment of Information Engineering, University of Padova, 35131 Padova, ItalyDepartment of Computer Science, Brown University, Providence, RI 02912, USAWe present an algorithm for approximating the diameter of massive weighted undirected graphs on distributed platforms supporting a MapReduce-like abstraction. In order to be efficient in terms of both time and space, our algorithm is based on a decomposition strategy which partitions the graph into disjoint clusters of bounded radius. Theoretically, our algorithm uses linear space and yields a polylogarithmic approximation guarantee; most importantly, for a large family of graphs, it features a round complexity asymptotically smaller than the one exhibited by a natural approximation algorithm based on the state-of-the-art <inline-formula><math display="inline"><semantics><mo>Δ</mo></semantics></math></inline-formula>-stepping SSSP algorithm, which is its only practical, linear-space competitor in the distributed setting. We complement our theoretical findings with a proof-of-concept experimental analysis on large benchmark graphs, which suggests that our algorithm may attain substantial improvements in terms of running time compared to the aforementioned competitor, while featuring, in practice, a similar approximation ratio.https://www.mdpi.com/1999-4893/13/9/216graph analyticsparallel graph algorithmsweighted graph decompositionweighted diameter approximationMapReduce |
| spellingShingle | Matteo Ceccarello Andrea Pietracaprina Geppino Pucci Eli Upfal Distributed Graph Diameter Approximation Algorithms graph analytics parallel graph algorithms weighted graph decomposition weighted diameter approximation MapReduce |
| title | Distributed Graph Diameter Approximation |
| title_full | Distributed Graph Diameter Approximation |
| title_fullStr | Distributed Graph Diameter Approximation |
| title_full_unstemmed | Distributed Graph Diameter Approximation |
| title_short | Distributed Graph Diameter Approximation |
| title_sort | distributed graph diameter approximation |
| topic | graph analytics parallel graph algorithms weighted graph decomposition weighted diameter approximation MapReduce |
| url | https://www.mdpi.com/1999-4893/13/9/216 |
| work_keys_str_mv | AT matteoceccarello distributedgraphdiameterapproximation AT andreapietracaprina distributedgraphdiameterapproximation AT geppinopucci distributedgraphdiameterapproximation AT eliupfal distributedgraphdiameterapproximation |