The Newman-Girvan Algorithm

The Core Idea

The Newman-Girvan algorithm is a divisive (top-down) community-detection method. It starts with a single connected component and progressively splits it into separate communities by removing edges that act as bridges between them. The algorithm identifies these bridges using edge betweenness centrality: edges that lie on many shortest paths are likely to be community boundaries.

The key structure is a dendrogram: as edges are removed, the algorithm builds a tree showing how the graph splits into progressively smaller communities.

The Critical Rule

Recalculate edge betweenness for every single edge after every single edge removal. Never remove multiple edges before recalculating. Removing one edge changes the shortest paths in the graph, which changes the betweenness of every remaining edge. Failing to recalculate produces wrong results.

Algorithm Steps

1. Compute edge betweenness centrality for all edges in the graph.
2. Remove the edge with the highest betweenness (it is the most likely bridge between communities).
3. Recalculate edge betweenness for all remaining edges.
4. Repeat until the desired number of connected components is reached, or until the graph is fully fragmented.

Why Edge Betweenness Works

Edges connecting different communities necessarily lie on many shortest paths because they are the only way to travel between those communities. Within a dense cluster, there are many alternative paths, so no single edge dominates. Between communities, every path must pass through one of a small number of connecting edges, giving them very high betweenness.

Removing the highest-betweenness edge repeatedly peels apart the community structure.

The Dendrogram Output

The algorithm does not produce a single “best” partition; it produces a hierarchy of partitions. Each horizontal cut through the dendrogram corresponds to a different number of communities. Choosing the cut point requires an additional criterion (e.g. stopping when modularity peaks, or specifying the desired number of components).

Worked Example: 2025 Q8 Graph

Consider the graph: A-B, A-E, B-C, B-F, C-D, C-F, D-F, D-H, F-G, G-H.

First Iteration: Compute All Edge Betweenness

Edge betweenness is computed by counting, for each edge, the number of (source, target) pairs whose shortest path passes through that edge. For undirected graphs, halve all scores at the end because each path s→t is also counted as t→s.

In the initial graph, edge D-H has high betweenness: it is the only connection between H and the main cluster. Many shortest paths between {A,B,C,D,E,F,G} and {H} must pass through D-H. Similarly, edge G-H is the other route to H (via F-G), so D-H and G-H share the load, but D-H connects to the more central D node and is likely the highest.

Other edges within the dense A-B-C-D-F clique have relatively low betweenness (many alternative routes). Edge A-E: E is a leaf, so ALL paths involving E go through A-E, giving it moderate betweenness.

First Removal

Remove D-H (highest betweenness). Graph now has two components: {A,B,C,D,E,F,G} and {H}.

Second Iteration: Recalculate

After removing D-H, all paths to H must now go through G-H. Edge G-H’s betweenness increases dramatically. Edge F-G now carries all traffic to both G and H, so F-G’s betweenness also increases. The edges around the dense core redistribute as paths that previously used D-H are rerouted.

Second Removal

Remove the new highest-betweenness edge (likely G-H or F-G). Continue until the desired number of components.

2025 Q8g Model Answer

The Newman-Girvan algorithm breaks the graph into connected clusters. The answer expected: state that it iteratively computes edge betweenness, removes the highest-scoring edge, and recalculates. Two marks: one for naming the algorithm, one for describing the process correctly.

Summary

Step	Detail
1	Compute edge betweenness for all edges
2	Remove edge with highest betweenness
3	Recalculate edge betweenness for all remaining edges
4	Repeat until desired number of components
Approach	Divisive (top-down): start with one component, split repeatedly
Output	Dendrogram (hierarchy of partitions)
Principle	High-betweenness edges are bridges between communities

Past paper questions: y2025p3q8g, y2020p3q9