facett_graphview/analysis/
community.rs

1//! **Community detection** — the analysis-toolbox front door. **Louvain** modularity
2//! optimisation is re-exported from [`crate::community`] (the existing, well-tested
3//! implementation that drives the semantic-zoom meta-graph); **label propagation** is
4//! added here as a fast near-linear alternative.
5
6use super::Adjacency;
7
8// Re-export the existing Louvain so the analysis toolbox is one import surface.
9pub use crate::community::{louvain, modularity, Communities};
10
11/// **Label propagation** (Raghavan et al.) — a fast, near-linear community detector:
12/// every node starts in its own community, then repeatedly adopts the community held
13/// by the plurality of its undirected neighbours (ties broken by lowest community id,
14/// so it's deterministic) until a full pass makes no change or `max_iters` is hit.
15///
16/// Returns a [`Communities`] with the partition's modularity as quality DATA (same
17/// shape as [`louvain`], so the two are drop-in interchangeable).
18#[must_use]
19pub fn label_propagation(g: &Adjacency, max_iters: usize) -> Communities {
20    let n = g.n;
21    let mut label: Vec<usize> = (0..n).collect();
22    for _ in 0..max_iters.max(1) {
23        let mut changed = false;
24        // Deterministic synchronous-ish sweep in index order (updates visible at once).
25        for i in 0..n {
26            if g.und[i].is_empty() {
27                continue;
28            }
29            // Tally weighted neighbour labels; pick the max, lowest-id tie-break.
30            let mut tally: std::collections::BTreeMap<usize, f32> = std::collections::BTreeMap::new();
31            for &(j, w) in &g.und[i] {
32                *tally.entry(label[j]).or_insert(0.0) += w;
33            }
34            let mut best = label[i];
35            let mut best_w = tally.get(&label[i]).copied().unwrap_or(0.0);
36            for (&lab, &w) in &tally {
37                if w > best_w + 1e-9 {
38                    best_w = w;
39                    best = lab;
40                }
41            }
42            if best != label[i] {
43                label[i] = best;
44                changed = true;
45            }
46        }
47        if !changed {
48            break;
49        }
50    }
51    finalize(n, label, g)
52}
53
54/// Compact arbitrary labels into `0..count` and compute the partition modularity.
55fn finalize(n: usize, label: Vec<usize>, g: &Adjacency) -> Communities {
56    let mut map = std::collections::HashMap::new();
57    let mut of = Vec::with_capacity(n);
58    let mut count = 0;
59    for &l in &label {
60        let id = *map.entry(l).or_insert_with(|| {
61            let id = count;
62            count += 1;
63            id
64        });
65        of.push(id);
66    }
67    // Undirected edge list (each undirected edge once) for the modularity score.
68    let mut edges = Vec::new();
69    for i in 0..n {
70        for &(j, _) in &g.und[i] {
71            if i < j {
72                edges.push((i, j));
73            }
74        }
75    }
76    let q = modularity(n, &edges, &of);
77    Communities { of, count, modularity: q }
78}
79
80#[cfg(test)]
81mod tests {
82    use super::*;
83
84    /// Two triangles {0,1,2} and {3,4,5}. Kept separate (no bridge): a single weak
85    /// bridge is a known collapse mode for deterministic label propagation — Louvain
86    /// (tested below) is the one to trust for the bridged case.
87    fn two_triangles() -> Adjacency {
88        Adjacency::from_edges(6, &[(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3)])
89    }
90
91    #[test]
92    fn label_propagation_splits_the_two_triangles() {
93        let g = two_triangles();
94        let c = label_propagation(&g, 100);
95        // 0,1,2 share a community; 3,4,5 share another.
96        assert_eq!(c.of[0], c.of[1]);
97        assert_eq!(c.of[1], c.of[2]);
98        assert_eq!(c.of[3], c.of[4]);
99        assert_eq!(c.of[4], c.of[5]);
100        assert_ne!(c.of[0], c.of[3], "the two triangles are distinct communities");
101        assert!(c.modularity > 0.3, "a clear split has positive modularity ({})", c.modularity);
102    }
103
104    #[test]
105    fn louvain_reexport_agrees_on_the_split() {
106        // The re-exported Louvain finds the same clear two-community structure.
107        let edges = vec![(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3), (2, 3)];
108        let c = louvain(6, &edges);
109        assert_eq!(c.of[0], c.of[1]);
110        assert_ne!(c.of[0], c.of[3]);
111        assert!(c.modularity > 0.3);
112    }
113
114    #[test]
115    fn edgeless_graph_is_all_singletons() {
116        let g = Adjacency::from_edges(4, &[]);
117        let c = label_propagation(&g, 10);
118        assert_eq!(c.count, 4);
119    }
120}
facett_graphview/analysis/community.rs

facett_graphview/analysis/
community.rs
