yog/community/louvain

Louvain method for community detection.

A fast, hierarchical algorithm that optimizes modularity. One of the most widely used community detection algorithms due to its excellent balance of speed and quality.

Algorithm

The Louvain method works in two phases that repeat until convergence:

1. Local Optimization: Each node moves to the neighbor community that maximizes modularity gain
2. Aggregation: Communities become super-nodes in a new aggregated graph
3. Repeat until no improvement in modularity

When to Use

Complexity

• Time: O(E × iterations), typically O(E log V) in practice
• Space: O(V + E)

Example

import yog
import yog/community/louvain
import yog/community/metrics

let graph =
  yog.undirected()
  |> yog.add_node(1, "A")
  |> yog.add_node(2, "B")
  |> yog.add_node(3, "C")
  |> yog.add_edges([#(1, 2, 1), #(2, 3, 1), #(1, 3, 1)])

// Basic usage
let communities = louvain.detect(graph)
io.debug(communities.num_communities)  // => 1 (all connected)

// With custom options
let options = louvain.LouvainOptions(
  min_modularity_gain: 0.0001,
  max_iterations: 100,
  seed: 42,
)
let communities = louvain.detect_with_options(graph, options)

// Evaluate quality with modularity
let q = metrics.modularity(graph, communities)
io.debug(q)  // => 0.0 to 1.0 (higher is better)

References

• Blondel et al. 2008 - Fast unfolding of communities
• Wikipedia: Louvain Method

pub type LouvainOptions {
  LouvainOptions(
    min_modularity_gain: Float,
    max_iterations: Int,
    seed: Int,
  )
}

pub type LouvainStats {
  LouvainStats(
    num_phases: Int,
    final_modularity: Float,
    iteration_modularity: List(Float),
  )
}

pub fn default_options() -> LouvainOptions

pub fn detect(
  graph: model.Graph(n, Int),
) -> community.Communities

pub fn detect_hierarchical(
  graph: model.Graph(n, Int),
) -> community.Dendrogram

pub fn detect_hierarchical_with_options(
  graph: model.Graph(n, Int),
  options: LouvainOptions,
) -> community.Dendrogram

pub fn detect_with_options(
  graph: model.Graph(n, Int),
  options: LouvainOptions,
) -> community.Communities

pub fn detect_with_stats(
  graph: model.Graph(n, Int),
  options: LouvainOptions,
) -> #(community.Communities, LouvainStats)