Run Louvain Community Detection on the CSR index. Returns `(node_id, community_id, modularity)` rows.
(csr: &CsrIndex, params: &AlgoParams)
| 26 | /// |
| 27 | /// Returns `(node_id, community_id, modularity)` rows. |
| 28 | pub fn run(csr: &CsrIndex, params: &AlgoParams) -> AlgoResultBatch { |
| 29 | let n = csr.node_count(); |
| 30 | if n == 0 { |
| 31 | return AlgoResultBatch::new(GraphAlgorithm::Louvain); |
| 32 | } |
| 33 | |
| 34 | let max_iter = params.iterations(10); |
| 35 | let resolution = params.louvain_resolution(); |
| 36 | let mut reporter = ProgressReporter::new(GraphAlgorithm::Louvain, max_iter, None, n); |
| 37 | |
| 38 | // Build undirected weighted adjacency for modularity computation. |
| 39 | // For unweighted graphs, each undirected edge has weight 1.0. |
| 40 | let (adj, node_degree, total_weight) = build_undirected_adjacency(csr, n); |
| 41 | |
| 42 | // Initialize: each node is its own community. |
| 43 | let mut community: Vec<usize> = (0..n).collect(); |
| 44 | |
| 45 | // Precompute community-level aggregates. |
| 46 | let mut comm_total_degree: Vec<f64> = node_degree.clone(); |
| 47 | |
| 48 | for iter in 1..=max_iter { |
| 49 | let mut moved = 0usize; |
| 50 | |
| 51 | for node in 0..n { |
| 52 | let current_comm = community[node]; |
| 53 | let node_deg = node_degree[node]; |
| 54 | |
| 55 | // Compute weights to each neighbor community. |
| 56 | let mut comm_weights: HashMap<usize, f64> = HashMap::new(); |
| 57 | for &(neighbor, weight) in &adj[node] { |
| 58 | let nc = community[neighbor]; |
| 59 | *comm_weights.entry(nc).or_insert(0.0) += weight; |
| 60 | } |
| 61 | |
| 62 | // Weight to current community. |
| 63 | let w_current = comm_weights.get(¤t_comm).copied().unwrap_or(0.0); |
| 64 | |
| 65 | // Find best community to move to. |
| 66 | let mut best_comm = current_comm; |
| 67 | let mut best_gain = 0.0f64; |
| 68 | |
| 69 | for (&candidate_comm, &w_candidate) in &comm_weights { |
| 70 | if candidate_comm == current_comm { |
| 71 | continue; |
| 72 | } |
| 73 | // Modularity gain of moving to candidate vs staying. |
| 74 | let net_gain = (w_candidate - w_current) |
| 75 | - resolution |
| 76 | * node_deg |
| 77 | * (comm_total_degree[candidate_comm] - comm_total_degree[current_comm] |
| 78 | + node_deg) |
| 79 | / (2.0 * total_weight); |
| 80 | |
| 81 | if net_gain > best_gain { |
| 82 | best_gain = net_gain; |
| 83 | best_comm = candidate_comm; |
| 84 | } |
| 85 | } |