Girvan-Newman Algorithm Improvement — Part 3
Lydia Malone is a second-year Computer Science student at Southern Methodist University.
For our implementation of the Girvan-Newman algorithm, in order to determine the edge with the highest betweenness value at each iteration, we used the breadth first search function to create a spanning tree from each vertex to every other vertex. This allowed us to determine which edge had the highest number of shortest paths running through it, and thus, which edge to eliminate.
To extend this project, we decided to modify the algorithm to optimize time over accuracy. Rather than creating a spanning tree from each vertex that reaches every other vertex, we chose a fraction of the vertices at random and calculated a spanning tree for each. Without considering every vertex, there is still a higher probability that an edge between communities will be included in a randomly selected shortest path than one within a community. In other words, the edges with the highest traffic will likely still be detected. This allowed us to reduce the time spent calculating edge betweenness and improved the algorithm’s overall efficiency.
As a check to confirm that each edge that we selected to remove is an edge between communities, we used a modularity calculation to test our progress. Rather than removing the edge with the highest betweenness value, we took the three edges with the highest betweenness values, calculated what the modularity of the graph would be if each one were removed, and chose the one that led to the greatest increase in modularity.
On the Football Conference 2000 dataset, the standard implementation of the Girvan-Newman algorithm took 6.23 seconds, and our modified version took 4.55 seconds, improving the efficiency by 27%. The two algorithms detected nearly identical community structures.
