A Parallel and Distributed Rust Library for Core Decomposition on Large Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914174579245056 |
|---|---|
| author | Rucci, Davide Parfeniuc, Sebastian Mordacchini, Matteo Carlini, Emanuele Cuzzocrea, Alfredo Dazzi, Patrizio |
| author_facet | Rucci, Davide Parfeniuc, Sebastian Mordacchini, Matteo Carlini, Emanuele Cuzzocrea, Alfredo Dazzi, Patrizio |
| contents | In this paper, we investigate the parallelization of $k$-core decomposition, a method used in graph analysis to identify cohesive substructures and assess node centrality. Although efficient sequential algorithms exist for this task, the scale of modern networks requires faster, multicore-ready approaches. To this end, we adapt a distributed $k$-core algorithm originally proposed by Montresor et al. to shared-memory systems and implement it in Rust, leveraging the language's strengths in concurrency and memory safety. We developed three progressively optimized versions: SequentialK as a baseline, ParallelK introducing multi-threaded message passing, and FastK further reducing synchronization overhead. Extensive experiments on real-world datasets, including road networks, web graphs, and social networks, show that FastK consistently outperforms both SequentialK and ParallelK, as well as a reference Python implementation available in the NetworkX library. Results indicate up to an 11x speedup on 16 threads and execution times up to two orders of magnitude faster than the Python implementation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_00233 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Parallel and Distributed Rust Library for Core Decomposition on Large Graphs Rucci, Davide Parfeniuc, Sebastian Mordacchini, Matteo Carlini, Emanuele Cuzzocrea, Alfredo Dazzi, Patrizio Distributed, Parallel, and Cluster Computing In this paper, we investigate the parallelization of $k$-core decomposition, a method used in graph analysis to identify cohesive substructures and assess node centrality. Although efficient sequential algorithms exist for this task, the scale of modern networks requires faster, multicore-ready approaches. To this end, we adapt a distributed $k$-core algorithm originally proposed by Montresor et al. to shared-memory systems and implement it in Rust, leveraging the language's strengths in concurrency and memory safety. We developed three progressively optimized versions: SequentialK as a baseline, ParallelK introducing multi-threaded message passing, and FastK further reducing synchronization overhead. Extensive experiments on real-world datasets, including road networks, web graphs, and social networks, show that FastK consistently outperforms both SequentialK and ParallelK, as well as a reference Python implementation available in the NetworkX library. Results indicate up to an 11x speedup on 16 threads and execution times up to two orders of magnitude faster than the Python implementation. |
| title | A Parallel and Distributed Rust Library for Core Decomposition on Large Graphs |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2512.00233 |