# `Yog.Community.Walktrap`
[🔗](https://github.com/code-shoily/yog_ex/blob/v0.97.0/lib/yog/community/walktrap.ex#L1)

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

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

| 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

- [Pons & Latapy 2006 - Computing communities with random walks](https://doi.org/10.1080/15427951.2007.10129237)
- [Wikipedia: Walktrap Algorithm](https://en.wikipedia.org/wiki/Walktrap_community)

# `walktrap_options`

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

Options for Walktrap algorithm

# `default_options`

```elixir
@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`

```elixir
@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`

```elixir
@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`

```elixir
@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
    )

---

*Consult [api-reference.md](api-reference.md) for complete listing*