Girvan Newman Part 3 — Two Multi-Edge Removal
By Ian Webster
Links to other parts: Part 1, Part 2
Multi-Edge Removal
We settled on implementing a multi-edge removal feature in our Girvan Newman algorithm for our project's improvement. This feature speeds up the process of separating communities in the graph by removing multiple edges with equal betweenness values at a time, rather than removing them one at a time like the original algorithm does.
Further adding to this feature, we implemented a range of edge removal to see how this would affect the graph and the performance of the algorithm. The range is any positive whole integer and defines how far away from the maximum betweenness value the algorithm will delete. For instance, if the highest betweenness is 80, and the range is 5, the algorithm will remove all edges with a betweenness greater than or equal to 75. Our intent is that this will speed up the process for the larger datasets by removing larger chunks of edges than the default range of zero would.
Pros:
Compared to single edge removal, multi-edge removal cuts the processing time in half. This is more and more valuable the larger the graph or dataset is.
Below are the calculated times it took for our algorithm to separate the communities of the football graph with single-edge-removal and multi-edge-removal with both the default range of 0 and a range of 3.
Cons:
Unfortunately after recording the runtimes between the different ranges, we found that the differences in times are either non-existent or too small to be deemed effective.
Multi also has a chance to remove integral edges, which will isolate an individual vertex/node to its own community that should not exist. This risk increases as the range increases and as the size of the graph decreases.
Links to other parts: Part 1, Part 2
References
[1] The Boost Graph Library — 1.78.0
[2] Girvan-Newman algorithm | NetworkX Guide
[3]https://www.researchgate.net/publication/271472127_Community_structure_in_networks_Girvan-Newman_algorithm_improvement
[4] smu-cs-3353/22s-pa03-girvan-newman-ian_maxwell: 22s-pa03-girvan-newman-ian_maxwell created by GitHub Classroom
Writer Bio
I am a Sophomore at SMU majoring in Computer Science and Creative Computations. I have a deep interest in procedural generations and algorithms and a passion for game design and development.
