nordisk/facett

facett-graphview/src/analysis/similarity.rs

//! **Node similarity** — neighbourhood-overlap measures over the undirected view:
//! common neighbours, Jaccard, Adamic–Adar, and cosine. Each compares two nodes by
//! how much their neighbour sets overlap — the link-prediction / "you may also know"
//! primitive.

use std::collections::BTreeSet;

use super::Adjacency;

/// The undirected neighbour set of `i` (as a sorted set for fast intersection).
fn neighbours(g: &Adjacency, i: usize) -> BTreeSet<usize> {
    g.und.get(i).map(|l| l.iter().map(|&(j, _)| j).collect()).unwrap_or_default()
}

/// The **count of common neighbours** of `a` and `b`.
#[must_use]
pub fn common_neighbours(g: &Adjacency, a: usize, b: usize) -> usize {
    if a >= g.n || b >= g.n {
        return 0;
    }
    let (na, nb) = (neighbours(g, a), neighbours(g, b));
    na.intersection(&nb).count()
}

/// **Jaccard similarity** — `|N(a) ∩ N(b)| / |N(a) ∪ N(b)|` ∈ `[0,1]`. `0.0` when
/// both neighbourhoods are empty.
#[must_use]
pub fn jaccard(g: &Adjacency, a: usize, b: usize) -> f32 {
    if a >= g.n || b >= g.n {
        return 0.0;
    }
    let (na, nb) = (neighbours(g, a), neighbours(g, b));
    let inter = na.intersection(&nb).count();
    let union = na.union(&nb).count();
    if union == 0 { 0.0 } else { inter as f32 / union as f32 }
}

/// **Adamic–Adar index** — `Σ_{z ∈ N(a) ∩ N(b)} 1 / ln(deg z)`, weighting rare shared
/// neighbours more. Degree-1 shared neighbours (ln 1 = 0) are skipped.
#[must_use]
pub fn adamic_adar(g: &Adjacency, a: usize, b: usize) -> f32 {
    if a >= g.n || b >= g.n {
        return 0.0;
    }
    let (na, nb) = (neighbours(g, a), neighbours(g, b));
    na.intersection(&nb)
        .filter_map(|&z| {
            let d = g.degree(z) as f32;
            if d > 1.0 { Some(1.0 / d.ln()) } else { None }
        })
        .sum()
}

/// **Cosine similarity** of neighbourhoods — `|N(a) ∩ N(b)| / sqrt(|N(a)|·|N(b)|)`.
#[must_use]
pub fn cosine(g: &Adjacency, a: usize, b: usize) -> f32 {
    if a >= g.n || b >= g.n {
        return 0.0;
    }
    let (na, nb) = (neighbours(g, a), neighbours(g, b));
    let inter = na.intersection(&nb).count() as f32;
    let denom = ((na.len() * nb.len()) as f32).sqrt();
    if denom <= 0.0 { 0.0 } else { inter / denom }
}

/// The `top_k` most Jaccard-similar nodes to `a` (excluding `a` itself), as
/// `(node, score)` sorted by score descending then index ascending. Zero-score
/// candidates are dropped.
#[must_use]
pub fn most_similar(g: &Adjacency, a: usize, top_k: usize) -> Vec<(usize, f32)> {
    if a >= g.n {
        return Vec::new();
    }
    let mut scored: Vec<(usize, f32)> =
        (0..g.n).filter(|&b| b != a).map(|b| (b, jaccard(g, a, b))).filter(|&(_, s)| s > 0.0).collect();
    scored.sort_by(|x, y| y.1.partial_cmp(&x.1).unwrap_or(std::cmp::Ordering::Equal).then(x.0.cmp(&y.0)));
    scored.truncate(top_k);
    scored
}

#[cfg(test)]
mod tests {
    use super::*;

    /// Two nodes 0 and 1 sharing neighbours 2 and 3; node 4 shares nothing with 0.
    fn shared() -> Adjacency {
        Adjacency::from_edges(5, &[(0, 2), (0, 3), (1, 2), (1, 3), (4, 2)])
    }

    #[test]
    fn common_neighbours_and_jaccard() {
        let g = shared();
        assert_eq!(common_neighbours(&g, 0, 1), 2, "0 and 1 share {{2,3}}");
        // N(0)={2,3}, N(1)={2,3} → identical → Jaccard 1.0.
        assert!((jaccard(&g, 0, 1) - 1.0).abs() < 1e-6);
        // N(0)={2,3}, N(4)={2} → inter 1, union 2 → 0.5.
        assert!((jaccard(&g, 0, 4) - 0.5).abs() < 1e-6);
    }

    #[test]
    fn cosine_matches_hand_calc() {
        let g = shared();
        // inter 2, |N0|=2, |N1|=2 → 2/sqrt(4)=1.0.
        assert!((cosine(&g, 0, 1) - 1.0).abs() < 1e-6);
        // inter 1, |N0|=2, |N4|=1 → 1/sqrt(2) ≈ 0.7071.
        assert!((cosine(&g, 0, 4) - std::f32::consts::FRAC_1_SQRT_2).abs() < 1e-4);
    }

    #[test]
    fn adamic_adar_weights_rare_shared_neighbours() {
        let g = shared();
        // Shared neighbours 2 (deg 3) and 3 (deg 2): 1/ln3 + 1/ln2.
        let expect = 1.0 / 3f32.ln() + 1.0 / 2f32.ln();
        assert!((adamic_adar(&g, 0, 1) - expect).abs() < 1e-4, "AA = {}", adamic_adar(&g, 0, 1));
    }

    #[test]
    fn most_similar_ranks_the_twin_first() {
        let g = shared();
        let top = most_similar(&g, 0, 3);
        assert_eq!(top[0].0, 1, "node 1 is 0's exact neighbourhood twin");
        assert!((top[0].1 - 1.0).abs() < 1e-6);
        // Node 4 shares one neighbour → present but lower.
        assert!(top.iter().any(|&(n, _)| n == 4));
    }

    #[test]
    fn out_of_range_and_empty_are_safe() {
        let g = shared();
        assert_eq!(common_neighbours(&g, 0, 99), 0);
        assert_eq!(jaccard(&g, 99, 0), 0.0);
        assert!(most_similar(&g, 99, 5).is_empty());
    }
}