icentral-test-incremental-brandes

icentral-test-incremental-brandes is a Rust crate designed for efficiently computing betweenness centrality in dynamic graphs using incremental updates, a vital aspect of network analysis commonly used in sociology, computer networking, and recommendation systems. This crate provides advanced algorithms that enable the computation of centrality measures while minimizing computational overhead when graph topology updates occur.

Features

• Incremental Centrality Computation: Performs efficient updates of betweenness centrality scores upon edge insertions in a graph.
• Concurrency: Utilizes Rust's Arc and Mutex for safe concurrent graph manipulation.
• Performance Analysis: Outputs detailed runtime analysis and speedup graphs for empirical evaluation.

Usage

To use this crate, include it in your Cargo.toml:

[dependencies]
icentral-test-incremental-brandes = "0.1.0"

Here is an example demonstrating its basic usage:

use icentral_test_incremental_brandes::{exp_inc_brandes_p, incremental_brandes_test};
// Import other necessary items...

fn main() {
    // Your setup code...
    if let Ok(()) = exp_inc_brandes_p(graph, Some(100), &rand_edge_vec, brandes_time) {
        // Process results...
    }
}

Consult the respective method documentation for detailed parameters and expected behaviors.

Concepts

This crate implements variations of Brandes' algorithm for dynamic settings:

• Incremental Brandes: Efficiently updates the centrality scores as graph changes occur.
• Parallel Processing: Achieves faster computations leveraging multi-threaded operations enabled by the Rust concurrency model.

Mathematical Background

Betweenness centrality quantifies the influence of a node over the flow of information between other nodes, defined as: [ C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma(s, t | v)}{\sigma(s, t)} ] where ( \sigma(s, t) ) is the total number of shortest paths from node ( s ) to node ( t ), and ( \sigma(s, t | v) ) is the number of those paths passing through some node ( v ).

License

This project is licensed under the MIT License - see the LICENSE file for details.

Disclaimer: This README.md file was generated by an AI model and may not be 100% accurate however it 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.