ICentral Partial BBFS

Overview

icentral-partial-bbfs is a Rust crate designed to manage dynamic changes in graphs by leveraging a variant of the Betweenness Centrality computations through Partial Brandes' Breadth-First Searching (BBFS). The primary functionality of this crate lies in allowing efficient updates to the workspace representation of a graph upon addition or deletion of edges, ensuring that alterations in betweenness centrality are accurately captured and efficiently recalculated.

Functionality

• update_workspace_for_partial_bbfs_addition: This function updates the graph's workspace upon an edge addition. It iteratively calculates new path counts and modifies the workspace's internal data structures to reflect the change.

• partial_bbfs_addition: Handles the introduction of a new edge into the graph. The function determines the optimal direction for computing paths and subsequently manages workspace updates to encapsulate this structural addition.

• partial_bbfs_deletion: This function is designed to manage the removal of an edge. Utilizing a full reconstruction strategy temporarily, it re-initializes pertinent data structures, acknowledges the edge removal, and recalculates relevant betweenness centrality scores.

Technical Insights

The crate employs nuanced techniques like reversing edges for optimal distance calculations and utilizing an internal queue to manage graph traversal states efficiently.

Compatibility

This crate uses Rust edition 2021. Note: current edge deletion does full re-computation, highlighting pending optimizations.

Usage Example

use icentral_partial_bbfs::{ICentralWorkspace, Component, NodeIdQueue, Edge, NodeId, BetweennessCentralityError};

let mut workspace = ICentralWorkspace::new(...);
let mut component = Component::new(...);
let source: NodeId = ...;
let inserted_edge: Edge = ...;
let deleted_edge: Edge = ...;

partial_bbfs_addition(&mut workspace, &mut component, source, inserted_edge).unwrap();

partial_bbfs_deletion(&mut workspace, &component, source, &deleted_edge).unwrap();

Disclaimer

This README.md 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.