Girvan-Newman Algorithm

This lecture covers the Girvan-Newman Algorithm for divisive community detection, which decomposes a network based on edge betweenness. The algorithm repeats edge removal based on betweenness until no edges are left, resulting in a hierarchical network decomposition. It explains edge betweenness as the fraction of shortest paths passing over an edge, and demonstrates the computation of betweenness and edge flow. Sample results from physics collaborations and Zachary's Karate club are presented, showcasing the algorithm's application. The lecture also includes an algorithm for computing betweenness, path counting, and edge flow distribution. Finally, it challenges the audience with questions on edge betweenness and path counts in a network.