Girvan-Newman Algorithm

A Bit of History

Michelle Girvan and Mark Newman introduced the method in their 2002 paper “Community Structure in Social and Biological Networks.” Their shift in viewpoint was elegant: instead of assembling communities from similar vertices, repeatedly cut the connections that appear to carry the most traffic between regions of the network.

What Does “Community” Mean?

Informally, a community has many connections inside itself and comparatively few connections to other groups. That definition describes a pattern, not a unique object: the same network may have teams, departments, and divisions at different scales. Girvan–Newman therefore produces a sequence of candidate partitions rather than requiring the number of communities in advance.

Edge Betweenness: Counting Shortest-Path Traffic

For an undirected edge $e$, edge betweenness centrality is

$$C_B(e)=\sum_{s<t}\frac{\sigma_{st}(e)}{\sigma_{st}},$$

where $\sigma_{st}$ is the number of shortest paths between $s$ and $t$, and $\sigma_{st}(e)$ counts those using $e$. When several equally short paths exist, the pair contributes fractionally instead of giving every route a full vote.

The Divisive Pipeline

1. Measure. Compute every current edge's betweenness with Brandes' dependency-accumulation method.
2. Remove. Delete one maximum-betweenness edge. A deterministic endpoint order makes ties reproducible; another valid policy removes all tied maxima as one batch.
3. Inspect. Recompute connected components. When their count increases, record the new partition as another level in the hierarchy.
4. Score. Evaluate that partition—commonly with modularity measured against the original, intact graph—and remember the best level encountered.
5. Repeat. Recalculate betweenness on the modified graph before choosing the next edge. Stop at the desired number of groups or when no edges remain.

A Bridge Between Two Dense Groups

The graph below contains two four-vertex cliques joined only by edge $DE$. Each of the $4\times4=16$ cross-group vertex pairs must use $DE$, so that edge alone receives 16 units of betweenness from those pairs. Inside either clique, traffic can spread across many alternatives.

Why Must Betweenness Be Recomputed?

Removing an edge changes the set of shortest paths. Some routes disappear, tied routes may become unique, and traffic can be redirected onto edges that previously looked ordinary. Reusing the first betweenness ranking would describe the old graph, not the current one.

Selecting a Level with Modularity

Edge removal creates a hierarchy, but it does not say which level is best. For a partition into communities $C$, unweighted modularity can be written

$$Q=\sum_C\left[\frac{m_C}{m}-\left(\frac{K_C}{2m}\right)^2\right],$$

where $m$ is the number of edges in the original graph, $m_C$ is the number of original edges internal to $C$, and $K_C$ is the sum of original degrees in $C$. The first term rewards internal edges; the second subtracts what a degree-preserving random baseline would predict.

For the two-clique example, $m=13$. Each side contains six internal edges and has degree sum 13, giving $Q=2[6/13-(13/26)^2]\approx0.423$ after removing the bridge.

What Does the Heuristic Actually Guarantee?

Brandes' calculation gives the exact edge-betweenness values for the current graph, and the chosen tie policy gives a reproducible removal hierarchy. What is not guaranteed is recovery of a unique ground-truth community structure or the globally maximum-modularity partition.

The bridge intuition is strongest when groups are internally well connected and have few links between them. A high-betweenness edge can instead be an internal bottleneck, and modularity itself has known scale limitations. Treat the output as an interpretable structural hypothesis to examine, not an oracle.

Complexity Analysis

For positively weighted graphs, the Brandes stage replaces BFS with Dijkstra, increasing each full centrality computation. Removing tied edges in batches, stopping after a target number of communities, or recomputing only affected regions can reduce practical work, but the classic algorithm remains best suited to small and medium exploratory networks.

Implementation

The Python reference below completes the whole workflow: exact unweighted edge betweenness, deterministic one-edge removals, hierarchy snapshots, and modularity against the original graph. The C++ and Java panels implement the same Brandes kernel used inside each iteration.

from collections import defaultdict, deque

def connected_components(adj):
    seen, groups = set(), []
    for start in range(len(adj)):
        if start in seen:
            continue
        stack, component = [start], []
        seen.add(start)
        while stack:
            u = stack.pop()
            component.append(u)
            for v in sorted(adj[u], reverse=True):
                if v not in seen:
                    seen.add(v)
                    stack.append(v)
        groups.append(tuple(sorted(component)))
    return tuple(sorted(groups))

