Effect of Edge Edits on Betweenness Centrality

The 2025 Q8e Scenario

Starting from the A-H graph (A-B, A-E, B-C, B-F, C-D, C-F, D-F, D-H, F-G, G-H), two edits are applied:

1. Remove edge D-H
2. Add edge C-E

The question asks: how do these changes affect the betweenness centrality of nodes C, H, and E?

Effect of Removing D-H

Before removal, H connects to the main cluster via two paths: D-H (through D) and G-H (through G, then F, then C or D). After removing D-H, H can only connect via G.

Impact on $C_B(H)$

H becomes a leaf node relative to the main cluster (connected only through G). No shortest paths between other pairs of nodes pass through H: the only nodes that need H in their paths are paths whose source or target is H itself. Since betweenness excludes source and target nodes ($s \neq v \neq t$), $C_B(H)$ decreases dramatically. It may drop to zero (no path passes through H as an intermediate node).

Impact on $C_B(G)$

All traffic to and from H now must go through G (and then F). This increases $C_B(G)$: G now lies on all paths between H and any other node in the main cluster.

Impact on $C_B(F)$

F also gains betweenness because it is on the only route from H to the rest of the graph (via G→F).

Effect of Adding C-E

Before addition, E was a leaf connected only to A. All paths involving E (as source or target) had to go through A, and all paths where E is an intermediate node were impossible.

Impact on $C_B(E)$

E gains a second neighbour (C), so it is no longer a leaf. E can now lie on shortest paths between A and D (via E→C→D), or between A and other nodes reachable through C. $C_B(E)$ increases from zero to a small positive value: E becomes an intermediate node on some paths between A’s side and C’s side.

Impact on $C_B(A)$

Some paths that previously had to go through A (because E only connected through A) are now rerouted through C-E. For example, a path from E to C previously went E→A→B→C. Now E→C directly is a shorter path, so it no longer passes through A. $C_B(A)$ decreases: some of A’s betweenness is redistributed to C and E.

Impact on $C_B(C)$

C becomes an intermediary for E’s paths to the rest of the graph. Paths from E to D, F, G, H can now go E→C→D or E→C→F instead of E→A→B→C→D. $C_B(C)$ increases: C gains betweenness from its new role as a connector for E.

The General Principle

Adding edges creates alternative shortest paths, which redistributes betweenness. Existing intermediaries lose traffic (their betweenness decreases) because some paths are shortened via the new edge. The nodes incident to the new edge gain traffic (their betweenness increases). The total “amount” of betweenness in the graph is conserved in the sense that it shifts from old routes to new ones.

Summary

Edit	Node	Effect on $C_B$	Reason
Remove D-H	H	Decreases (to 0)	Becomes a leaf; no paths pass through it
Remove D-H	G	Increases	All H→main-cluster traffic now goes through G
Add C-E	A	Decreases	Some E-paths reroute via C, bypassing A
Add C-E	C	Increases	Becomes an intermediary for E-paths
Add C-E	E	Increases (from 0)	Gains a second neighbour; lies on new paths

Past paper questions: y2025p3q8e