graphmind_graph_algorithms/
cdlp.rs

1//! Community Detection via Label Propagation (CDLP)
2//!
3//! Synchronous label propagation algorithm for community detection.
4//! Each node starts with its own ID as label, then iteratively sets its
5//! label to the most frequent label among its neighbors.
6
7use super::common::{GraphView, NodeId};
8use std::collections::HashMap;
9
10/// Result of CDLP algorithm
11#[derive(Debug, Clone)]
12pub struct CdlpResult {
13    /// Mapping from NodeId to community label
14    pub labels: HashMap<NodeId, NodeId>,
15    /// Number of iterations until convergence
16    pub iterations: usize,
17}
18
19/// Configuration for CDLP
20pub struct CdlpConfig {
21    /// Maximum number of iterations
22    pub max_iterations: usize,
23}
24
25impl Default for CdlpConfig {
26    fn default() -> Self {
27        Self {
28            max_iterations: 100,
29        }
30    }
31}
32
33/// Run synchronous CDLP on the given graph view
34///
35/// Returns community labels for each node. Uses undirected edges
36/// (both successors and predecessors).
37pub fn cdlp(view: &GraphView, config: &CdlpConfig) -> CdlpResult {
38    let n = view.node_count;
39    if n == 0 {
40        return CdlpResult {
41            labels: HashMap::new(),
42            iterations: 0,
43        };
44    }
45
46    // Initialize: each node gets its own NodeId as label
47    let mut labels: Vec<NodeId> = (0..n).map(|i| view.index_to_node[i]).collect();
48    let mut new_labels = labels.clone();
49    let mut converged;
50    let mut iterations = 0;
51
52    for _iter in 0..config.max_iterations {
53        converged = true;
54        iterations += 1;
55
56        for idx in 0..n {
57            // Collect neighbor labels (undirected)
58            let mut label_counts: HashMap<NodeId, usize> = HashMap::new();
59            for &neighbor in view.successors(idx) {
60                *label_counts.entry(labels[neighbor]).or_insert(0) += 1;
61            }
62            for &neighbor in view.predecessors(idx) {
63                *label_counts.entry(labels[neighbor]).or_insert(0) += 1;
64            }
65
66            if label_counts.is_empty() {
67                new_labels[idx] = labels[idx];
68                continue;
69            }
70
71            // Pick the most frequent label; break ties by choosing smallest label
72            let max_count = *label_counts.values().max().unwrap();
73            let best_label = label_counts
74                .into_iter()
75                .filter(|(_, count)| *count == max_count)
76                .map(|(label, _)| label)
77                .min()
78                .unwrap();
79
80            if best_label != labels[idx] {
81                converged = false;
82            }
83            new_labels[idx] = best_label;
84        }
85
86        std::mem::swap(&mut labels, &mut new_labels);
87
88        if converged {
89            break;
90        }
91    }
92
93    let result_labels: HashMap<NodeId, NodeId> = (0..n)
94        .map(|idx| (view.index_to_node[idx], labels[idx]))
95        .collect();
96
97    CdlpResult {
98        labels: result_labels,
99        iterations,
100    }
101}
102
103#[cfg(test)]
104mod tests {
105    use super::*;
106    use crate::common::GraphView;
107    use std::collections::HashMap;
108
109    fn make_triangle_graph() -> GraphView {
110        // Triangle: 1-2, 2-3, 1-3
111        let index_to_node = vec![1, 2, 3];
112        let mut node_to_index = HashMap::new();
113        node_to_index.insert(1, 0);
114        node_to_index.insert(2, 1);
115        node_to_index.insert(3, 2);
116
117        let outgoing = vec![vec![1, 2], vec![0, 2], vec![0, 1]];
118        let incoming = vec![vec![1, 2], vec![0, 2], vec![0, 1]];
119
120        GraphView::from_adjacency_list(3, index_to_node, node_to_index, outgoing, incoming, None)
121    }
122
123    #[test]
124    fn test_cdlp_triangle() {
125        let view = make_triangle_graph();
126        let result = cdlp(&view, &CdlpConfig::default());
127        // In a triangle, all nodes should converge to the same label
128        let labels: Vec<NodeId> = result.labels.values().cloned().collect();
129        assert!(
130            labels.iter().all(|l| *l == labels[0]),
131            "All nodes in a triangle should have the same community label"
132        );
133    }
134
135    #[test]
136    fn test_cdlp_disconnected() {
137        // Two disconnected nodes: 1 and 2
138        let index_to_node = vec![1, 2];
139        let mut node_to_index = HashMap::new();
140        node_to_index.insert(1, 0);
141        node_to_index.insert(2, 1);
142
143        let view = GraphView::from_adjacency_list(
144            2,
145            index_to_node,
146            node_to_index,
147            vec![vec![], vec![]],
148            vec![vec![], vec![]],
149            None,
150        );
151        let result = cdlp(&view, &CdlpConfig::default());
152        assert_ne!(result.labels[&1], result.labels[&2]);
153    }
154
155    #[test]
156    fn test_cdlp_empty() {
157        let view = GraphView::from_adjacency_list(0, vec![], HashMap::new(), vec![], vec![], None);
158        let result = cdlp(&view, &CdlpConfig::default());
159        assert!(result.labels.is_empty());
160    }
161}
graphmind_graph_algorithms/cdlp.rs

graphmind_graph_algorithms/
cdlp.rs
