The implementation and Analysis of the Girvan-Newman Algorithm Part 1

By Giancarlos Dominguez, Melodie Zhu, and Sneha Alex

Intro

The Girvan-Newman Algorithm is an important process in the field of graph theory. It focuses on iterating through the entire graph, deleting edges with the highest between-ness centrality value until the communities are obviously clear, showing which nodes are closer to which other nodes.

Given the task of implementing the algorithm to work with undirected and unweighted graphs as our third project for CS 3353: Fundamentals of Algorithms, first we must recognize the necessary steps:

Algorithm Logic

One of the biggest concepts for the algorithm is edge between-ness, which is the number of how many shortest paths cross through the edge. By calculting the between-ness of all edges from a different starting point, once all nodes have been visited, the edge with the highest value is removed from the graph, and the process is continued until there are no more edges. However, we took a different approach, and instead we programmed it so that it will stop when the minimum number of communities has been reached, the minimum being a number chosen by the user of the program.

Here is a basic rundown of the algorithm:

while (# of communities found < # of comminties user wants)
   for (each node in the graph)
      calculate the between-ness of each edge 
   Find the edge with the highest between-ness value and delete it
   Calculate the communities again

Results

Testing our program with a simple graph and a more well-known dataset of football teams during the 2000 conference, and setting a minimum of 4 communities, we got the following results, presented as a before and after:

Before: 10 nodes and 15 edges

After: 10 nodes, 4 edges, 4 communities

Here the communities and their members are visible due to the size of the graph.

Football dataset(Before): 613 Nodes and 115 Edges

Football dataset(After): 613 Nodes and 569 Edges

Here is the result of the football dataset. Granted the communities are much less clear than the previous graph, but nonetheless, it shows a visible difference to how the graph was before underdoing the algoritm.

Conclusion

Although the implementation of the Girvan-Newman Algorithm is not 100% accurate, it is somewhat succesful in providing a notion of which communties are present in a graph. For futher reading on the extension part of the project and analysis, readers can click here.

Github code

Readers can click on the link to the repo here.

Giancarlos Dominguez is a sophomore at SMU, majoring in Computer Science with a minor in English. Some days he prefers C++ and Python. Other days he prefers normal english.

Melodie Zhu is a sophomore at Southern Methodist University, studying Computer Science and Accounting.

Sneha Alex is a sophomore at Southern Methodist University and is pursuing a Bachelor’s degree in Computer Science.