iCentral Test Incremental QUBE

icentral-test-incremental-qube is an advanced Rust crate designed for efficiently calculating betweenness centrality updates in dynamic graph structures. The primary focus is the implementation of algorithms facilitating the rapid updating of centrality scores upon incremental changes, such as edge insertions, exploiting the properties of Minimum Union Cycles (MUCs).

Features

• Incremental Centrality Computation: Quickly update betweenness centrality scores leveraging MUCs without computing from scratch.
• Efficient Edge Handling: Seamlessly integrates new edges using specialized graph data structures for skewed properties.
• Performance Analysis: Built-in functions to monitor and log computational time, speedups, and other performance metrics compared to traditional Brandes algorithm.

Usage

This crate requires setting up a Graph type with specific trait implementations:

use icentral_test_incremental_qube::exp_inc_qube_p;

let mut graph = /* initialize graph here */;
let rand_edge_vec = /* vector of edges to insert */;
let brandes_time = /* timing from Brandes computation */;

exp_inc_qube_p(&mut graph, None, &rand_edge_vec, brandes_time).expect("Failed to update betweenness centrality");

Mathematical Concepts

• Betweenness Centrality: A measure of a vertex's significance in terms of the number of shortest paths passing through it in the graph.
• Minimum Union Cycles (MUCs): Graph substructures used here to optimize the edge insertion process leading to expedited centrality recalculations.

Technical Requirements

This crate requires the implementation of several traits for the Graph generics, such as InsertEdgeUpdateMuc, NodeIdToMucId, and others, facilitating the interaction with the graph's internal structure.

Safety and Warnings

The crate is designed with performance in mind. Ensure that graph operations do not lead to unintentional data races or memory issues, particularly under concurrent contexts.

Disclaimer

This README was generated by an AI model and may not be 100% precise. However, it should serve as a comprehensive guide to the functionalities and usage of the crate.

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.