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

By Sneha Alex, Giancarlos Dominguez, and Melodie Zhu

In their article “Community Structure in Networks: Girvan-Newman Algorithm Improvement,” Despalatović, Vojković, and Vukic̆ević describe a modification of the Girvan-Newman algorithm that deletes multiple nodes at a time instead of just one. Their findings indicated that their method had similar accuracy in identifying communities within a graph, but much faster. Upon implementing their algorithm, we found this to be true. This updated algorithm clearly operates much quicker than the original Girvan-Newman algorithm we implemented. We ran both algorithms on the graph of Football conferences. The Girvan-Newman algorithm took 3.73718 seconds to execute, while the improved algorithm took 0.738487 seconds. Below is the graph visualizing the time difference between these two algorithms.

As seen in the graph, the original Girvan-Newman algorithm was around five times slower than the improved algorithm with this graph. As established in Despalatović’s, Vojković’s, and Vukic̆ević’s research paper, deleting multiple nodes with each iteration of the Girvan-Newman algorithm has a similar efficiency in recognizing communities. Our findings match with the results suggested in their paper, with a similar recognition of communities with a much faster execution time.

Of course, without going through every node, this algorithm may not be quite as effective at recognizing communities as the Girvan-Newman algorithm. However, the very similar success rate and the much faster execution time make Despalatović’s, Vojković’s, and Vukic̆ević’s algorithm a good improvement to the Girvan-Newman algorithm.

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.

M. Girvan and M. E. J. Newman, “Community structure in social and biological networks,” Proceedings of the National Academy of Sciences, vol. 99, no. 12, pp. 7821–7826, Jun. 2002, doi: 10.1073/pnas.122653799.

M. E. J. Newman and M. Girvan, “Finding and evaluating community structure in networks,” Phys. Rev. E, vol. 69, no. 2, p. 026113, Feb. 2004, doi: 10.1103/PhysRevE.69.026113.

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.