Idea
Edges BETWEEN communities have high betweenness (many shortest paths cross them). Removing them isolates communities.
Advertisement
Algorithm
1. Compute edge betweenness. 2. Remove highest. 3. Recompute. 4. Repeat until desired granularity or graph disconnects.
Advertisement
Complexity
O(E² V) per removal. Massive for large graphs. Practical up to ~10k nodes.
Dendrogram
Sequence of splits forms tree. Choose cut level via modularity peak or domain knowledge.