Module algorithms 

Graph Algorithms for RedDB

High-performance graph algorithms optimized for attack path analysis:

• PageRank: Identify critical nodes
• Connected Components: Find isolated network segments
• Betweenness Centrality: Find chokepoints
• Community Detection: Cluster related assets
• Cycle Detection: Find lateral movement loops

Algorithm Complexity

Algorithm	Time Complexity	Space Complexity	Notes
PageRank	O(V + E) per iter	O(V)	Converges in ~20-50 iterations
Connected Components	O(V + E)	O(V)	Union-Find with path compress
Betweenness Centrality	O(V × E)	O(V + E)	Brandes’ algorithm
Community Detection	O(V + E) per iter	O(V)	Label propagation, ~5-10 iters
Cycle Detection	O(V + E)	O(V + cycles)	DFS with rotation dedup
BFS Path Finding	O(V + E)	O(V)	Single-source shortest path
Dijkstra (weighted)	O((V+E) log V)	O(V)	Priority queue based
K-Shortest Paths	O(K × V × E)	O(K × V)	Yen’s algorithm

Where V = vertices (nodes), E = edges.

Performance Benchmarks

On a graph with 1M edges (typical enterprise network):

• Graph creation: ~2 seconds
• PageRank: ~500ms (50 iterations)
• Connected Components: ~100ms
• Communities: ~300ms (10 iterations)

On a graph with 100K edges:

• Betweenness Centrality: ~5 seconds (O(V×E))

On a graph with 10K edges:

• Cycle Detection: ~50ms

Example

use reddb::storage::engine::algorithms::{PageRank, ConnectedComponents};

let pr = PageRank::new(&graph).run();
let components = ConnectedComponents::new(&graph).find();

Structs

BetweennessCentrality

Betweenness centrality computation using Brandes’ algorithm

BetweennessResult

Result of betweenness centrality computation

ClosenessCentrality

Closeness centrality measures how close a node is to all other nodes

ClosenessResult

Result of closeness centrality computation

ClusteringCoefficient

Local and global clustering coefficient

ClusteringResult

Result of clustering coefficient computation

CommunitiesResult

Result of community detection

Community

A community of nodes

Component

A connected component in the graph

ComponentsResult

Result of connected components computation

ConnectedComponents

Connected components finder

Cycle

A cycle in the graph

CycleDetector

DFS-based cycle detection

CyclesResult

Result of cycle detection

DegreeCentrality

Degree centrality measures node importance by connection count

DegreeCentralityResult

Result of degree centrality computation

EigenvectorCentrality

Eigenvector centrality: importance based on neighbor importance

EigenvectorResult

Result of eigenvector centrality computation

HITS

HITS algorithm: Identifies hubs and authorities

HITSResult

Result of HITS computation

LabelPropagation

Label Propagation Algorithm for community detection

Louvain

Louvain algorithm for community detection

LouvainResult

Result of Louvain community detection

PageRank

PageRank algorithm for identifying critical nodes

PageRankResult

Result of PageRank computation

PersonalizedPageRank

Personalized PageRank - teleport only to specified seed nodes

SCCResult

Result of SCC computation

StronglyConnectedComponents

Strongly connected components using Tarjan’s algorithm

TriangleCounting

Count triangles in the graph

TriangleResult

Result of triangle counting

WCCResult

Result of weakly connected components

WeaklyConnectedComponents

Weakly connected components - treats directed graph as undirected