weavatrix_graph/algo/network/
community.rs

1use super::adjacency::adjacency;
2use crate::algo::traversal::Direction;
3use crate::{IndexGraphView, Vec};
4
5#[derive(Debug, Clone, PartialEq, Eq)]
6pub struct Communities<Node> {
7    groups: Vec<Vec<Node>>,
8    memberships: Vec<(Node, usize)>,
9    iterations: usize,
10    converged: bool,
11}
12
13impl<Node> Communities<Node> {
14    #[must_use]
15    pub fn groups(&self) -> &[Vec<Node>] {
16        &self.groups
17    }
18
19    #[must_use]
20    pub fn memberships(&self) -> &[(Node, usize)] {
21        &self.memberships
22    }
23
24    #[must_use]
25    pub const fn iterations(&self) -> usize {
26        self.iterations
27    }
28
29    #[must_use]
30    pub const fn converged(&self) -> bool {
31        self.converged
32    }
33}
34
35/// Deterministic asynchronous label propagation over the undirected projection.
36#[must_use]
37pub fn label_propagation_communities<G>(graph: &G, max_iterations: usize) -> Communities<G::Node>
38where
39    G: IndexGraphView,
40{
41    let adjacent = adjacency(graph, Direction::Both);
42    let mut labels = (0..graph.node_bound()).collect::<Vec<_>>();
43    let mut converged = adjacent.nodes.is_empty();
44    let mut iterations = 0;
45    for iteration in 1..=max_iterations {
46        iterations = iteration;
47        let mut changed = false;
48        for &node in &adjacent.nodes {
49            let slot = G::node_slot(node);
50            let mut counts = Vec::<(usize, usize)>::new();
51            for &neighbor in &adjacent.neighbors[slot] {
52                let label = labels[neighbor];
53                if let Some((_, count)) = counts.iter_mut().find(|entry| entry.0 == label) {
54                    *count += 1;
55                } else {
56                    counts.push((label, 1));
57                }
58            }
59            let selected = counts
60                .into_iter()
61                .max_by(|left, right| left.1.cmp(&right.1).then_with(|| right.0.cmp(&left.0)))
62                .map_or(labels[slot], |entry| entry.0);
63            if selected != labels[slot] {
64                labels[slot] = selected;
65                changed = true;
66            }
67        }
68        if !changed {
69            converged = true;
70            break;
71        }
72    }
73    canonicalize(
74        &adjacent.nodes,
75        &labels,
76        G::node_slot,
77        iterations,
78        converged,
79    )
80}
81
82fn canonicalize<Node>(
83    nodes: &[Node],
84    labels: &[usize],
85    node_slot: fn(Node) -> usize,
86    iterations: usize,
87    converged: bool,
88) -> Communities<Node>
89where
90    Node: Copy,
91{
92    let mut unique = nodes
93        .iter()
94        .map(|node| labels[node_slot(*node)])
95        .collect::<Vec<_>>();
96    unique.sort_unstable();
97    unique.dedup();
98    let memberships = nodes
99        .iter()
100        .copied()
101        .map(|node| {
102            let label = labels[node_slot(node)];
103            let community = unique.binary_search(&label).unwrap_or(0);
104            (node, community)
105        })
106        .collect::<Vec<_>>();
107    let mut groups = vec![Vec::new(); unique.len()];
108    for &(node, community) in &memberships {
109        groups[community].push(node);
110    }
111    Communities {
112        groups,
113        memberships,
114        iterations,
115        converged,
116    }
117}
weavatrix_graph/algo/network/community.rs

weavatrix_graph/algo/network/
community.rs
