nordisk/facett

facett-graphview/src/analysis/community.rs

//! **Community detection** — the analysis-toolbox front door. **Louvain** modularity
//! optimisation is re-exported from [`crate::community`] (the existing, well-tested
//! implementation that drives the semantic-zoom meta-graph); **label propagation** is
//! added here as a fast near-linear alternative.

use super::Adjacency;

// Re-export the existing Louvain so the analysis toolbox is one import surface.
pub use crate::community::{louvain, modularity, Communities};

/// **Label propagation** (Raghavan et al.) — a fast, near-linear community detector:
/// every node starts in its own community, then repeatedly adopts the community held
/// by the plurality of its undirected neighbours (ties broken by lowest community id,
/// so it's deterministic) until a full pass makes no change or `max_iters` is hit.
///
/// Returns a [`Communities`] with the partition's modularity as quality DATA (same
/// shape as [`louvain`], so the two are drop-in interchangeable).
#[must_use]
pub fn label_propagation(g: &Adjacency, max_iters: usize) -> Communities {
    let n = g.n;
    let mut label: Vec<usize> = (0..n).collect();
    for _ in 0..max_iters.max(1) {
        let mut changed = false;
        // Deterministic synchronous-ish sweep in index order (updates visible at once).
        for i in 0..n {
            if g.und[i].is_empty() {
                continue;
            }
            // Tally weighted neighbour labels; pick the max, lowest-id tie-break.
            let mut tally: std::collections::BTreeMap<usize, f32> = std::collections::BTreeMap::new();
            for &(j, w) in &g.und[i] {
                *tally.entry(label[j]).or_insert(0.0) += w;
            }
            let mut best = label[i];
            let mut best_w = tally.get(&label[i]).copied().unwrap_or(0.0);
            for (&lab, &w) in &tally {
                if w > best_w + 1e-9 {
                    best_w = w;
                    best = lab;
                }
            }
            if best != label[i] {
                label[i] = best;
                changed = true;
            }
        }
        if !changed {
            break;
        }
    }
    finalize(n, label, g)
}

/// Compact arbitrary labels into `0..count` and compute the partition modularity.
fn finalize(n: usize, label: Vec<usize>, g: &Adjacency) -> Communities {
    let mut map = std::collections::HashMap::new();
    let mut of = Vec::with_capacity(n);
    let mut count = 0;
    for &l in &label {
        let id = *map.entry(l).or_insert_with(|| {
            let id = count;
            count += 1;
            id
        });
        of.push(id);
    }
    // Undirected edge list (each undirected edge once) for the modularity score.
    let mut edges = Vec::new();
    for i in 0..n {
        for &(j, _) in &g.und[i] {
            if i < j {
                edges.push((i, j));
            }
        }
    }
    let q = modularity(n, &edges, &of);
    Communities { of, count, modularity: q }
}

#[cfg(test)]
mod tests {
    use super::*;

    /// Two triangles {0,1,2} and {3,4,5}. Kept separate (no bridge): a single weak
    /// bridge is a known collapse mode for deterministic label propagation — Louvain
    /// (tested below) is the one to trust for the bridged case.
    fn two_triangles() -> Adjacency {
        Adjacency::from_edges(6, &[(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3)])
    }

    #[test]
    fn label_propagation_splits_the_two_triangles() {
        let g = two_triangles();
        let c = label_propagation(&g, 100);
        // 0,1,2 share a community; 3,4,5 share another.
        assert_eq!(c.of[0], c.of[1]);
        assert_eq!(c.of[1], c.of[2]);
        assert_eq!(c.of[3], c.of[4]);
        assert_eq!(c.of[4], c.of[5]);
        assert_ne!(c.of[0], c.of[3], "the two triangles are distinct communities");
        assert!(c.modularity > 0.3, "a clear split has positive modularity ({})", c.modularity);
    }

    #[test]
    fn louvain_reexport_agrees_on_the_split() {
        // The re-exported Louvain finds the same clear two-community structure.
        let edges = vec![(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3), (2, 3)];
        let c = louvain(6, &edges);
        assert_eq!(c.of[0], c.of[1]);
        assert_ne!(c.of[0], c.of[3]);
        assert!(c.modularity > 0.3);
    }

    #[test]
    fn edgeless_graph_is_all_singletons() {
        let g = Adjacency::from_edges(4, &[]);
        let c = label_propagation(&g, 10);
        assert_eq!(c.count, 4);
    }
}