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

Girvan-Newman algorithm for hierarchical community detection.

Detects communities by iteratively removing edges with the highest
edge betweenness centrality. Edges with high betweenness are "bridges"
between communities.

## Algorithm

1. **Calculate** edge betweenness centrality for all edges
2. **Remove** the edge(s) with highest betweenness (batch removal)
3. **Repeat** until no edges remain
4. **Record** connected components at each step (hierarchy)

## When to Use

| Use Case | Recommendation |
|----------|----------------|
| Hierarchical structure needed | ✓ Excellent |
| Small to medium graphs | ✓ Good |
| Large graphs | ✗ Too slow (use Louvain/Leiden) |
| Edge importance analysis | ✓ Provides edge betweenness |

## Complexity

- **Time**: O(E² × V) or O(E³) in worst case - expensive!
- **Space**: O(V + E)

**Note**: This algorithm is significantly slower than Louvain/Leiden.
Use only when you specifically need the hierarchical decomposition.

## Example

    # Basic usage - returns finest partition
    communities = Yog.Community.GirvanNewman.detect(graph)

    # With options - target specific number of communities
    {:ok, communities} = Yog.Community.GirvanNewman.detect_with_options(graph,
      target_communities: 2
    )

    # Full hierarchical detection
    dendrogram = Yog.Community.GirvanNewman.detect_hierarchical(graph)

## References

- [Girvan & Newman 2002 - Community structure in social networks](https://doi.org/10.1073/pnas.122653799)
- [Wikipedia: Girvan-Newman Algorithm](https://en.wikipedia.org/wiki/Girvan%E2%80%93Newman_algorithm)

# `girvan_newman_options`

```elixir
@type girvan_newman_options() :: %{target_communities: integer() | nil}
```

Options for Girvan-Newman algorithm

# `default_options`

```elixir
@spec default_options() :: girvan_newman_options()
```

Returns default options for Girvan-Newman.

## Defaults

- `target_communities`: nil - Full dendrogram (all levels)

# `detect`

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

Detects communities using Girvan-Newman with default options.

Returns the finest partition (most communities).

# `detect_hierarchical`

```elixir
@spec detect_hierarchical(Yog.graph()) :: Yog.Community.Dendrogram.t()
```

Full hierarchical Girvan-Newman detection.

Returns a dendrogram with community structure at each level as edges are removed.

## Example

    dendrogram = Yog.Community.GirvanNewman.detect_hierarchical(graph)
    IO.inspect(length(dendrogram.levels))

# `detect_with_options`

```elixir
@spec detect_with_options(Yog.graph(), keyword() | map()) ::
  {:ok, Yog.Community.Result.t()} | {:error, String.t()}
```

Detects communities using Girvan-Newman with custom options.

## Options

- `:target_communities` - Stop when this many communities reached (default: nil = full)

## Example

    {:ok, communities} = Yog.Community.GirvanNewman.detect_with_options(graph,
      target_communities: 3
    )

# `edge_betweenness`

```elixir
@spec edge_betweenness(Yog.graph()) :: %{
  required({Yog.node_id(), Yog.node_id()}) => float()
}
```

Calculates edge betweenness centrality for all edges.

Returns a map of `{node1, node2} => betweenness_score` where node1 < node2.

## Example

    betweenness = Yog.Community.GirvanNewman.edge_betweenness(graph)
    IO.inspect(betweenness)

---

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