oxibrain-index 0.4.0

Lexical and graph index primitives for oxibrain — n-gram, TF-IDF, adjacency, community
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

//! Deterministic label-propagation community detection (DESIGN §9.4).
//! Tie-break: lowest label value wins. Fixed iteration cap guarantees termination.
use crate::adjacency::AdjacencyGraph;
use std::collections::BTreeMap;
#[derive(Debug, Clone)]
pub struct CommunityMap {
    pub labels: BTreeMap<String, u64>,
}
pub fn label_propagation(graph: &AdjacencyGraph, max_iterations: usize) -> CommunityMap {
    let nodes: Vec<String> = graph.all_nodes();
    let mut labels: BTreeMap<String, u64> = nodes
        .iter()
        .enumerate()
        .map(|(i, n)| (n.clone(), i as u64))
        .collect();
    for _ in 0..max_iterations {
        let mut changed = false;
        for node in &nodes {
            let mut nl: Vec<u64> = Vec::new();
            for (n, _, _) in graph.neighbors_out(node) {
                if let Some(&l) = labels.get(n) {
                    nl.push(l);
                }
            }
            for (n, _, _) in graph.neighbors_in(node) {
                if let Some(&l) = labels.get(n) {
                    nl.push(l);
                }
            }
            if nl.is_empty() {
                continue;
            }
            nl.sort_unstable();
            let new_label = most_frequent(&nl);
            if labels.get(node) != Some(&new_label) {
                labels.insert(node.clone(), new_label);
                changed = true;
            }
        }
        if !changed {
            break;
        }
    }
    CommunityMap { labels }
}
fn most_frequent(sorted: &[u64]) -> u64 {
    let mut best = sorted[0];
    let mut best_c = 1;
    let mut cur = sorted[0];
    let mut cur_c = 1;
    for &l in &sorted[1..] {
        if l == cur {
            cur_c += 1;
        } else {
            if cur_c > best_c {
                best_c = cur_c;
                best = cur;
            }
            cur = l;
            cur_c = 1;
        }
    }
    if cur_c > best_c {
        best = cur;
    }
    best
}

/// Confidence-weighted label propagation (§9.4, 10.6). Same algorithm as
/// `label_propagation` but neighbor votes are weighted by edge weight (mean
/// belief confidence). An edge with weight 0.9 has 3× the vote of weight 0.3.
pub fn label_propagation_weighted(
    graph: &crate::adjacency::WeightedAdjacencyGraph,
    max_iterations: usize,
) -> CommunityMap {
    let nodes = graph.all_nodes();
    let mut labels: BTreeMap<String, u64> = nodes
        .iter()
        .enumerate()
        .map(|(i, n)| (n.clone(), i as u64))
        .collect();

    for _ in 0..max_iterations {
        let mut changed = false;
        for node in &nodes {
            // Collect weighted votes: (label, total_weight).
            let mut votes: BTreeMap<u64, f64> = BTreeMap::new();
            for (n, w) in graph.neighbors_out(node) {
                if let Some(&l) = labels.get(n) {
                    *votes.entry(l).or_default() += *w;
                }
            }
            for (n, w) in graph.neighbors_in(node) {
                if let Some(&l) = labels.get(n) {
                    *votes.entry(l).or_default() += *w;
                }
            }
            if votes.is_empty() {
                continue;
            }
            // Pick the label with the highest total weight.
            // Tie-break: lowest label value wins (deterministic).
            let new_label = votes
                .iter()
                .max_by(|a, b| {
                    a.1.partial_cmp(b.1)
                        .unwrap_or(std::cmp::Ordering::Equal)
                        .then_with(|| b.0.cmp(a.0))
                })
                .map(|(l, _)| *l)
                .unwrap_or(0);
            if labels.get(node) != Some(&new_label) {
                labels.insert(node.clone(), new_label);
                changed = true;
            }
        }
        if !changed {
            break;
        }
    }

    CommunityMap { labels }
}