A Parallel and Distributed Rust Library for Core Decomposition on Large Graphs

1 st Davide Rucci, 2 nd Sebastian Parfeniuc, 3 rd Matteo Mordacchini, 4 th Emanuele Carlini, 5 th Alfredo Cuzzocrea, 6 th Patrizio Dazzi · 2025

Read A Parallel and Distributed Rust Library for Core Decomposition on Large Graphs by 1 st Davide Rucci, 2 nd Sebastian Parfeniuc, 3 rd Matteo Mordacchini, 4 th Emanuele Carlini, 5 th Alfredo Cuzzocrea, 6 th Patrizio Dazzi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-00233.txt.

Introduction

Breaking a graph into its dense cores reveals cohesive groups and central nodes. Davide Rucci and co-authors investigate parallel k-core decomposition in a 2025 study, implemented as a Rust library. Sequential algorithms exist, but modern networks are too large for one processor.

The library is built for multicore and distributed use on large graphs. Core decomposition helps analysts assess node centrality and find tightly knit substructures in social, web, and infrastructure networks. A fast, shared implementation gives researchers a practical tool for graphs that no longer fit comfortably in a single machine's workflow. Rust's speed and safety guarantees suit a library meant for heavy graph workloads. Core decomposition is also a preprocessing step for many community detection methods.

Catalog record

CREATOR1 st Davide Rucci, 2 nd Sebastian Parfeniuc, 3 rd Matteo Mordacchini, 4 th Emanuele Carlini, 5 th Alfredo Cuzzocrea, 6 th Patrizio Dazzi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-00233

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Parallel and Distributed Rust Library for Core Decomposition on Large Graphs Thanks: This work is supported by Spoke 1 and Spoke 6 of the ICSC National Research Centre for High Performance Computing, Big Data and Quantum Computing within the NextGenerationEU program (Project Code: PNRR CN00000013). 1 st Davide Rucci, 2 nd Sebastian Parfeniuc, 3 rd Matteo Mordacchini, 4 th Emanuele Carlini, 5 th Alfredo Cuzzocrea, 6 th Patrizio Dazzi Abstract In this paper, we investigate the parallelization of k 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 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 11× speedup on 16 threads and execution times up to two orders of magnitude faster than the Python implementation. I Introduction Graph-structured data have become a central abstraction across diverse application domains, from social and communication networks to biological interaction graphs, transportation systems, and the web itself [ 19 , 29 , 17 , 30 , 42 ] . In recent years, graph-based modeling has extended well beyond traditional network science, becoming a unifying framework for reasoning about interactions, dependencies, and optimization in heterogeneous systems. Graph representations have been proposed for centralized [ 1 , 24 ] and decentralized social platforms [ 15 ] , mobile communication networks [ 39 , 6 , 31 ] , vehicular ad hoc systems [ 34 ] , resource allocation [ 12 ] and load distribution in IoT/edge [ 41 , 5 , 11 ] and fog computing [ 18 ] . In the context of cloud infrastructures [ 43 ] and federated learning [ 23 , 2 , 21 ] , graphs capture data flow, task placement, and collaboration patterns among distributed agents. Similarly, graph abstractions are increasingly employed in cybersecurity, recommendation systems [ 14 ] , biological networks, and optimization of large-scale computing environments. This proliferation underscores the versatility of graph-based solutions as a foundation for both theoretical analysis and practical system design. Given this wide range of applications, identifying key structural features of graphs is essential for both understanding and optimizing system behavior. Among the available graph analysis tools, the k-core decomposition [ 35 ] stands out for its simplicity, interpretability, and analytical power. It provides a hierarchical peeling of the network, identifying progressively denser subgraphs that can reveal communities, influential actors, and structural weaknesses. The coreness of a node represents the highest k such that the node belongs to the k th core, which can be computed directly through standard linear-time algorithms [ 26 ] (see also Section II ). The coreness metric captures a network’s community structure [ 27 , 13 , 32 , 3 ] and serves as a meaningful node importance score [ 22 , 40 ] , complementing measures such as degree and h -index. Its sensitivity to structural anomalies also makes it valuable for detecting outliers [ 36 , 8 ] . Despite the existence of efficient sequential algorithms, e.g. most notably the linear-time approach of Batagelj and Zaversnik [ 4 ] , the rapid growth of real-world graphs in both size and density poses new computational challenges [ 33 ] . Modern social or web graphs routinely include hundreds of millions of vertices and billions of edges, stressing the limits of single-core memory bandwidth and cache capacity. As data volumes continue to expand, exploiting multicore and many-core architectures becomes essential to preserve interactivity and scalability in graph analytics workflows. This transition, however, is not straightforward: irregular memory access patterns, data dependencies, and load imbalance make graph algorithms notoriously difficult to parallelize effectively. A variety of parallel and distributed k -core algorithms have been proposed to address these challenges. Shared-memory systems typically rely on fine-grained parallel peeling, dynamic work distribution, or frontier-based processing, while distributed systems adopt message-passing protocols that exchange local degree estimates among neighboring vertices. Among the latter, the decentralized algorithm by Montresor et al. [ 28 ] offers an elegant, asynchronous formulation particularly suited for large-scale and failure-tolerant environments. Yet, adapting such distributed designs to shared-memory architectures raises non-trivial issues related to synchronization cost, cache coherence, and contention on shared data structures. Achieving high performance while preserving correctness and determinism requires careful engineering of communication patterns and memory layouts. In this paper, we introduce a Rust-based parallel library for k -core decomposition, which leverages ideas from both distributed protocols and shared-memory execution. Rust provides a unique combination of low-level control and strong compile-time safety guarantees: its ownership model eliminates data races, while zero-cost abstractions and fine-grained concurrency primitives make it suitable for high-performance scientific computing. Ultimately, we design a shared-memory adaptation that maintains the decentralized spirit of message-passing while minimizing synchronization and communication overhead. We introduce three progressively optimized implementations. SequentialK serves as a correctness baseline and performance reference. ParallelK explores multi-threaded execution using message queues and synchronization barriers, leveraging both high-level thread-pool abstractions and native threads. Finally, FastK refines this design with cache-aware data structures, global shared states, and selective message propagation to reduce contention and improve convergence speed. Through extensive experiments on large real-world graphs, including road networks, social networks, and web graphs, we show that FastK consistently achieves substantial gains over both our baselines and widely used Python implementations such as NetworkX [ 16 ] , delivering up to 11× speedup on 16 cores and execution times two orders of magnitude faster. Beyond performance, our results demonstrate the practical viability of Rust for graph analytics: it combines efficiency and memory safety without sacrificing low-level control. The proposed library contributes reusable building blocks for parallel and distributed graph algorithms, paving the way toward safer, high-performance data-intensive computation. To present these results, the remainder of this paper is organized as follows. Section II provides the basic definitions and background about the k -core decomposition. Section II frames our work with the relevant scientific literature. Section III details parallel Rust implementations and their design choices. Section IV introduces FastK and its optimizations along with synchronization and activation strategies. Section V presents the experimental methodology, datasets, and results; Section VI draws concluding remarks. II Background and Related Work The concept of the k -core, first introduced by Seidman [ 35 ] , provides a fundamental tool for analyzing the structure of complex networks. Intuitively, a k -core is a maximal subgraph in which every vertex has at least k neighbors within the subgraph. Formally: Definition 1 ( k -core [ 35 ] ) For any positive integer k , the k -core of a graph G=(V,E) is the inclusion-maximal subset K\subseteq V such that the induced subgraph G[K] contains only vertices of degree at least

Read the complete text