Yog.Community.Walktrap (YogEx v0.97.0)

Walktrap algorithm for community detection.

Uses random walks to compute distances between nodes. Nodes are merged into communities based on these distances, creating a hierarchical structure that captures the graph's community organization.

Algorithm

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

When to Use

Use Case	Recommendation
Hierarchical structure	✓ Good
Local structure matters	✓ Captures neighborhood via walks
Large graphs	Consider faster alternatives
Quality priority	Good balance of speed and quality

Complexity

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

Example

# Basic usage (walk_length=4 is default)
communities = Yog.Community.Walktrap.detect(graph)

# With options
communities = Yog.Community.Walktrap.detect_with_options(graph,
  walk_length: 5,
  target_communities: 3
)

# Full hierarchical detection
dendrogram = Yog.Community.Walktrap.detect_hierarchical(graph, 4)

References

Summary

Types

walktrap_options()

Options for Walktrap algorithm

Functions

default_options()

Returns default options for Walktrap.

detect(graph)

Detects communities using Walktrap with default options.

detect_hierarchical(graph, walk_length \\ 4)

Full hierarchical Walktrap detection.

detect_with_options(graph, opts)

Detects communities using Walktrap with custom options.

Types

walktrap_options()

@type walktrap_options() :: %{
  walk_length: integer(),
  target_communities: integer() | nil
}

Options for Walktrap algorithm

Functions

default_options()

@spec default_options() :: walktrap_options()

Returns default options for Walktrap.

Defaults

walk_length: 4 - Number of steps in random walk
target_communities: nil - Full dendrogram (all levels)

detect(graph)

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

Detects communities using Walktrap with default options.

Example

communities = Yog.Community.Walktrap.detect(graph)
IO.inspect(communities.num_communities)

detect_hierarchical(graph, walk_length \\ 4)

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

Full hierarchical Walktrap detection.

Returns a dendrogram with community structure at each merge level.

Parameters

graph - The graph to analyze
walk_length - Number of steps in random walk (default: 4)

Example

dendrogram = Yog.Community.Walktrap.detect_hierarchical(graph, 4)
IO.inspect(length(dendrogram.levels))

detect_with_options(graph, opts)

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

Detects communities using Walktrap with custom options.

Options

:walk_length - Length of random walks (default: 4)
:target_communities - Stop when this many communities reached (default: nil = full)

Example

communities = Yog.Community.Walktrap.detect_with_options(graph,
  walk_length: 5,
  target_communities: 3
)