1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
//! Community detection algorithms for graphs.
//!
//! Given a graph, find natural groupings where nodes within groups are
//! densely connected, and connections between groups are sparse.
//!
//! ## The Modularity Objective
//!
//! Most algorithms optimize **modularity** Q, which compares the actual
//! number of edges within communities to the expected number in a random
//! graph with the same degree sequence:
//!
//! ```text
//! Q = (1/2m) × Σ[A_ij - γ(k_i × k_j)/(2m)] × δ(c_i, c_j)
//! ```
//!
//! Where:
//! - m = total edge weight (sum of all edges)
//! - A_ij = edge weight between i and j
//! - k_i = degree of node i
//! - γ = resolution parameter
//! - δ(c_i, c_j) = 1 if i and j are in same community
//!
//! **Intuition**: For each pair in the same community, we add (actual edges) -
//! (expected edges). A good partition has Q > 0, meaning more internal edges
//! than expected by chance.
//!
//! ## The Resolution Parameter γ
//!
//! The resolution parameter controls granularity:
//!
//! - **γ = 1**: Standard modularity (default)
//! - **γ > 1**: Smaller communities (higher penalty for merging)
//! - **γ < 1**: Larger communities (lower penalty for merging)
//!
//! This is crucial because modularity has a **resolution limit**—it can't
//! detect communities smaller than √(2m). Increasing γ helps find fine-grained
//! structure.
//!
//! ## Algorithms
//!
//! ### Leiden (Recommended)
//!
//! The Leiden algorithm ([Traag et al. 2019](https://arxiv.org/abs/1810.08473))
//! improves on Louvain with a critical guarantee: **communities are always
//! well-connected**.
//!
//! **Three phases**:
//! 1. **Local moving**: Greedily move nodes to improve modularity
//! 2. **Refinement**: Split communities that aren't internally connected
//! 3. **Aggregation**: Contract graph, repeat
//!
//! The refinement phase is the key innovation. Louvain skips this, which can
//! produce pathological results—nodes labeled as "same community" with no
//! path between them.
//!
//! ### Louvain
//!
//! The original fast modularity algorithm ([Blondel et al. 2008](https://arxiv.org/abs/0803.0476)).
//! Still useful as a baseline, but **can produce disconnected communities**.
//!
//! In experiments, Louvain produced disconnected communities in up to 16% of
//! cases when run iteratively. Use Leiden instead for production.
//!
//! ### Label Propagation
//!
//! O(E) algorithm that spreads labels through the network. Each node adopts
//! the most common label among its neighbors. Fast but approximate.
//!
//! ## Usage
//!
//! ```rust
//! use petgraph::graph::UnGraph;
//! use sheaf::community::{Leiden, CommunityDetection};
//!
//! // Build a graph
//! let mut graph = UnGraph::<(), ()>::new_undirected();
//! let a = graph.add_node(());
//! let b = graph.add_node(());
//! let c = graph.add_node(());
//! graph.add_edge(a, b, ());
//! graph.add_edge(b, c, ());
//!
//! // Detect communities
//! let leiden = Leiden::new();
//! let communities = leiden.detect(&graph).unwrap();
//! // communities[i] = community ID for node i
//! ```
//!
//! ## References
//!
//! - Traag, Waltman, van Eck (2019). "From Louvain to Leiden: guaranteeing
//! well-connected communities." Scientific Reports 9, 5233.
//! - Blondel et al. (2008). "Fast unfolding of communities in large networks."
//! - Newman & Girvan (2004). "Finding and evaluating community structure in networks."
pub use LabelPropagation;
pub use Leiden;
pub use Louvain;
pub use CommunityDetection;
pub use ;