Yog.Community.Louvain (YogEx v0.97.0)

Copy Markdown View Source

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

Use CaseRecommendation
Large graphs (millions of nodes)✓ Excellent
Hierarchical structure needed✓ Yes
General purpose✓ Works well on most networks
Quality over speedConsider Leiden

Complexity

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

Example

# Basic usage
communities = Yog.Community.Louvain.detect(graph)
communities.num_communities  # => number of communities found

# With custom options
options = [
  min_modularity_gain: 0.0001,
  max_iterations: 100,
  seed: 42
]
communities = Yog.Community.Louvain.detect_with_options(graph, options)

References

Summary

Types

louvain_options()

Options for the Louvain algorithm

louvain_stats()

Statistics from the Louvain algorithm run

Functions

default_options()

Returns default options for Louvain algorithm.

detect(graph)

Detects communities using the Louvain algorithm with default options.

detect_hierarchical(graph)

Full hierarchical Louvain detection.

detect_hierarchical_with_options(graph, opts)

Full hierarchical Louvain detection with custom options.

detect_with_options(graph, opts)

Detects communities using the Louvain algorithm with custom options.

detect_with_stats(graph, opts)

Detects communities and returns statistics for debugging/analysis.

Types

louvain_options()

@type louvain_options() :: %{
  min_modularity_gain: float(),
  max_iterations: integer(),
  resolution: float(),
  seed: integer()
}

Options for the Louvain algorithm

louvain_stats()

@type louvain_stats() :: %{
  num_phases: integer(),
  final_modularity: float(),
  iteration_modularity: [float()]
}

Statistics from the Louvain algorithm run

Functions

default_options()

@spec default_options() :: louvain_options()

Returns default options for Louvain algorithm.

detect(graph)

@spec detect(Yog.graph()) :: Yog.Community.Result.t()

Detects communities using the Louvain algorithm with default options.

detect_hierarchical(graph)

@spec detect_hierarchical(Yog.graph()) :: Yog.Community.Dendrogram.t()

Full hierarchical Louvain detection.

detect_hierarchical_with_options(graph, opts)

@spec detect_hierarchical_with_options(
  Yog.graph(),
  keyword()
) :: Yog.Community.Dendrogram.t()

Full hierarchical Louvain detection with custom options.

detect_with_options(graph, opts)

@spec detect_with_options(
  Yog.graph(),
  keyword()
) :: Yog.Community.Result.t()

Detects communities using the Louvain algorithm with custom options.

Options

  • :min_modularity_gain - Stop when gain < threshold (default: 0.000001)
  • :max_iterations - Maximum iterations per phase (default: 100)
  • :resolution - Resolution parameter (gamma) (default: 1.0)
  • :seed - Random seed for tie-breaking (default: 42)

detect_with_stats(graph, opts)

@spec detect_with_stats(
  Yog.graph(),
  keyword()
) :: {Yog.Community.Result.t(), louvain_stats()}

Detects communities and returns statistics for debugging/analysis.