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/// Parallel edges are deduplicated (nx.Graph semantics). Self-loops are kept:
16/// networkx stores `v` in its own adjacency `G[v]`, so `adj[v]` includes `v`.
17/// This matters because `local_efficiency` induces a subgraph on `G[v]`, and a
18/// self-loop makes `v` a member of that neighbour set.
19/// Node IDs are assigned in first-seen order (matching networkx insertion order).
20///
21/// Returns `(n, adj)` where `adj[i]` is the neighbour list of node `i` in
22/// insertion order, including `i` itself when `i` carries a self-loop.
23pub fn parse_edge_list_ordered(input: &str) -> (usize, Vec<Vec<usize>>) {
24    let mut name_to_id: HashMap<String, usize> = HashMap::new();
25    let mut next_id = 0usize;
26    let mut parsed: Vec<(usize, usize)> = Vec::new();
27
28    for line in input.lines() {
29        let line = line.trim();
30        if line.is_empty() || line.starts_with('#') {
31            continue;
32        }
33        let mut parts = line.split_ascii_whitespace();
34        let Some(u_str) = parts.next() else { continue };
35        let Some(v_str) = parts.next() else { continue };
36
37        let u = *name_to_id.entry(u_str.to_owned()).or_insert_with(|| {
38            let id = next_id;
39            next_id += 1;
40            id
41        });
42        let v = *name_to_id.entry(v_str.to_owned()).or_insert_with(|| {
43            let id = next_id;
44            next_id += 1;
45            id
46        });
47        parsed.push((u, v));
48    }
49
50    let n = next_id;
51    let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
52    let mut seen: HashSet<(usize, usize)> = HashSet::with_capacity(parsed.len());
53
54    for (u, v) in parsed {
55        let key = if u <= v { (u, v) } else { (v, u) };
56        if !seen.insert(key) {
57            continue;
58        }
59        if u == v {
60            adj[u].push(u);
61        } else {
62            adj[u].push(v);
63            adj[v].push(u);
64        }
65    }
66
67    (n, adj)
68}
69
70/// BFS within a subgraph defined by `local_nodes` (global IDs in local index order).
71/// `local_index[global_id]` = local index, or `u32::MAX` if not in the subgraph.
72/// Returns hop-distances from `src_local` to every node in the subgraph.
73fn bfs_distances(
74    global_adj: &[Vec<usize>],
75    local_nodes: &[usize],
76    local_index: &[u32],
77    src_local: usize,
78) -> Vec<u32> {
79    let k = local_nodes.len();
80    let mut dist = vec![u32::MAX; k];
81    dist[src_local] = 0;
82    let mut queue = VecDeque::with_capacity(k);
83    queue.push_back(src_local);
84
85    while let Some(u_loc) = queue.pop_front() {
86        let d = dist[u_loc];
87        let u_glob = local_nodes[u_loc];
88        for &v_glob in &global_adj[u_glob] {
89            let li = local_index[v_glob];
90            if li == u32::MAX {
91                continue;
92            }
93            let v_loc = li as usize;
94            if dist[v_loc] == u32::MAX {
95                dist[v_loc] = d + 1;
96                queue.push_back(v_loc);
97            }
98        }
99    }
100    dist
101}
102
103/// Global efficiency of the subgraph induced by `local_nodes` (global IDs).
104/// Matches `networkx.global_efficiency` exactly, iterating in node insertion order.
105fn global_efficiency_subgraph(global_adj: &[Vec<usize>], local_nodes: &[usize]) -> f64 {
106    let k = local_nodes.len();
107    if k < 2 {
108        return 0.0;
109    }
110
111    let global_n = global_adj.len();
112    let mut local_index = vec![u32::MAX; global_n];
113    for (i, &g) in local_nodes.iter().enumerate() {
114        local_index[g] = i as u32;
115    }
116
117    let denom = (k * (k - 1)) as f64;
118    let mut g_eff = 0.0f64;
119
120    for src in 0..k {
121        let dist = bfs_distances(global_adj, local_nodes, &local_index, src);
122        for &d in &dist {
123            if d > 0 && d != u32::MAX {
124                g_eff += 1.0 / d as f64;
125            }
126        }
127    }
128
129    g_eff / denom
130}
131
132/// Compute local efficiency, matching `networkx.local_efficiency`.
133pub fn local_efficiency(n: usize, adj: &[Vec<usize>]) -> f64 {
134    if n == 0 {
135        return 0.0;
136    }
137
138    let mut total = 0.0f64;
139    for v in 0..n {
140        total += global_efficiency_subgraph(adj, &adj[v]);
141    }
142    total / n as f64
143}
rsomics_local_efficiency/lib.rs

rsomics_local_efficiency/
lib.rs