def edge_betweenness(adj):
    """Unnormalized Brandes edge betweenness for a simple undirected graph."""
    n = len(adj)
    score = defaultdict(float)
    for source in range(n):
        predecessors = [[] for _ in range(n)]
        distance = [-1] * n
        path_count = [0] * n
        distance[source], path_count[source] = 0, 1
        order, queue = [], deque([source])

        while queue:
            u = queue.popleft()
            order.append(u)
            for v in sorted(adj[u]):
                if distance[v] < 0:
                    distance[v] = distance[u] + 1
                    queue.append(v)
                if distance[v] == distance[u] + 1:
                    path_count[v] += path_count[u]
                    predecessors[v].append(u)

        dependency = [0.0] * n
        for v in reversed(order):
            for u in predecessors[v]:
                share = (path_count[u] / path_count[v]) * (1.0 + dependency[v])
                score[min(u, v), max(u, v)] += share
                dependency[u] += share

    return {edge: value / 2.0 for edge, value in score.items()}

def modularity(n, original_edges, partition):
    """Score a partition against the original unweighted graph."""
    m = len(original_edges)
    if m == 0:
        return 0.0
    degree = [0] * n
    for u, v in original_edges:
        degree[u] += 1
        degree[v] += 1

    quality = 0.0
    for vertices in partition:
        community = set(vertices)
        internal = sum(u in community and v in community for u, v in original_edges)
        degree_sum = sum(degree[v] for v in community)
        quality += internal / m - (degree_sum / (2 * m)) ** 2
    return quality

def girvan_newman(n, edges):
    """Return deterministic removals, split levels, and the best modularity level."""
    if n < 0:
        raise ValueError("n must be nonnegative")
    original = set()
    for u, v in edges:
        if not (0 <= u < n and 0 <= v < n):
            raise ValueError("edge endpoint outside 0..n-1")
        if u != v:
            original.add((min(u, v), max(u, v)))
    original = tuple(sorted(original))

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

    partition = connected_components(adj)
    levels = [(partition, modularity(n, original, partition), None)]
    removal_order = []
    previous_count = len(partition)

    while any(adj):
        scores = edge_betweenness(adj)
        maximum = max(scores.values())
        tied = [edge for edge, value in scores.items()
                if abs(value - maximum) <= 1e-12]
        removed = min(tied)
        u, v = removed
        adj[u].remove(v)
        adj[v].remove(u)
        removal_order.append((removed, maximum))

        partition = connected_components(adj)
        if len(partition) > previous_count:
            levels.append((partition, modularity(n, original, partition), removed))
            previous_count = len(partition)

    best = max(levels, key=lambda level: (level[1], -len(level[0])))
    return {"removals": removal_order, "levels": levels, "best": best}


edges = [(0,1), (1,2), (2,0), (2,3), (3,4), (4,5), (5,3)]
result = girvan_newman(6, edges)
print("first removed:", result["removals"][0])  # ((2, 3), 9.0)
print("best partition:", result["best"][:2])    # two triangles, Q ≈ 0.357

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

map<pair<int,int>, double> edgeBetweenness(
        const vector<vector<int>>& adj) {
    int n = static_cast<int>(adj.size());
    map<pair<int,int>, double> betweenness;

    for (int s = 0; s < n; s++) {
        vector<int> dist(n, -1), order;
        vector<double> numPaths(n, 0.0);
        vector<vector<int>> preds(n);
        dist[s] = 0; numPaths[s] = 1.0;
        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 = static_cast<int>(order.size()) - 1; i >= 0; i--) {
            int w = order[i];
            for (int v : preds[w]) {
                double share = (numPaths[v] / numPaths[w]) * (1.0 + 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(adj);
    auto bridge = max_element(bc.begin(), bc.end(),
        [](const auto& a, const auto& b) { return a.second < b.second; });
    cout << bridge->first.first << "-" << bridge->first.second
         << ": " << bridge->second << '\n'; // 2-3: 9
}

import java.util.*;

class GirvanNewman {
    record Edge(int u, int v) {
        static Edge of(int a, int b) {
            return new Edge(Math.min(a, b), Math.max(a, b));
        }
    }

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

        for (int s = 0; s < n; s++) {
            int[] dist = new int[n];
            double[] numPaths = new double[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.0;
            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 = (numPaths[v] / numPaths[w]) * (1.0 + dependency[w]);
                    betweenness.merge(Edge.of(v, w), 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]); }
        Map<Edge, Double> scores = edgeBetweenness(adj);
        Map.Entry<Edge, Double> bridge = scores.entrySet().stream()
            .max(Map.Entry.comparingByValue()).orElseThrow();
        System.out.println(bridge.getKey() + ": " + bridge.getValue()); // Edge[u=2,v=3]: 9.0
    }
}

How It Compares with Other Community Methods

Where the Method Is Useful

Pitfalls and Edge Cases

Exercises