View source for 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.

[[Category:Network Science]] [[Category:Algorithms]]