Yog.Community.GirvanNewman (YogEx v0.97.0)

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

Calculate edge betweenness centrality for all edges
Remove the edge(s) with highest betweenness (batch removal)
Repeat until no edges remain
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

Summary

Types

girvan_newman_options()

Options for Girvan-Newman algorithm

Functions

default_options()

Returns default options for Girvan-Newman.

detect(graph)

Detects communities using Girvan-Newman with default options.

detect_hierarchical(graph)

Full hierarchical Girvan-Newman detection.

detect_with_options(graph, opts)

Detects communities using Girvan-Newman with custom options.

edge_betweenness(graph)

Calculates edge betweenness centrality for all edges.

Types

girvan_newman_options()

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

Options for Girvan-Newman algorithm

Functions

default_options()

@spec default_options() :: girvan_newman_options()

Returns default options for Girvan-Newman.

Defaults

target_communities: nil - Full dendrogram (all levels)

detect(graph)

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

Detects communities using Girvan-Newman with default options.

Returns the finest partition (most communities).

detect_hierarchical(graph)

@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(graph, opts)

@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(graph)

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