ExLeiden

Hex.pm VersionHexDocs

A pure Elixir implementation of the Leiden algorithm for community detection in networks.

The Leiden algorithm improves upon the Louvain method by addressing the resolution limit problem and ensuring communities that are well-connected internally.

Note: This is a work-in-progress implementation. The core algorithm structure is complete, but the API and result format may change before v1.0.

Note: For the best reading experience with properly rendered mathematical formulas, view this README on GitHub.

Installation

Add ex_leiden to your list of dependencies in mix.exs:

def deps do
  [
    {:ex_leiden, "~> 0.1"}
  ]
end

Configuration

ExLeiden leverages Nx numerical definitions (defn) for GPU-accelerated computation. To enable hardware acceleration, configure the EXLA backend in your application's config/config.exs:

# Configure Nx to use EXLA backend
config :nx, :default_backend, EXLA.Backend

# Configure EXLA compilation options
config :nx, :default_defn_options, [
  compiler: EXLA,
  client: :host  # Use :cuda or :rocm for GPU acceleration
]

Backend Configuration Options:

For GPU acceleration setup and additional client options, refer to the EXLA documentation.

Leiden Algorithm Overview

The Leiden algorithm consists of three main phases:

  1. Local moving phase - Moves nodes between communities to optimize the quality function
  2. Refinement phase - Splits disconnected communities to ensure well-connected communities
  3. Aggregation phase - Creates aggregate networks for the next iteration

This approach guarantees well-connected communities and addresses the resolution limit problem found in the Louvain method.

References: From Louvain to Leiden: guaranteeing well-connected communities

Quality Functions

ExLeiden supports two quality functions for community detection:

Modularity

$$H = \frac{1}{2m} \sum_c \left( e_c - \gamma \frac{K_c^2}{2m} \right)$$

Constant Potts Model (CPM)

$$H = \sum_c \left( e_c - \gamma \binom{n_c}{2} \right)$$

Where:

Usage

ExLeiden accepts graphs in multiple formats and converts them internally to adjacency matrices for efficient computation.

# From edge list (unweighted)
edges = [{1, 2}, {2, 3}, {3, 1}]
{:ok, %{source: source, result: result}} = ExLeiden.call(edges)

# From edge list (weighted)
weighted_edges = [{:a, :b, 0.5}, {:b, :c, 1.2}, {:c, :a, 0.8}]
{:ok, %{source: _source, result: result}} = ExLeiden.call(weighted_edges)

# From explicit vertices and edges
vertices = ["alice", "bob", "carol"]
edges = [{"alice", "bob"}, {"bob", "carol"}]
{:ok, %{source: _source, result: result}} = ExLeiden.call({vertices, edges})

# From adjacency matrix (2D list)
matrix = [
  [0, 1, 1],
  [1, 0, 1],
  [1, 1, 0]
]
{:ok, %{source: _source, result: result}} = ExLeiden.call(matrix)

# From Nx tensor adjacency matrix
tensor = Nx.tensor([[0, 1, 0], [1, 0, 1], [0, 1, 0]])
{:ok, %{source: _source, result: result}} = ExLeiden.call(tensor)

# From libgraph Graph struct
graph = Graph.new()
        |> Graph.add_vertices([1, 2, 3])
        |> Graph.add_edges([{1, 2}, {2, 3}])
{:ok, %{source: _source, result: result}} = ExLeiden.call(graph)

# With options
{:ok, %{source: _source, result: result}} = ExLeiden.call(edges, [
  resolution: 1.5,
  quality_function: :cpm,
  community_size_threshold: 10  # Stop when communities ≤ 10 nodes
])

Options

The algorithm behavior can be customized using various options:

Result Format

Returns {:ok, result} where result is a map containing:

Complete Result Structure

{:ok, %{
  source: %ExLeiden.Source{
    adjacency_matrix: #Nx.Tensor<...>,
    # ... other source fields
  },
  result: %{
    1 => {
      [
        %{id: 0, children: [1, 2, 3]},    # Community 0 contains nodes [1, 2, 3]
        %{id: 1, children: [4, 5]},       # Community 1 contains nodes [4, 5]
        %{id: 2, children: [6, 7, 8]}     # Community 2 contains nodes [6, 7, 8]
      ],
      [
        {0, 1, 0.5},    # Bridge between community 0 and 1 with weight 0.5
        {1, 2, 0.3}     # Bridge between community 1 and 2 with weight 0.3
      ]
    },
    2 => {
      [
        %{id: 0, children: [0, 1]},       # Level 2 community contains level 1 communities 0 and 1
        %{id: 1, children: [2]}           # Level 2 community contains level 1 community 2
      ],
      [
        {0, 1, 0.2}     # Bridge between level 2 communities
      ]
    }
  }
}}

Structure Details

Error Handling

The only source of errors is option validation. The Leiden algorithm itself cannot fail - it always produces a valid community detection result. Invalid options return {:error, reason} tuples:

# Invalid options - returns map of option -> reason
{:error, %{
  resolution: "must be a positive number",
  quality_function: "must be :modularity or :cpm"
}}

Implementation Status

✅ Completed Features

🚧 TODOs