girvan_newman

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 with highest betweenness
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

import yog
import yog/community/girvan_newman as gn

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

// Basic usage - returns finest partition
let communities = gn.detect(graph)

// With options - target specific number of communities
let options = gn.GirvanNewmanOptions(target_communities: Some(2))
let communities = gn.detect_with_options(graph, options)

// Full hierarchical detection
let dendrogram = gn.detect_hierarchical(graph, zero: 0, add: int.add, compare: int.compare)

References

Types

GirvanNewmanOptions

</>

Options for Girvan-Newman algorithm.

pub type GirvanNewmanOptions {
  GirvanNewmanOptions(target_communities: option.Option(Int))
}

Constructors

```
GirvanNewmanOptions(target_communities: option.Option(Int))
```
Arguments

target_communities

Stop when this many communities found (None = full dendrogram)

Values

default_options

</>

pub fn default_options() -> GirvanNewmanOptions

Default options for Girvan-Newman.

detect

</>

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

Detects communities using the Girvan-Newman algorithm with default options.

Returns the community structure at the finest level (most communities). For the full hierarchy, use detect_hierarchical.

detect_hierarchical

</>

pub fn detect_hierarchical(
  graph: model.Graph(n, e),
  zero zero: e,
  add add: fn(e, e) -> e,
  compare compare: fn(e, e) -> order.Order,
) -> community.Dendrogram

Full hierarchical Girvan-Newman detection.

detect_with_options

</>

pub fn detect_with_options(
  graph: model.Graph(n, Int),
  options: GirvanNewmanOptions,
) -> Result(community.Communities, String)

Detects communities using the Girvan-Newman algorithm with custom options.

edge_betweenness

</>

pub fn edge_betweenness(
  graph: model.Graph(n, e),
  zero: e,
  add: fn(e, e) -> e,
  compare: fn(e, e) -> order.Order,
) -> dict.Dict(#(Int, Int), Float)