#graph #betweenness #centrality #biconnected #rbfs

icentral-rbfs

A Rust crate for calculating and updating betweenness centrality scores in graphs using Recursive Breit-First Search strategies, optimized for dynamic and static networks

1 unstable release

new 0.1.0 Apr 4, 2025

#1 in #centrality


Used in 25 crates (4 directly)

MIT/Apache

20KB
465 lines

iCentral RBFS

icentral-rbfs is a Rust crate designed for high-performance computation of betweenness centrality using Recursive Breit-First Search (RBFS) strategies. This crate provides efficient mechanisms for updating and recalculating betweenness centrality scores in dynamic or static graphs, utilizing biconnected components and graph types for optimized computation paths.

Overview

Betweenness centrality is a fundamental metric in network analysis used to quantify the influence of a vertex within a graph. This crate focuses on providing tools to adjust and recompute this metric in the face of graph structure modifications such as vertex additions or removals.

Key Features

  • RBFS Strategy: Offers recursive breadth-first search algorithms tailored for dynamic graph updates.
  • Biconnected Components Handling: Efficient processing of graph components that are maximally biconnected, enhancing computation efficiency.
  • Operation Modes: Supports multiple operation modes through RbfsOperation enum, allowing addition and subtraction of vertex influences.

Usage

To leverage icentral-rbfs in your project, include it in your Cargo.toml file:

[dependencies]
icentral-rbfs = "0.1.0"

Functions

  • rbfs: Executes a recursive breadth-first search, updating betweenness centrality scores.
  • rbfs_bcc: Specifically targets biconnected components to optimize recalculations of centrality.
  • rbfs_graph: Processes graph elements to adjust centrality scores based on graph structure changes.

These functions apply the RBFS principles to either a complete graph or segmented biconnected components, offering depth and precision in update scenarios.

Installation

Ensure you are using Rust 2021 edition for compatibility. Further dependencies, if required, should align with this edition's features and libraries.

Contribution

Contributions are welcome. Please submit issues or pull requests to our repository if enhancements or bug fixes are needed.


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.

Dependencies

~16–26MB
~392K SLoC