yog/community/walktrap

Walktrap community detection algorithm.

Identifies communities using random walks to define distances between nodes. Nodes in the same community tend to have similar transition probabilities to other nodes (they “see” the network similarly).

Algorithm

1. Compute transition probabilities P^t (t-step random walk)
2. Define distance between nodes based on transition probability differences
3. Merge closest communities iteratively (hierarchical agglomerative)
4. Return hierarchy of community partitions

When to Use

Complexity

• Time: O(V² × log V) for hierarchical clustering
• Space: O(V²) for distance matrix

Example

import yog
import yog/community/walktrap

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 (walk_length=4 is default)
let communities = walktrap.detect(graph)

// With options
let options = walktrap.WalktrapOptions(
  walk_length: 4,
  target_communities: Some(2),
)
let communities = walktrap.detect_with_options(graph, options)

// Full hierarchical detection
let dendrogram = walktrap.detect_hierarchical(graph, walk_length: 4)

References

• Pons & Latapy 2006 - Computing communities with random walks
• Wikipedia: Walktrap Algorithm

pub type WalktrapOptions {
  WalktrapOptions(
    walk_length: Int,
    target_communities: option.Option(Int),
  )
}

pub fn default_options() -> WalktrapOptions

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

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

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