Girvan-Newman, in depth: edge betweenness by Brandes accumulation, the divisive loop, the dendrogram and choosing the cut by modularity

Why bridges carry the most shortest paths

The edge betweenness of an edge e is the number of shortest paths, over all pairs of nodes, that pass through e. When two shortest paths tie between a pair, each gets a fractional share, so a pair always contributes exactly 1 in total spread over its paths.

Why does this find community boundaries? Inside a dense group there are many routes between any two members, so traffic is spread over many edges. Between two groups joined by a few edges, every path from one side to the other must squeeze through those few edges. If a group of 50 nodes connects to another group of 50 through a single edge, that edge carries all 2,500 cross pairs. No internal edge comes close.

Degree-based scores fail here. A bridge edge often joins two ordinary, low-degree nodes. Its importance is global, not local, and only a measure that looks at every pair of nodes will notice it. That is also why the method is expensive: the global view costs a shortest-path search from every node.

Computing edge betweenness

Counting paths pair by pair would cost far too much. Ulrik Brandes showed in 2001 how to accumulate betweenness with one breadth-first search per source node, and the same idea works for edges. For a source s, run BFS and record three things for every node v: its distance from s, the number of shortest paths from s to v (call it sigma[v]), and its predecessors, the neighbours one step closer to s.

Then walk the nodes in reverse BFS order, farthest first. Each node w holds a dependency delta[w], the share of shortest paths from s that pass through w on the way to something farther out. For each predecessor v of w, the edge (v, w) gets credit sigma[v] / sigma[w] * (1 + delta[w]). The 1 counts the path that ends at w itself. The ratio splits the credit among predecessors in proportion to how many shortest paths come through each. That same credit is added to delta[v].

from collections import deque, defaultdict

def edge_betweenness(adj):
    # adj: dict node -> set of neighbours, undirected, unweighted
    score = defaultdict(float)
    for s in adj:
        order, preds = [], {v: [] for v in adj}
        sigma = dict.fromkeys(adj, 0); sigma[s] = 1
        dist = dict.fromkeys(adj, -1); dist[s] = 0
        q = deque([s])
        while q:                                  # forward pass: BFS
            v = q.popleft(); order.append(v)
            for w in adj[v]:
                if dist[w] < 0:
                    dist[w] = dist[v] + 1; q.append(w)
                if dist[w] == dist[v] + 1:
                    sigma[w] += sigma[v]; preds[w].append(v)
        delta = dict.fromkeys(adj, 0.0)
        while order:                              # backward pass: accumulate
            w = order.pop()
            for v in preds[w]:
                credit = sigma[v] / sigma[w] * (1 + delta[w])
                score[frozenset((v, w))] += credit
                delta[v] += credit
    # every unordered pair was counted once from each end
    return {tuple(sorted(e)): x / 2 for e, x in score.items()}

The final division by 2 matters. In an undirected graph the pair (a, b) is counted once from source a and once from source b. Forgetting the halving does not change which edge is removed, but it makes your numbers disagree with every library and paper. Each source costs O(n + m), so a full pass costs O(nm). With edge weights, replace BFS with Dijkstra and the pass costs O(nm + n^2 log n).

The divisive loop

The full algorithm is short:

1. Compute edge betweenness for every edge.
2. Remove the edge with the highest score.
3. If the number of connected components went up, record the new partition as a level of the dendrogram and score it.
4. Recompute betweenness and repeat until no edges remain, or until you have the level you need.

Step 4 is the one people get wrong. You must recompute after every removal. Once a bridge is gone, the paths it carried take other routes, and an edge that looked ordinary can become the new bottleneck. Removing the top ten edges from one ranking is a different and worse algorithm. Girvan and Newman single out the recalculation as the step that makes the method work.

Recomputing is cheaper than it sounds. Removing an edge only changes shortest paths inside the component that contained it, so you only need to recompute that component. Paths never cross between components. Here is the loop in that form:

def girvan_newman_levels(adj):
    adj = {v: set(ns) for v, ns in adj.items()}
    comps = components(adj)
    yield [set(c) for c in comps]
    while any(adj[v] for v in adj):
        # find the component that holds the single best edge
        best, best_comp = None, None
        for comp in comps:
            sub = {v: adj[v] for v in comp}
            for e, x in edge_betweenness(sub).items():
                if best is None or x > best[1]:
                    best, best_comp = (e, x), comp
        (a, b), _ = best
        adj[a].discard(b); adj[b].discard(a)
        new = components({v: adj[v] for v in best_comp})
        if len(new) > 1:
            comps = [c for c in comps if c is not best_comp] + new
            yield [set(c) for c in comps]

This version still recomputes every component on each round, for clarity. In production, cache each component's scores and recompute only the component that just lost an edge. When a graph has split into many pieces, that saves most of the work. In Python, networkx.algorithms.community.girvan_newman(G) yields the same sequence of partitions as tuples of node sets. Its most_valuable_edge argument lets you plug in a weighted or approximate scoring function.

Worked example: seven nodes

Take seven nodes and nine edges. Group A is nodes 0, 1, 2 and 3, with edges 0-1, 0-2, 1-2, 1-3 and 2-3. Group B is the triangle 4-5, 4-6, 5-6. A single edge, 3-4, joins them. The betweenness values below come from running the code above, not from estimates.

