Girvan-Newman Algorithm

A Bit of History

Michelle Girvan and Mark Newman published "Community Structure in Social and Biological Networks" in 2002, introducing an elegantly simple "divisive" strategy for community detection: rather than trying to build communities up from scratch, progressively tear the network apart along its weakest structural links. The paper became one of the most cited works in the emerging field of network science, directly building on the betweenness centrality concept from Part 25.

Working Principle

The algorithm repeatedly removes the single edge with the highest edge betweenness centrality — the fraction of all-pairs shortest paths passing through that edge — recomputing betweenness after each removal:

1. Compute the edge betweenness centrality of every edge in the current graph (how many shortest paths, across all vertex pairs, pass through it).
2. Remove the single edge with the highest betweenness.
3. Recompute edge betweenness for the remaining graph (removing an edge changes many shortest paths, so betweenness values must be recalculated, not simply reused).
4. Repeat until no edges remain, tracking the network's connected-component structure after every removal — the community structure existing at whichever stage maximizes modularity (the same quality measure introduced alongside Part 25's Louvain method deep dive) is typically chosen as the final community partition.

Worked Example

Consider two dense triangles connected by a single "bridge" edge. Every shortest path between a vertex in the first triangle and a vertex in the second triangle must cross that bridge edge — giving it an overwhelmingly higher edge betweenness than any edge purely within either triangle. Removing it on the very first iteration immediately splits the graph into its two obvious, intuitively correct communities — precisely the outcome the algorithm was designed to produce, and a clean illustration of why "remove the highest-betweenness edge" targets exactly the inter-community connections.

Why Edge Betweenness Finds Bridges

Edges connecting two otherwise well-separated dense clusters are disproportionately likely to lie on shortest paths between every pair of vertices straddling the two clusters — simply because there are comparatively few alternative routes between the clusters at all. This makes edge betweenness a naturally good proxy for "how much would removing this edge disconnect distinct communities," even though the algorithm never explicitly reasons about communities directly — it only ever measures and removes based on the purely local (though globally computed) betweenness quantity.

Complexity Analysis

