Community detection algorithms for directed graphs in Rust.
Rust's graph ecosystem is missing a correct, production-grade directed community detection crate. Existing options either treat directed graphs as undirected (losing flow information), are half-implemented prototypes, or wrap GPL C++ code. This crate fills the gap.
🚧 Early development. Not on crates.io yet.
- Directed Louvain (Leicht-Newman modularity + Blondel et al. greedy optimization) — v0.1
- Directed Leiden (Traag et al. refinement phase added) — v0.2
- Infomap (Rosvall-Bergstrom map equation, clean-room from paper) — v0.3
Community detection on directed graphs is a distinct problem from undirected. Edge direction carries real information:
- Citation networks — who cites whom
- Web graphs — who links to whom
- Code dependency graphs — who imports/calls whom
- Biological pathways — flow of activation
- Social graphs — who follows whom
Ignoring direction (the common approximation) loses this. The standard directed modularity formula is:
Q = (1/m) Σ_{ij} [A_ij - (k_i^out × k_j^in) / m] × δ(c_i, c_j)
where k^out is out-degree, k^in is in-degree, m is total edge weight. This replaces the symmetric k_i × k_j / 2m null model from undirected modularity.
MIT OR Apache-2.0 (your choice).
See PLAN.md for the implementation roadmap.