yog/community/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

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

When to Use

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,
  with_zero: 0,
  with_add: int.add,
  with_compare: int.compare
)

References

• Girvan & Newman 2002 - Community structure in social networks
• Wikipedia: Girvan-Newman Algorithm

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

pub fn default_options() -> GirvanNewmanOptions

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

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

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

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