yog/community/leiden

Leiden method for community detection.

An improvement over the Louvain algorithm that guarantees well-connected communities. Adds a refinement step to ensure communities are properly connected internally.

Algorithm

The Leiden method works in three phases that repeat until convergence:

1. Local Optimization (like Louvain): Nodes move to improve modularity
2. Refinement: Partition communities into well-connected sub-communities
3. Aggregation: Communities become super-nodes
4. Repeat until convergence

Key Differences from Louvain

When to Use

• When community quality matters more than raw speed
• When you need meaningful multi-level structure
• When disconnected communities would be problematic
• For hierarchical analysis requiring well-connected communities at each level

Complexity

• Time: Slightly slower than Louvain (refinement adds overhead)
• Space: O(V + E) same as Louvain

Example

import yog
import yog/community/leiden
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), #(3, 1, 1)])

// Basic usage
let communities = leiden.detect(graph)
io.debug(communities.num_communities)

// With custom options
let options = leiden.LeidenOptions(
  min_modularity_gain: 0.0001,
  max_iterations: 100,
  refinement_iterations: 5,
  seed: 42,
)
let communities = leiden.detect_with_options(graph, options)

References

• Traag et al. 2019 - From Louvain to Leiden
• Wikipedia: Leiden Algorithm

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

pub fn default_options() -> LeidenOptions

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: LeidenOptions,
) -> community.Dendrogram

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