Girvan-Newman algorithm

The Girvan-Newman algorithm is a divisive method for detecting community structure in networks. Developed by Michelle Girvan and Mark Newman in 2002, it uses the concept of betweenness centrality to identify and progressively remove the edges that most connect communities. The algorithm operates by computing the betweenness centrality of every edge in the network, removing the edge with the highest score, and repeating the process until the network is decomposed into isolated components. The sequence of removals produces a dendrogram that reveals the hierarchical community structure.

The insight behind the algorithm is that edges connecting communities have high betweenness centrality because they lie on many of the shortest paths between nodes in different communities. By removing these edges first, the algorithm naturally separates the network into its constituent clusters. The approach has been influential in network science and computational sociology, though it is computationally expensive for large networks and has been superseded by faster methods such as the Louvain algorithm and Leiden algorithm for many applications.