scirs2_cluster/community/
mod.rs

1//! Community detection algorithms for graph/network data.
2//!
3//! This module provides advanced community detection methods beyond the basic
4//! implementations in the `graph` module. It includes:
5//!
6//! - **Leiden Algorithm**: Refinement of Louvain guaranteeing well-connected communities
7//! - **Label Propagation**: Near-linear time community detection with seed label support
8//! - **Stochastic Block Model (SBM)**: Generative model-based community inference
9
10pub mod label_propagation;
11pub mod leiden;
12pub mod sbm;
13
14use serde::{Deserialize, Serialize};
15
16/// Common result type for community detection algorithms.
17#[derive(Debug, Clone, Serialize, Deserialize)]
18pub struct CommunityResult {
19    /// Community label assignment for each node (0-indexed, consecutive).
20    pub labels: Vec<usize>,
21    /// Number of distinct communities found.
22    pub num_communities: usize,
23    /// Quality score of the partition (e.g. modularity). May be `None` for
24    /// algorithms that do not compute a quality function.
25    pub quality_score: Option<f64>,
26}
27
28/// Adjacency representation used by the community module.
29///
30/// Uses `f64` edge weights directly, avoiding the `Eq + Hash` constraint
31/// problem present in the generic `Graph<F>` type.
32#[derive(Debug, Clone, Serialize, Deserialize)]
33pub struct AdjacencyGraph {
34    /// Number of nodes.
35    pub n_nodes: usize,
36    /// Adjacency list: `adjacency[u]` contains `(v, weight)` pairs.
37    /// The graph is assumed undirected; every edge appears in both directions.
38    pub adjacency: Vec<Vec<(usize, f64)>>,
39}
40
41impl AdjacencyGraph {
42    /// Create an empty graph with `n` nodes.
43    pub fn new(n: usize) -> Self {
44        Self {
45            n_nodes: n,
46            adjacency: vec![Vec::new(); n],
47        }
48    }
49
50    /// Build from a dense adjacency matrix (row-major, n x n).
51    /// Only positive off-diagonal entries are treated as edges.
52    pub fn from_dense(matrix: &[f64], n: usize) -> crate::error::Result<Self> {
53        if matrix.len() != n * n {
54            return Err(crate::error::ClusteringError::InvalidInput(
55                "Matrix length must equal n*n".to_string(),
56            ));
57        }
58        let mut g = Self::new(n);
59        for i in 0..n {
60            for j in (i + 1)..n {
61                let w = matrix[i * n + j];
62                if w > 0.0 {
63                    g.adjacency[i].push((j, w));
64                    g.adjacency[j].push((i, w));
65                }
66            }
67        }
68        Ok(g)
69    }
70
71    /// Build from a symmetric adjacency matrix stored as nested `Vec`.
72    pub fn from_nested(adj: &[Vec<f64>]) -> crate::error::Result<Self> {
73        let n = adj.len();
74        for row in adj {
75            if row.len() != n {
76                return Err(crate::error::ClusteringError::InvalidInput(
77                    "Adjacency matrix must be square".to_string(),
78                ));
79            }
80        }
81        let mut g = Self::new(n);
82        for i in 0..n {
83            for j in (i + 1)..n {
84                let w = adj[i][j];
85                if w > 0.0 {
86                    g.adjacency[i].push((j, w));
87                    g.adjacency[j].push((i, w));
88                }
89            }
90        }
91        Ok(g)
92    }
93
94    /// Add an undirected edge. Does NOT check for duplicates.
95    pub fn add_edge(&mut self, u: usize, v: usize, weight: f64) -> crate::error::Result<()> {
96        if u >= self.n_nodes || v >= self.n_nodes {
97            return Err(crate::error::ClusteringError::InvalidInput(
98                "Node index out of bounds".to_string(),
99            ));
100        }
101        if u != v {
102            self.adjacency[u].push((v, weight));
103            self.adjacency[v].push((u, weight));
104        }
105        Ok(())
106    }
107
108    /// Weighted degree of a node.
109    pub fn weighted_degree(&self, node: usize) -> f64 {
110        self.adjacency
111            .get(node)
112            .map(|nbrs| nbrs.iter().map(|(_, w)| *w).sum())
113            .unwrap_or(0.0)
114    }
115
116    /// Total edge weight (each undirected edge counted once).
117    pub fn total_edge_weight(&self) -> f64 {
118        let sum: f64 = self
119            .adjacency
120            .iter()
121            .flat_map(|nbrs| nbrs.iter().map(|(_, w)| *w))
122            .sum();
123        sum / 2.0
124    }
125
126    /// Get edge weight between two nodes (0 if no edge).
127    pub fn edge_weight(&self, u: usize, v: usize) -> f64 {
128        if let Some(nbrs) = self.adjacency.get(u) {
129            for &(nb, w) in nbrs {
130                if nb == v {
131                    return w;
132                }
133            }
134        }
135        0.0
136    }
137
138    /// Compute modularity for a given partition.
139    ///
140    /// Q = (1/2m) sum_{ij} [ A_{ij} - k_i k_j / (2m) ] delta(c_i, c_j)
141    pub fn modularity(&self, labels: &[usize]) -> f64 {
142        let m2 = self.total_edge_weight() * 2.0; // 2m
143        if m2 == 0.0 {
144            return 0.0;
145        }
146        let mut q = 0.0;
147        for i in 0..self.n_nodes {
148            let ki = self.weighted_degree(i);
149            for &(j, w) in &self.adjacency[i] {
150                if labels[i] == labels[j] {
151                    q += w - ki * self.weighted_degree(j) / m2;
152                }
153            }
154        }
155        q / m2
156    }
157}
158
159// Re-exports
160pub use label_propagation::{
161    label_propagation_community, LabelPropagationConfig, LabelPropagationResult,
162};
163pub use leiden::{leiden, LeidenConfig, QualityFunction};
164pub use sbm::{StochasticBlockModel, StochasticBlockModelConfig};
scirs2_cluster/community/mod.rs

scirs2_cluster/community/
mod.rs
