A Custom, Competing Algorithm to the Girvan-Newman
This is part two of the post. The first half is mentioned in Kas Taghavi’s profile.
Algorithm Efficiency
As shown by the graphs and our explanation of our custom algorithm we can conclude that we have developed a very efficient algorithm by using the Boost Graph Library and we can prove it by comparing it to the Girvan-Newman . The Girvan-Newman algorithm iterates through each vertex, v, twice then each node’s adjacent nodes, a, and then each edge, e, leading to an inefficient program of O(v^e) in the worst case when the number of edges overpower the number of vertices. This is because of the while loop that loops until each vertex has been visited. The custom algorithm only loops through the vertices and each vertex’s adjacent nodes once, as well as the number of edges in order to remove an edge. In the worst-case scenario, every vertex is connected to every other vertex, essentially being one big community. This means that the algorithm goes through each vertex, and the adjacent vertices for that vertex, or a O(v²*b).
We tested the algorithm’s time complexities on different randomly generated graphs and recorded the times as the number of vertices increased. Below is a table of random graphs and the times that it takes for the Girvan-Newman and custom algorithms to run:
As evident by the table above, the custom algorithm is much more efficient as its completion time is much more efficient than the Girvan-Newman algorithm’s completion time in both cases where only the number of edges increases as well as both number of nodes and the number of edges increase.
Limitations of Custom Algorithm
While the algorithm is very efficient and effective in determining communities, there are edge cases where the resulting graph would be lacking communities. This would come when there is no strongly defined community in the network as the intersection between the current node and each of its adjacent nodes falls below the intersecting node threshold that the algorithm tests for. Because of this, the algorithm may fail to generate communities for weakly connected graphs. This flaw is exemplified in random datasets where the probability of a connection is under 10%, such as in the image below. It is evident that no real communities are formed because of the weak connection as stated above.
All in all, the custom algorithm is much faster than the Girvan-Newman algorithm in boost implementation. That being said, the custom implementation is at a disadvantage when detecting communities in a network where there are no large communities and will end up returning minimal or no communities, an area that the Girvan-Newman algorithm will be better at.
Author: My name is Clayton Manchac and I am a computer science, finance, math, and statistics enthusiast with an interest in trading. I enjoy windows down driving, skiing, country music, & pickleball.
