rsomics_local_efficiency/
lib.rs

1/// Compute local efficiency of an undirected graph.
2///
3/// Replicates `networkx.local_efficiency` exactly:
4/// - `local_efficiency(G) = (Σ_v global_efficiency(G[N(v)])) / |V|`
5/// - `global_efficiency(H) = (Σ_{i≠j} 1/d(i,j)) / (|V|(|V|-1))`
6///   where d is BFS hop-distance within the subgraph
7/// - Nodes with fewer than 2 neighbours contribute 0.
8///
9/// Ref: Latora & Marchiori, PRL 87(19):198701 (2001). doi:10.1103/PhysRevLett.87.198701
10use std::collections::{HashMap, HashSet, VecDeque};
11
12/// Parse an undirected edge list from text.
13///
14/// Lines starting with `#` or blank are skipped (nx.read_edgelist convention).
15/// Self-loops are dropped. Parallel edges are deduplicated (nx.Graph semantics).
16/// Node IDs are assigned in first-seen order (matching networkx insertion order).
17///
18/// Returns `(n, adj)` where `adj[i]` is the neighbour list of node `i` in
19/// insertion order.
20pub fn parse_edge_list_ordered(input: &str) -> (usize, Vec<Vec<usize>>) {
21    let mut name_to_id: HashMap<String, usize> = HashMap::new();
22    let mut next_id = 0usize;
23    let mut parsed: Vec<(usize, usize)> = Vec::new();
24
25    for line in input.lines() {
26        let line = line.trim();
27        if line.is_empty() || line.starts_with('#') {
28            continue;
29        }
30        let mut parts = line.split_ascii_whitespace();
31        let Some(u_str) = parts.next() else { continue };
32        let Some(v_str) = parts.next() else { continue };
33
34        let u = *name_to_id.entry(u_str.to_owned()).or_insert_with(|| {
35            let id = next_id;
36            next_id += 1;
37            id
38        });
39        let v = *name_to_id.entry(v_str.to_owned()).or_insert_with(|| {
40            let id = next_id;
41            next_id += 1;
42            id
43        });
44        if u != v {
45            parsed.push((u, v));
46        }
47    }
48
49    let n = next_id;
50    let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
51    let mut seen: HashSet<(usize, usize)> = HashSet::with_capacity(parsed.len());
52
53    for (u, v) in parsed {
54        let key = if u < v { (u, v) } else { (v, u) };
55        if seen.insert(key) {
56            adj[u].push(v);
57            adj[v].push(u);
58        }
59    }
60
61    (n, adj)
62}
63
64/// BFS within a subgraph defined by `local_nodes` (global IDs in local index order).
65/// `local_index[global_id]` = local index, or `u32::MAX` if not in the subgraph.
66/// Returns hop-distances from `src_local` to every node in the subgraph.
67fn bfs_distances(
68    global_adj: &[Vec<usize>],
69    local_nodes: &[usize],
70    local_index: &[u32],
71    src_local: usize,
72) -> Vec<u32> {
73    let k = local_nodes.len();
74    let mut dist = vec![u32::MAX; k];
75    dist[src_local] = 0;
76    let mut queue = VecDeque::with_capacity(k);
77    queue.push_back(src_local);
78
79    while let Some(u_loc) = queue.pop_front() {
80        let d = dist[u_loc];
81        let u_glob = local_nodes[u_loc];
82        for &v_glob in &global_adj[u_glob] {
83            let li = local_index[v_glob];
84            if li == u32::MAX {
85                continue;
86            }
87            let v_loc = li as usize;
88            if dist[v_loc] == u32::MAX {
89                dist[v_loc] = d + 1;
90                queue.push_back(v_loc);
91            }
92        }
93    }
94    dist
95}
96
97/// Global efficiency of the subgraph induced by `local_nodes` (global IDs).
98/// Matches `networkx.global_efficiency` exactly, iterating in node insertion order.
99fn global_efficiency_subgraph(global_adj: &[Vec<usize>], local_nodes: &[usize]) -> f64 {
100    let k = local_nodes.len();
101    if k < 2 {
102        return 0.0;
103    }
104
105    let global_n = global_adj.len();
106    let mut local_index = vec![u32::MAX; global_n];
107    for (i, &g) in local_nodes.iter().enumerate() {
108        local_index[g] = i as u32;
109    }
110
111    let denom = (k * (k - 1)) as f64;
112    let mut g_eff = 0.0f64;
113
114    for src in 0..k {
115        let dist = bfs_distances(global_adj, local_nodes, &local_index, src);
116        for &d in &dist {
117            if d > 0 && d != u32::MAX {
118                g_eff += 1.0 / d as f64;
119            }
120        }
121    }
122
123    g_eff / denom
124}
125
126/// Compute local efficiency, matching `networkx.local_efficiency`.
127pub fn local_efficiency(n: usize, adj: &[Vec<usize>]) -> f64 {
128    if n == 0 {
129        return 0.0;
130    }
131
132    let mut total = 0.0f64;
133    for v in 0..n {
134        total += global_efficiency_subgraph(adj, &adj[v]);
135    }
136    total / n as f64
137}
rsomics_local_efficiency/lib.rs

rsomics_local_efficiency/
lib.rs
