The Implementation and Analysis of the Girvan-Newman Algorithm Part 2
By Sneha Alex, Giancarlos Dominguez, and Melodie Zhu
The Implementation and Analysis of the Girvan-Newman Algorithm Part 3
Our modification of the Girvan-Newman method attempts to improve upon the original algorithm by allowing removal of multiple edges, as delineated in Despalatović, Vojković, and Vukic̆ević’s article “Community Structure in Networks: Girvan-Newman Algorithm Improvement.” In our implementation, we modified our Girvan-Newman algorithm to be removing three edges at one time instead of one-by-one. This extension can be implemented as the Girvan-Newman algorithm leaves the order of removal edges with the same highest edge betweenness to the programmer’s discretion.
This modification applies well to complex networks, where it is likely that there are more edges with the same highest edge betweenness. By removing all edges with the highest edge betweenness in the same step, the number of recalculations of edge betweenness can be greatly reduced in networks with strong community structure. Originally, the time complexity of recalculating edge betweenness is O(mn), where m is the number of edges and n is the number of vertices. The modified algorithm has the best-case scenario of reducing complexity to O(mn) by reducing the number of calculations.
The implementation of this modified algorithm is as follows:
- Calculate edge betweenness for every edge in the graph.
- Remove all edges with the highest edge betweenness.
- Recalculate edge betweenness for remaining edges.
- Repeat steps 2–4 until the graph is empty.
This extension also improves the Girvan-Newman algorithm by allowing the community structure to produce a unique output for a given input, as it does not depend on the labeling of the vertices in the graph. The result of the Girvan-Newman method may change depending on if the labeling of the vertices are rearranged.
Citations
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.
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.
