Girvan-Newman algorithm in Python
Repeatedly removes the edge of highest betweenness to split the graph into communities.
- File
girvan_newman_algorithm.py, 114 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/girvan-newman-algorithm/. The authors are listed in prov/G0RYGC.jsonl.
from collections import deque
from fractions import Fraction
def _components(n: int, adj: list[set[int]]) -> list[list[int]]:
seen = [False] * n
comps = []
for s in range(n):
if seen[s]:
continue
seen[s] = True
comp = [s]
queue = deque([s])
while queue:
u = queue.popleft()
for w in adj[u]:
if not seen[w]:
seen[w] = True
comp.append(w)
queue.append(w)
comps.append(sorted(comp))
return comps
def _modularity(n: int, edges: list[tuple[int, int]], part: list[list[int]]) -> Fraction:
m = len(edges)
if m == 0:
return Fraction(0)
label = [0] * n
for i, comp in enumerate(part):
for v in comp:
label[v] = i
inside = [0] * len(part)
degsum = [0] * len(part)
for u, v in edges:
degsum[label[u]] += 1
degsum[label[v]] += 1
if label[u] == label[v]:
inside[label[u]] += 1
return sum(
(Fraction(inside[i], m) - Fraction(degsum[i], 2 * m) ** 2 for i in range(len(part))),
Fraction(0),
)
def edge_betweenness(n: int, adj: list[set[int]]) -> dict[tuple[int, int], Fraction]:
"""Exact edge betweenness over unordered pairs, keyed by (u, v) with u < v."""
b = {(u, v): Fraction(0) for u in range(n) for v in adj[u] if u < v} # @line L10
for s in range(n): # @line L11
dist = [-1] * n # @line L12
sigma = [0] * n
dist[s] = 0
sigma[s] = 1
order = []
queue = deque([s])
while queue:
u = queue.popleft()
order.append(u)
for w in adj[u]:
if dist[w] < 0:
dist[w] = dist[u] + 1
queue.append(w)
if dist[w] == dist[u] + 1:
sigma[w] += sigma[u]
delta = [Fraction(0)] * n # @line L13
for w in reversed(order): # @line L14
for v in adj[w]: # @line L15
if dist[v] == dist[w] - 1:
c = Fraction(sigma[v], sigma[w]) * (1 + delta[w]) # @line L16
b[(min(v, w), max(v, w))] += c
delta[v] += c
for e in b: # @line L17
b[e] /= 2
return b # @line L18
def girvan_newman_algorithm(
n: int, edges: list[tuple[int, int]]
) -> tuple[list[list[int]], list[list[list[int]]]]:
"""Return (best, levels) for an undirected simple graph on 0 .. n-1.
levels lists the partitions into connected components seen while edges of
largest betweenness are removed one by one, ties broken by the smallest
(u, v) with u < v; best is the first level of largest modularity in the
original graph. Each partition is a sorted list of sorted lists.
Time O(m n (n + m)), extra space O(n + m) besides the levels.
"""
edges = sorted({(min(u, v), max(u, v)) for u, v in edges if u != v})
adj = [set() for _ in range(n)] # @line L1
for u, v in edges:
adj[u].add(v)
adj[v].add(u)
part = _components(n, adj)
levels = [part]
best, best_q = part, _modularity(n, edges, part)
remaining = len(edges)
while remaining > 0: # @line L2
b = edge_betweenness(n, adj) # @line L3
top = max(b.values()) # @line L4
u, v = min(e for e, x in b.items() if x == top)
adj[u].discard(v) # @line L5
adj[v].discard(u)
remaining -= 1
comps = _components(n, adj)
if len(comps) > len(part): # @line L6
part = comps # @line L7
levels.append(part)
q = _modularity(n, edges, part) # @line L8
if q > best_q:
best, best_q = part, q
return best, levels # @line L9
test_girvan_newman_algorithm.py 149 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/girvan-newman-algorithm/. The authors are listed in prov/G0RYGC.jsonl.
import random
from fractions import Fraction
from itertools import combinations
from girvan_newman_algorithm import edge_betweenness, girvan_newman_algorithm
def all_shortest_paths(n, edge_set, s, t):
"""Every shortest s-t path, by growing all simple paths level by level."""
if s == t:
return [[s]]
paths = [[s]]
for _ in range(n):
longer = []
for p in paths:
for w in range(n):
if w not in p and (min(p[-1], w), max(p[-1], w)) in edge_set:
longer.append(p + [w])
done = [p for p in longer if p[-1] == t]
if done:
return done
paths = longer
return []
def brute_betweenness(n, edges):
edge_set = set(edges)
b = {e: Fraction(0) for e in edges}
for s, t in combinations(range(n), 2):
paths = all_shortest_paths(n, edge_set, s, t)
for p in paths:
for x, y in zip(p, p[1:]):
b[(min(x, y), max(x, y))] += Fraction(1, len(paths))
return b
def brute_components(n, edges):
label = list(range(n))
changed = True
while changed:
changed = False
for u, v in edges:
low = min(label[u], label[v])
if label[u] != low or label[v] != low:
label[u] = label[v] = low
changed = True
groups = {}
for v in range(n):
groups.setdefault(label[v], []).append(v)
return sorted(sorted(g) for g in groups.values())
def brute_q(n, edges, part):
m = len(edges)
if m == 0:
return Fraction(0)
deg = [0] * n
for u, v in edges:
deg[u] += 1
deg[v] += 1
q = Fraction(0)
for c in part:
cs = set(c)
inside = sum(1 for u, v in edges if u in cs and v in cs)
q += Fraction(inside, m) - Fraction(sum(deg[v] for v in c), 2 * m) ** 2
return q
def reference(n, edges):
"""Girvan-Newman from the definitions: path enumeration, label components."""
current = sorted(edges)
part = brute_components(n, current)
levels = [part]
while current:
b = brute_betweenness(n, current)
top = max(b.values())
e = min(x for x in current if b[x] == top)
current.remove(e)
comps = brute_components(n, current)
if len(comps) > len(part):
part = comps
levels.append(part)
qs = [brute_q(n, edges, p) for p in levels]
return levels[qs.index(max(qs))], levels
def random_graph(rng, n, p):
return [(u, v) for u, v in combinations(range(n), 2) if rng.random() < p]
def test_example():
edges = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 4), (4, 5), (4, 6), (5, 6)]
adj = [set() for _ in range(7)]
for u, v in edges:
adj[u].add(v)
adj[v].add(u)
b = edge_betweenness(7, adj)
assert b[(3, 4)] == 12 and b[(1, 3)] == 6 and b[(4, 5)] == 5 and b[(0, 1)] == 3 and b[(1, 2)] == 1
best, levels = girvan_newman_algorithm(7, edges)
assert best == [[0, 1, 2, 3], [4, 5, 6]]
assert len(levels) == 7
assert levels[2] == [[0], [1, 2, 3], [4, 5, 6]]
assert brute_q(7, edges, best) == Fraction(59, 162)
def test_small_cases():
assert girvan_newman_algorithm(0, []) == ([], [[]])
assert girvan_newman_algorithm(1, []) == ([[0]], [[[0]]])
assert girvan_newman_algorithm(3, []) == ([[0], [1], [2]], [[[0], [1], [2]]])
best, levels = girvan_newman_algorithm(2, [(0, 1)])
assert levels == [[[0, 1]], [[0], [1]]] and best == [[0, 1]]
def test_random_against_reference():
rng = random.Random(20020611)
for _ in range(600):
n = rng.randint(1, 7)
edges = random_graph(rng, n, rng.choice([0.2, 0.4, 0.6, 0.9]))
adj = [set() for _ in range(n)]
for u, v in edges:
adj[u].add(v)
adj[v].add(u)
assert edge_betweenness(n, adj) == brute_betweenness(n, edges)
assert girvan_newman_algorithm(n, edges) == reference(n, edges)
def test_levels_are_nested():
rng = random.Random(7821)
for _ in range(200):
n = rng.randint(2, 12)
edges = random_graph(rng, n, 0.35)
best, levels = girvan_newman_algorithm(n, edges)
assert levels[-1] == [[v] for v in range(n)]
assert best in levels
for coarse, fine in zip(levels, levels[1:]):
assert len(fine) == len(coarse) + 1
for c in fine:
assert any(set(c) <= set(d) for d in coarse)
if __name__ == "__main__":
test_example()
test_small_cases()
test_random_against_reference()
test_levels_are_nested()
print("ok")
What the next level needs
- the tests did not run in this build