PROPAGATE: A Seed Propagation Framework to Compute Distance-Based Metrics on Very Large Graphs
Fuente:
Zenodo
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Recurso digital |
| Veröffentlicht: |
Zenodo
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866901340087648256 |
|---|---|
| author | Amati, Giambattista Cruciani, Antonio VOCCA, Paola Pasquini, Daniele Angelini, Simone |
| author_facet | Amati, Giambattista Cruciani, Antonio VOCCA, Paola Pasquini, Daniele Angelini, Simone |
| contents | <p>We propose PROPAGATE, a fast approximation framework to estimate distance-based metrics on very large graphs such as: the (effective) diameter or the average distance within a small error. The framework assigns seeds to nodes and propagates them in a BFS-like fashion, computing the neighbors set until we obtain either the whole vertex set (for computing the diameter) or a given percentage of vertices (for the effective diameter). At each iteration, we derive compressed Boolean representations of the neighborhood sets discovered so far. The PROPAGATE framework yields two algorithms: PROPAGATE-P, which propagates all the $m$ seeds in parallel, and PROPAGATE-S which propagates the seeds sequentially. <br>For each node, the compressed representation of the \Bool\til algorithm requires $m$ bits while PROPAGATE-S $1$ bit only. Both algorithms compute the average distance, the effective diameter, the diameter, and the connectivity rate (a measure of the the sparseness degree of the transitive closure graph) within a small error with high probability: for any $\varepsilon>0$ and using $m=\Theta\left(\frac{\log n}{\varepsilon^2}\right)$ sample nodes, the error for the average distance is bounded by $\xi = \frac{\varepsilon \Delta}{\alpha}$; the errors for the effective diameter and the diameter are bounded by $\xi = \frac{\varepsilon}{\alpha}$; and the error for the connectivity rate is bounded by $\varepsilon$ where $\Delta$ is the diameter and $\alpha$ is the connectivity rate. The time complexity of our approaches is $\mathcal{O}(\Delta\cdot m)$ for PROPAGATE-P and $\mathcal{O}\left(\frac{\log n}{\varepsilon^2}\cdot \Delta \cdot m\right)$ for PROPAGATE-S, where $m$ is the number of edges of the graph and $\Delta$ is the diameter.</p> <p>The experimental results show that the PROPAGATE framework improves the current state of the art in accuracy, speed, and space. Moreover, we experimentally show that PROPAGATE is also very efficient for solving the All Pair Shortest Path problem in very large graphs.</p> |
| format | Recurso digital |
| id | zenodo_https___doi_org_10_1007_978-3-031-43418-1_40 |
| institution | Zenodo |
| language | |
| publishDate | 2026 |
| publisher | Zenodo |
| record_format | zenodo |
| spellingShingle | PROPAGATE: A Seed Propagation Framework to Compute Distance-Based Metrics on Very Large Graphs Amati, Giambattista Cruciani, Antonio VOCCA, Paola Pasquini, Daniele Angelini, Simone Graph theory Graph mining Effective Diameter Shortest Paths sampling <p>We propose PROPAGATE, a fast approximation framework to estimate distance-based metrics on very large graphs such as: the (effective) diameter or the average distance within a small error. The framework assigns seeds to nodes and propagates them in a BFS-like fashion, computing the neighbors set until we obtain either the whole vertex set (for computing the diameter) or a given percentage of vertices (for the effective diameter). At each iteration, we derive compressed Boolean representations of the neighborhood sets discovered so far. The PROPAGATE framework yields two algorithms: PROPAGATE-P, which propagates all the $m$ seeds in parallel, and PROPAGATE-S which propagates the seeds sequentially. <br>For each node, the compressed representation of the \Bool\til algorithm requires $m$ bits while PROPAGATE-S $1$ bit only. Both algorithms compute the average distance, the effective diameter, the diameter, and the connectivity rate (a measure of the the sparseness degree of the transitive closure graph) within a small error with high probability: for any $\varepsilon>0$ and using $m=\Theta\left(\frac{\log n}{\varepsilon^2}\right)$ sample nodes, the error for the average distance is bounded by $\xi = \frac{\varepsilon \Delta}{\alpha}$; the errors for the effective diameter and the diameter are bounded by $\xi = \frac{\varepsilon}{\alpha}$; and the error for the connectivity rate is bounded by $\varepsilon$ where $\Delta$ is the diameter and $\alpha$ is the connectivity rate. The time complexity of our approaches is $\mathcal{O}(\Delta\cdot m)$ for PROPAGATE-P and $\mathcal{O}\left(\frac{\log n}{\varepsilon^2}\cdot \Delta \cdot m\right)$ for PROPAGATE-S, where $m$ is the number of edges of the graph and $\Delta$ is the diameter.</p> <p>The experimental results show that the PROPAGATE framework improves the current state of the art in accuracy, speed, and space. Moreover, we experimentally show that PROPAGATE is also very efficient for solving the All Pair Shortest Path problem in very large graphs.</p> |
| title | PROPAGATE: A Seed Propagation Framework to Compute Distance-Based Metrics on Very Large Graphs |
| topic | Graph theory Graph mining Effective Diameter Shortest Paths sampling |
| url | https://doi.org/10.1007/978-3-031-43418-1_40 |