Modifications to the Base Implementation of the Girvan-Newman Algorithm (GMZ Series Part 2)
If you have not read part 1 of this Girvan-Newman Algorithm series, we highly suggest you read it here (hyperlink here ).
Reintroduction to Girvan Newman Algorithm
As mentioned in part 1 of this 3-part series, the Girvan-Newman Algorithm, named after Michelle Girvan and Mark Newman, is a hierarchical method used to detect communities in networks[1].
Modifications — Multi Edge Removal
Our initial idea for the extension portion of our project was to find a variety of modifications and improvements to the Girvan-Newman Algorithm and essentially implement all of them. Following these implementations, we were going to compare the individual performance of each modification and, finally, implement all of them into the “Ultimate Girvan-Newman Algorithm.” However, after much research, we found that many of these modifications do not work on undirected, unweighted graphs (which we were using). So, we had to do away with the idea.
Regardless, we decided to implement the one modification that DID work with our implementation, which was the ability for multi-edge removal. Essentially, instead of removing one edge at a time, we can remove multiple edges at a time which reduces the number of operations but retains the same computational complexity. So, it is still unable to apply the algorithm to networks with a lot of nodes[2].
Our results?
For one, the time it took to run the base implementation versus running the extension portion could be discerned. In terms of its performance, which is measured by the final modularity, the modularity decreased from 0.65597 from the base implementation to 0.611.
Notes
Although we weren't able to implement it, we found a certain modification interesting. This modification is worth noting.
- Trust-Based Girvan Newman Algorithm: This modification was highly intriguing because it reconstructs the Girvan-Newman Algorithm so it isn’t based on the betweenness centrality, but, rather, it is based on trust. This modification did not work with our algorithm because its implementation works better with weighted, directed graphs, which was not what we were using for our implementation[3].
The trust between nodes u and v is determined using the “direct trust” between nodes (u,v) and the “indirect trust between nodes (u, v).
The pseudocode for this algorithm is as follows:
As you’ll notice, this algorithm requires a weighted graph so we didn’t implement this one. We thought it was still worth noting though!
Sources:
[1] https://en.wikipedia.org/wiki/Girvan%E2%80%93Newman_algorithm.
[2] L. Despalatović, T. Vojković, and D. Vukic̆ević, “Community structure in networks: Girvan-Newman algorithm improvement,” 2014 37th International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO), 2014, pp. 997–1002, doi: 10.1109/MIPRO.2014.6859714.
[3] https://link.springer.com/content/pdf/10.1007/s12652-021-03508-y.pdf
About Eileen:
Eileen is a sophomore at Southern Methodist University. She is pursuing a B.S. in Computer Science with a specialization in Cyber Security. In her free time, Eileen enjoys catching up on sleep and practicing self-care.
