sz_orm_graph/
community.rs

1//! 社区发现（Community Detection）
2//!
3//! 提供图社区发现算法，将图划分为紧密连接的子图。
4
5use std::collections::{HashMap, HashSet};
6
7use crate::algorithm::{DirectedGraph, NodeId};
8
9/// 社区
10#[derive(Debug, Clone, serde::Serialize)]
11pub struct Community {
12    pub id: usize,
13    pub nodes: Vec<NodeId>,
14}
15
16impl Community {
17    pub fn new(id: usize, nodes: Vec<NodeId>) -> Self {
18        Self { id, nodes }
19    }
20
21    pub fn size(&self) -> usize {
22        self.nodes.len()
23    }
24
25    pub fn contains(&self, node: NodeId) -> bool {
26        self.nodes.contains(&node)
27    }
28}
29
30/// 社区发现结果
31#[derive(Debug, Clone, serde::Serialize)]
32pub struct CommunityDetectionResult {
33    pub communities: Vec<Community>,
34    pub modularity: f64,
35}
36
37impl CommunityDetectionResult {
38    pub fn community_count(&self) -> usize {
39        self.communities.len()
40    }
41
42    pub fn largest_community_size(&self) -> usize {
43        self.communities.iter().map(|c| c.size()).max().unwrap_or(0)
44    }
45
46    pub fn node_community_map(&self) -> HashMap<NodeId, usize> {
47        let mut map = HashMap::new();
48        for community in &self.communities {
49            for &node in &community.nodes {
50                map.insert(node, community.id);
51            }
52        }
53        map
54    }
55}
56
57/// 基于标签传播的社区发现
58pub struct LabelPropagation;
59
60impl LabelPropagation {
61    /// 执行标签传播算法
62    ///
63    /// 每个节点初始化为唯一标签，迭代传播直到收敛。
64    pub fn detect(graph: &DirectedGraph, max_iterations: usize) -> CommunityDetectionResult {
65        let nodes: Vec<NodeId> = graph.nodes().collect();
66        if nodes.is_empty() {
67            return CommunityDetectionResult {
68                communities: Vec::new(),
69                modularity: 0.0,
70            };
71        }
72        let mut labels: HashMap<NodeId, usize> = HashMap::new();
73        for (i, &node) in nodes.iter().enumerate() {
74            labels.insert(node, i);
75        }
76        for _ in 0..max_iterations {
77            let mut changed = false;
78            for &node in &nodes {
79                let neighbor_labels = Self::collect_neighbor_labels(graph, node, &labels);
80                if let Some(new_label) = Self::majority_label(&neighbor_labels) {
81                    if labels[&node] != new_label {
82                        labels.insert(node, new_label);
83                        changed = true;
84                    }
85                }
86            }
87            if !changed {
88                break;
89            }
90        }
91        let mut communities_map: HashMap<usize, Vec<NodeId>> = HashMap::new();
92        for &node in &nodes {
93            let label = labels[&node];
94            communities_map.entry(label).or_default().push(node);
95        }
96        let communities: Vec<Community> = communities_map
97            .into_iter()
98            .enumerate()
99            .map(|(i, (_, nodes))| Community::new(i, nodes))
100            .collect();
101        let modularity = Self::compute_modularity(graph, &communities);
102        CommunityDetectionResult {
103            communities,
104            modularity,
105        }
106    }
107
108    fn collect_neighbor_labels(
109        graph: &DirectedGraph,
110        node: NodeId,
111        labels: &HashMap<NodeId, usize>,
112    ) -> Vec<usize> {
113        let mut result = Vec::new();
114        if let Some(neighbors) = graph.neighbors(node) {
115            for &(neighbor, _) in neighbors {
116                if let Some(&label) = labels.get(&neighbor) {
117                    result.push(label);
118                }
119            }
120        }
121        result
122    }
123
124    fn majority_label(labels: &[usize]) -> Option<usize> {
125        if labels.is_empty() {
126            return None;
127        }
128        let mut counts: HashMap<usize, usize> = HashMap::new();
129        for &label in labels {
130            *counts.entry(label).or_insert(0) += 1;
131        }
132        counts
133            .into_iter()
134            .max_by_key(|(_, count)| *count)
135            .map(|(label, _)| label)
136    }
137
138    fn compute_modularity(graph: &DirectedGraph, communities: &[Community]) -> f64 {
139        let total_edges = graph.edge_count() as f64;
140        if total_edges == 0.0 {
141            return 0.0;
142        }
143        let _node_community: HashMap<NodeId, usize> = {
144            let mut map = HashMap::new();
145            for community in communities {
146                for &node in &community.nodes {
147                    map.insert(node, community.id);
148                }
149            }
150            map
151        };
152        let mut q = 0.0;
153        for community in communities {
154            let community_nodes: HashSet<NodeId> = community.nodes.iter().copied().collect();
155            let mut internal_edges = 0;
156            let mut degree_sum = 0;
157            for &node in &community.nodes {
158                if let Some(neighbors) = graph.neighbors(node) {
159                    for &(neighbor, _) in neighbors {
160                        if community_nodes.contains(&neighbor) {
161                            internal_edges += 1;
162                        }
163                        degree_sum += 1;
164                    }
165                }
166            }
167            q += internal_edges as f64 / total_edges
168                - (degree_sum as f64 / (2.0 * total_edges)).powi(2);
169        }
170        q
171    }
172}
173
174/// 基于连通分量的社区发现（简单方法）
175pub struct ConnectedComponentDetector;
176
177impl ConnectedComponentDetector {
178    /// 将每个连通分量作为一个社区
179    pub fn detect(graph: &DirectedGraph) -> CommunityDetectionResult {
180        let components = graph.connected_components();
181        let communities: Vec<Community> = components
182            .into_iter()
183            .enumerate()
184            .map(|(i, nodes)| Community::new(i, nodes))
185            .collect();
186        let modularity = LabelPropagation::compute_modularity(graph, &communities);
187        CommunityDetectionResult {
188            communities,
189            modularity,
190        }
191    }
192}
193
194#[cfg(test)]
195mod tests {
196    use super::*;
197
198    #[test]
199    fn test_community_new() {
200        let c = Community::new(0, vec![1, 2, 3]);
201        assert_eq!(c.size(), 3);
202        assert!(c.contains(2));
203        assert!(!c.contains(4));
204    }
205
206    #[test]
207    fn test_label_propagation_empty() {
208        let g = DirectedGraph::new();
209        let result = LabelPropagation::detect(&g, 10);
210        assert_eq!(result.community_count(), 0);
211    }
212
213    #[test]
214    fn test_label_propagation_single_node() {
215        let mut g = DirectedGraph::new();
216        g.add_node(1);
217        let result = LabelPropagation::detect(&g, 10);
218        assert_eq!(result.community_count(), 1);
219    }
220
221    #[test]
222    fn test_label_propagation_two_components() {
223        let mut g = DirectedGraph::new();
224        g.add_edge_unweighted(1, 2);
225        g.add_edge_unweighted(2, 1);
226        g.add_edge_unweighted(3, 4);
227        g.add_edge_unweighted(4, 3);
228        let result = LabelPropagation::detect(&g, 100);
229        assert!(result.community_count() >= 1);
230    }
231
232    #[test]
233    fn test_label_propagation_connected() {
234        let mut g = DirectedGraph::new();
235        g.add_edge_unweighted(1, 2);
236        g.add_edge_unweighted(2, 3);
237        g.add_edge_unweighted(3, 1);
238        let result = LabelPropagation::detect(&g, 100);
239        assert!(result.community_count() >= 1);
240    }
241
242    #[test]
243    fn test_connected_component_detector() {
244        let mut g = DirectedGraph::new();
245        g.add_edge_unweighted(1, 2);
246        g.add_edge_unweighted(3, 4);
247        let result = ConnectedComponentDetector::detect(&g);
248        assert_eq!(result.community_count(), 2);
249    }
250
251    #[test]
252    fn test_connected_component_detector_single() {
253        let mut g = DirectedGraph::new();
254        g.add_edge_unweighted(1, 2);
255        g.add_edge_unweighted(2, 3);
256        let result = ConnectedComponentDetector::detect(&g);
257        assert_eq!(result.community_count(), 1);
258    }
259
260    #[test]
261    fn test_result_node_community_map() {
262        let communities = vec![Community::new(0, vec![1, 2]), Community::new(1, vec![3, 4])];
263        let result = CommunityDetectionResult {
264            communities,
265            modularity: 0.5,
266        };
267        let map = result.node_community_map();
268        assert_eq!(map[&1], 0);
269        assert_eq!(map[&3], 1);
270    }
271
272    #[test]
273    fn test_result_largest_community() {
274        let communities = vec![
275            Community::new(0, vec![1, 2]),
276            Community::new(1, vec![3, 4, 5]),
277        ];
278        let result = CommunityDetectionResult {
279            communities,
280            modularity: 0.0,
281        };
282        assert_eq!(result.largest_community_size(), 3);
283    }
284
285    #[test]
286    fn test_label_propagation_modularity() {
287        let mut g = DirectedGraph::new();
288        g.add_edge_unweighted(1, 2);
289        g.add_edge_unweighted(2, 1);
290        let result = LabelPropagation::detect(&g, 10);
291        assert!(result.modularity >= 0.0);
292    }
293}
sz_orm_graph/community.rs

sz_orm_graph/
community.rs
