Function label_propagation 

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

Label Propagation algorithm for fast community detection.

Each node starts with its own label, then iteratively adopts the most frequent label among its neighbors. Converges when no labels change or max_iterations reached.

This is a near-linear time algorithm suitable for large graphs. Uses deterministic tiebreaking (smallest label wins) for reproducible results.

Arguments

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

Returns

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

Complexity

Time: O(k * |E|) where k = iterations (typically 5-10) Space: O(|V|) for label storage

Algorithm Details

• Initialize each node with unique label (node ID)
• Iteratively adopt most frequent neighbor label
• Bidirectional edges (both incoming and outgoing neighbors)
• Deterministic tiebreaking: smallest label wins
• Early stopping when converged (no labels change)

References

• Raghavan, U. N., Albert, R., & Kumara, S. (2007). “Near linear time algorithm to detect community structures in large-scale networks.”

Example

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