Icentral Parallel Brandes

The icentral-parallel-brandes crate implements an optimized parallel version of Brandes' algorithm to compute betweenness centrality in large-scale graphs. This algorithm distributes computation across multiple threads, thereby achieving enhanced efficiency and performance compared to its sequential counterpart.

Overview

Brandes' algorithm is a fundamental technique in network analysis for quantifying the importance of nodes within a graph based on shortest paths. This crate leverages Rust's concurrency capabilities to improve the execution time with parallel computation, enabling rapid analysis of substantial graphs.

Key Features

• Parallel Execution: Utilizes multiple threads to process subgraphs concurrently, which reduces computation time significantly.
• Generic Graph Interface: Works with any graph structure implementing the NumNodes, MappedNodes, GetNodeIdRange, GetNeighborsForNode, and GetEdges traits.
• Efficient Memory Management: The design ensures minimal overhead and optimal performance through careful allocation and deallocation.

Usage

To use this crate, add the following to your Cargo.toml:

[dependencies]
icentral-parallel-brandes = "0.1.0"

Then, import and use the parallel_brandes function in your Rust code:

use icentral_parallel_brandes::parallel_brandes;

// Assume `MyGraph` implements necessary traits
let my_graph = MyGraph::new();
let mut scores = BetweennessScores::new();

parallel_brandes(&my_graph, &mut scores).expect("Algorithm execution failed");

About

This crate is suited for applications in network analysis, where analyzing the betweenness centrality of nodes in massive graphs is crucial such as social network analysis, infrastructure planning, and more.

Note: This README.md file was generated by an AI model and may not be 100% accurate; however, it should provide significant guidance.

Further Reading

Further understanding of the algorithm's theoretical background can be found in U. Brandes, "A Faster Algorithm for Betweenness Centrality," Journal of Mathematical Sociology, 2001.

This crate is in the process of being translated from c++ to rust. Currently, it still needs exhaustive testing. It is likely there currently exist many glitches which need to be fixed before proper usage. This crate is based on the original icentral program developed by Fuad Jamor. Please see the following repository for details: https://github.com/fjamour/icentral.

For progress updates, see the workspacer rust project.