icentral-brandes

The icentral-brandes crate is a comprehensive Rust implementation of the Brandes algorithm tailored for efficient computation of betweenness centrality in large and complex graphs. The crate facilitates both standard and incremental betweenness centrality computations. This is achieved through advanced data structures specifically designed to handle graph adjacency, path counting, and dependency tracking with precision. The crate leverages multi-threading capabilities and mutable graph access, ensuring optimal performance for processing high-density networks.

Features

• Flexible Workspace Setup: Provides distinct workspace structures optimized for different stages and strategies of the Brandes algorithm.
• Incremental Updates: Efficiently recalculates betweenness centrality scores when edges are added, without the need for recomputing everything from scratch.
• Parallel Execution: Utilizes Rust's concurrency model to handle graph computations in a thread-safe manner.
• Customizable Graph Interaction: Interfaces seamlessly with graphs providing node neighbor insights and shortest path calculations.
• Rich Debugging Information: Facilitates deep debugging through comprehensive log tracing of algorithmic operations.

Usage

use icentral_brandes::{BrandesDeltaStepAdjacentWorkspace, brandes_betweenness_centrality};

fn main() {
    let graph = // Initialize your graph here
    let scores = brandes_betweenness_centrality(&graph).expect("Failed to compute betweenness centrality");
    // Use the scores...
}

Technical Details

Classes within this crate meticulously handle edge case scenarios to ensure consistency across various graph topologies. Techniques such as the Delta-stepping approach and adjacency-based stepping offer precise control over node evaluation and path discovery processes, yielding accurate centrality measures.

The Delta-step methods provide increased efficiency by partitioning graph iterations and selectively adjusting dependencies, beneficial for dynamically evolving graph structures.

Note

This README.md was generated by an AI model and may not be 100% accurate, though should be pretty good.

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.