Round one removes 3-4. The graph splits into {0, 1, 2, 3} and {4, 5, 6}. Modularity rises from 0 for the single community to 0.364 for this split.

Round two recomputes inside A only. Now edges 0-1, 0-2, 1-3 and 2-3 all tie at 1.5, and 1-2 scores 1. A has a symmetric diamond shape, so no edge is a clear bridge. Whichever of the tied edges you remove, A does not split, because a cycle remains. The next partition only appears after more removals, and every finer partition scores lower. For example, {0, 1, 2}, {3}, {4, 5, 6} scores 0.290. The algorithm has nothing more to say, and that is the right answer: there are two communities.

The example also shows the tie problem. With four edges tied at 1.5, the order you remove them depends on dictionary order or node labels. Make tie-breaking explicit. Either remove all tied edges together, as some implementations do, or break ties by a stable key such as the sorted node IDs. That way two runs on the same graph give the same dendrogram.

Choosing where to cut

The dendrogram holds every partition from one community down to n singletons. You have to pick one. The standard rule is to pick the level with the highest modularity Q. Q compares the fraction of edges inside communities with the fraction you would expect if edges were rewired at random while keeping every node's degree. Modularity, defined and derived explains the formula and its known blind spots.

Compute Q against the original graph, not against the graph with edges removed. The removed edges are evidence about structure, and once removed they would otherwise vanish from the score. In the example, the two-community level scores 0.364 against the original nine edges.

def modularity(orig_edges, degree, communities):
    m = len(orig_edges)
    label = {v: i for i, comm in enumerate(communities) for v in comm}
    inside = defaultdict(int); deg_sum = defaultdict(int)
    for a, b in orig_edges:
        if label[a] == label[b]:
            inside[label[a]] += 1
    for v, d in degree.items():
        deg_sum[label[v]] += d
    return sum(inside[k] / m - (deg_sum[k] / (2 * m)) ** 2 for k in deg_sum)

# E: original edge list, deg: original degrees, components(): BFS labelling
best = max(girvan_newman_levels(adj), key=lambda part: modularity(E, deg, part))

There are two other ways to stop. If the domain fixes the number of groups, say two factions or k departments, stop at the first level with k components. If you only need the top of the hierarchy, stop once Q has fallen well below its best value for several levels in a row. Q usually rises, peaks and then falls, so you rarely need the full dendrogram. Early stopping can cut the run time by a large factor.

Cost and how to reduce it

Each round costs one betweenness pass, O(nm). There can be up to m rounds. The worst case is O(m^2 n), which is O(n^3) on a sparse graph where m grows like n. In practice that means a few thousand nodes in Python, and perhaps tens of thousands in compiled code with component caching. Beyond that, the method is too slow.

Sampling sources is the most effective speed-up. Betweenness from a few hundred random sources ranks clear bridges correctly almost every time. It is noisy for nearly tied edges, but those are exactly the edges whose removal order matters least. If you sample, fix the random seed so the dendrogram is reproducible.

Failure modes

These are the problems that show up in practice:

• No recompute. Removing several edges from one ranking. The result looks plausible but differs from the real algorithm. Test your loop on a small graph against networkx.
• Weights read the wrong way. Shortest-path weights are distances. If your weights mean strength, such as message counts, convert them first, for example to 1 / w. Otherwise the strongest ties will look like the longest paths and get cut first.
• Modularity's resolution limit. In large graphs, maximising Q can merge small, real communities into bigger ones. If you expect many small groups, check the levels below the best Q as well.
• Nondeterminism. Ties broken by hash order give different dendrograms on different runs or Python versions. Break ties by a stable key.

Trade-offs and alternatives

Choose Girvan-Newman when the graph is small, when you want the whole hierarchy and not just one partition, or when the bridge edges matter in their own right. Examples are finding the links whose failure would split a network, or explaining to a reader why two groups count as separate. The removed edges are the explanation.

Choose something else at scale. Louvain optimises modularity greedily and runs in close to linear time on sparse graphs. Leiden fixes Louvain's badly connected communities. Label propagation is faster still, but gives less stable results. A common workflow is to use Louvain or Leiden for the production partition, then run Girvan-Newman inside one community of interest to see its internal structure and the edges that hold it together.

One more point about the BFS at the core: the forward pass is ordinary breadth-first search with path counting. If BFS layers and predecessor lists are not yet second nature, BFS and DFS in depth is worth reading first, because almost every bug in a betweenness implementation is a BFS bug.

What to do next

1. Implement edge_betweenness and check it on the seven-node example: the bridge must score 12, and edges 1-2 and 5-6 must score 1.
2. Compare your scores with networkx.edge_betweenness_centrality(G, normalized=False) on a few random graphs.
3. Add the divisive loop with per-component recomputation and a stable tie-break.
4. Score each level with modularity against the original edges, and keep the best one.
5. Time it at 1,000, 2,000 and 4,000 nodes to see the growth. Then decide on source sampling or a switch to Leiden before your real graph grows past that.
6. Look at the list of removed edges, not just the communities. They are often the result that matters.