label_propagation

Label Propagation Algorithm (LPA) for community detection.

A near-linear time algorithm that detects community structure by propagating labels through the network. Each node adopts the most frequent label among its neighbors until convergence.

Algorithm

Initialize: Each node gets a unique label
Iterate: Nodes update their label to the most common among neighbors
Converge: Stop when no changes occur or max iterations reached

When to Use

Use Case	Recommendation
Very large graphs	✓ Excellent (near-linear time)
Speed critical	✓ Fastest option
Quality priority	Consider Louvain/Leiden
Overlapping communities	Use Clique Percolation

Complexity

Time: O(E × iterations), typically near-linear in practice
Space: O(V + E)

Example

import yog
import yog/community/label_propagation as lpa

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)])

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

// With custom options
let options = lpa.LabelPropagationOptions(max_iterations: 100, seed: 42)
let communities = lpa.detect_with_options(graph, options)

References

Types

LabelPropagationOptions

</>

Options for Label Propagation Algorithm.

pub type LabelPropagationOptions {
  LabelPropagationOptions(max_iterations: Int, seed: Int)
}

Constructors

LabelPropagationOptions(max_iterations: Int, seed: Int)

Values

default_options

</>

pub fn default_options() -> LabelPropagationOptions

Default options for LPA.

detect

</>

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

Detects communities using the Label Propagation Algorithm.

detect_with_options

</>

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

Detects communities using LPA with custom options.