Computing edge betweenness for the whole graph once (using an efficient algorithm, such as Newman's own fast betweenness computation method) costs \(O(VE)\), and the algorithm recomputes it after every one of the \(E\) edge removals:

$$\text{Time: } O(V E^2)$$

This is notably expensive for large graphs compared to the Louvain method's near-linear complexity, making Girvan-Newman most practical on small-to-medium networks, or as a conceptually clear teaching example of divisive community detection rather than a large-scale production tool.

Implementation

from collections import deque, defaultdict

def edge_betweenness(n, adj):
    """Brute-force edge betweenness via BFS shortest-path counting from every source."""
    betweenness = defaultdict(float)

    for s in range(n):
        # BFS to find shortest-path distances and counts (Brandes'-style single-source pass)
        dist = [-1] * n
        num_paths = [0] * n
        dist[s], num_paths[s] = 0, 1
        order = []
        preds = defaultdict(list)
        q = deque([s])
        while q:
            v = q.popleft()
            order.append(v)
            for w in adj[v]:
                if dist[w] == -1:
                    dist[w] = dist[v] + 1
                    q.append(w)
                if dist[w] == dist[v] + 1:
                    num_paths[w] += num_paths[v]
                    preds[w].append(v)

        # Back-propagate dependency scores to accumulate edge betweenness
        dependency = [0.0] * n
        for w in reversed(order):
            for v in preds[w]:
                share = (num_paths[v] / num_paths[w]) * (1 + dependency[w])
                edge = tuple(sorted((v, w)))
                betweenness[edge] += share
                dependency[v] += share

    for edge in betweenness:
        betweenness[edge] /= 2  # each shortest path counted from both endpoints
    return betweenness

def girvan_newman(n, edges):
    adj = [set() for _ in range(n)]
    for u, v in edges:
        adj[u].add(v)
        adj[v].add(u)

    remaining = set(tuple(sorted(e)) for e in edges)
    removal_order = []

    while remaining:
        bc = edge_betweenness(n, adj)
        # Only consider edges still present
        bc = {e: b for e, b in bc.items() if e in remaining}
        if not bc:
            break
        edge_to_remove = max(bc, key=bc.get)
        u, v = edge_to_remove
        adj[u].discard(v)
        adj[v].discard(u)
        remaining.discard(edge_to_remove)
        removal_order.append(edge_to_remove)

    return removal_order

edges = [(0,1),(1,2),(2,0),(2,3),(3,4),(4,5),(5,3)]  # two triangles joined by a bridge
print(girvan_newman(6, edges))

// Simplified sketch: full Brandes'-style betweenness computation (shown in the
// Python panel) is the standard approach; C++ production code typically follows
// the same BFS + dependency-accumulation structure per source vertex.
#include <vector>
#include <queue>
#include <map>
#include <iostream>
using namespace std;

map<pair<int,int>, double> edgeBetweenness(int n, vector<vector<int>>& adj) {
    map<pair<int,int>, double> betweenness;

    for (int s = 0; s < n; s++) {
        vector<int> dist(n, -1), numPaths(n, 0), order;
        vector<vector<int>> preds(n);
        dist[s] = 0; numPaths[s] = 1;
        queue<int> q; q.push(s);
        while (!q.empty()) {
            int v = q.front(); q.pop();
            order.push_back(v);
            for (int w : adj[v]) {
                if (dist[w] == -1) { dist[w] = dist[v] + 1; q.push(w); }
                if (dist[w] == dist[v] + 1) { numPaths[w] += numPaths[v]; preds[w].push_back(v); }
            }
        }

        vector<double> dependency(n, 0.0);
        for (int i = order.size() - 1; i >= 0; i--) {
            int w = order[i];
            for (int v : preds[w]) {
                double share = ((double)numPaths[v] / numPaths[w]) * (1 + dependency[w]);
                auto edge = minmax(v, w);
                betweenness[edge] += share;
                dependency[v] += share;
            }
        }
    }
    for (auto& [edge, val] : betweenness) val /= 2;
    return betweenness;
}

int main() {
    int n = 6;
    vector<vector<int>> adj(n);
    vector<pair<int,int>> edges = {{0,1},{1,2},{2,0},{2,3},{3,4},{4,5},{5,3}};
    for (auto& [u, v] : edges) { adj[u].push_back(v); adj[v].push_back(u); }
    auto bc = edgeBetweenness(n, adj);
    for (auto& [edge, val] : bc) cout << "(" << edge.first << "," << edge.second << "): " << val << endl;
    return 0;
}

import java.util.*;

class GirvanNewman {
    static Map<List<Integer>, Double> edgeBetweenness(int n, List<List<Integer>> adj) {
        Map<List<Integer>, Double> betweenness = new HashMap<>();

        for (int s = 0; s < n; s++) {
            int[] dist = new int[n], numPaths = new int[n];
            Arrays.fill(dist, -1);
            List<Integer> order = new ArrayList<>();
            List<List<Integer>> preds = new ArrayList<>();
            for (int i = 0; i < n; i++) preds.add(new ArrayList<>());
            dist[s] = 0; numPaths[s] = 1;
            Deque<Integer> q = new ArrayDeque<>();
            q.add(s);
            while (!q.isEmpty()) {
                int v = q.poll();
                order.add(v);
                for (int w : adj.get(v)) {
                    if (dist[w] == -1) { dist[w] = dist[v] + 1; q.add(w); }
                    if (dist[w] == dist[v] + 1) { numPaths[w] += numPaths[v]; preds.get(w).add(v); }
                }
            }

            double[] dependency = new double[n];
            for (int i = order.size() - 1; i >= 0; i--) {
                int w = order.get(i);
                for (int v : preds.get(w)) {
                    double share = ((double) numPaths[v] / numPaths[w]) * (1 + dependency[w]);
                    List<Integer> edge = Arrays.asList(Math.min(v, w), Math.max(v, w));
                    betweenness.merge(edge, share, Double::sum);
                    dependency[v] += share;
                }
            }
        }
        betweenness.replaceAll((k, v) -> v / 2);
        return betweenness;
    }

    public static void main(String[] args) {
        int n = 6;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        int[][] edges = {{0,1},{1,2},{2,0},{2,3},{3,4},{4,5},{5,3}};
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        System.out.println(edgeBetweenness(n, adj));
    }
}

Real-World Applications

Exercises

1. Trace through the worked example (two triangles joined by a bridge) by hand, confirming the bridge edge has the highest betweenness among all edges.
2. Explain why edge betweenness must be recomputed after every single edge removal, rather than computed once and reused — what specifically changes after a removal?
3. Compare Girvan-Newman's "remove edges" strategy to the Louvain method's "move vertices between groups" strategy — which is naturally faster on very large networks, and why?
4. Challenge: Modify the implementation to also compute modularity at each stage of edge removal, and identify the removal stage achieving the highest modularity (the algorithm's typical stopping criterion).

Limitations