Function louvain_communities 

pub fn louvain_communities(
    graph: &SqliteGraph,
    max_iterations: usize,
) -> Result<Vec<Vec<i64>>, SqliteGraphError>

Louvain method for community detection via modularity optimization.

Iteratively moves nodes to maximize modularity (how many edges are within communities vs between communities). This is a simplified single-pass version.

Arguments

• graph - The graph to analyze
• max_iterations - Maximum number of iterations to prevent infinite loops (typically 10-20)

Returns

Communities as vectors of node IDs, sorted by smallest node ID in each community.

Complexity

Time: O(k * |V| * |E|) where k = iterations Space: O(|V|) for community assignments and degrees

Algorithm Details

Simplified single-pass modularity optimization (no multi-level aggregation):

1. Initialize each node in its own community
2. Calculate total edges (m) and node degrees
3. Iteratively move nodes to maximize modularity delta: ΔQ = (2edges_to_community - node_degreecommunity_degree/m) / (2*m)
4. Stop when no moves improve modularity

Modularity measures edge density within communities vs random expectation. Higher values indicate better community structure (typical range: 0.3-0.7).

Caveats

• Simplified version (no multi-level aggregation)
• May converge to local optima (not guaranteed global optimum)
• Performance depends on graph structure and edge distribution

References

• Blondel, V. D., et al. (2008). “Fast unfolding of communities in large networks.”

Example

use sqlitegraph::{SqliteGraph, algo::louvain_communities};
let graph = SqliteGraph::open_in_memory()?;
// ... add nodes and edges ...
let communities = louvain_communities(&graph, 10)?;