# A Greedy Algorithm for Neighborhood Overlap-Based Community Detection
## 3 Neighborhood OVERlap (NOVER)-Based Community Detection Algorithm
### NOVER Algorithm
Unlike our proposed NOVER algorithm, the Girvan-Newman algorithm for community detection (referred hereafter as GN-original algorithm) requires the betweenness values of the edges to be recomputed at the end of each iteration. Due to the removal of an edge during a particular iteration, the betweenness of the existing edges in the graph could increase or decrease and this needs to be captured in order to appropriately decide on the edge to be removed in the subsequent iteration. Figure 6 illustrates our application of the GN-original algorithm on the same example graph used in Figure 4 for the NOVER algorithm. For each iteration, the edge weights displayed in the graph corresponds to the edge betweenness values computed after the previous iteration and the edge removed (the edge with the maximum betweenness) for the current iteration is listed below the graph along with its betweenness value. We observe the GN-original and NOVER algorithms to determine an identical partition (as well as the best possible partition) of the vertices into communities. To compute the betweenness of the edges per iteration, the \(\Theta(\,|\,V\,|\,+\,|\,E\,|\,)\)-BFS algorithm needs to be run on each of the \(\,|\,V\,|\,\) vertices--incurring a time-complexity of \(\Theta(\,|\,V\,|\,\times\,(\,|\,V\,|\,+\,|\,E\,|\,))\) per iteration. There are a total of \(\,|\,E\,|\,\) edges in the graph and the above time-complexity is incurred for each edge removal. Hence, the overall time-complexity of the original Girvan-Newman algorithm for community detection is \(\Theta(\,|\,E\,|\,\times\,|\,V\,|\,\times\,(\,|\,V\,|\,+\,|\,E\,|\,))\). Note that our proposed NOVER algorithm is of time-complexity \(\Theta(\,|\,E\,|\,\times\,(\,|\,V\,|\,+\,|\,E\,|\,))\) and hence is expected to be faster than the GN-original algorithm by a factor of the number of vertices in the graph. For complex real-world networks of larger size (_i.e._, more nodes), we could expect the NOVER algorithm to run significantly faster than the original Girvan-Newman algorithm for community detection. Figure 5: Example to illustrate the calculation of edge betweenness. ### Givran-Newman Algorithm for Time-Efficient Community Detection

The original Girvan-Newman algorithm for community detection (GN-original algorithm) requires the betweenness of the edges to be recomputed for each iteration of the algorithm (_i.e._, after each edge removal). This is an expensive overhead. In this paper, we envision a variant of the Girvan-Newman algorithm (referred to as GN-efficient) wherein the edges are removed in the decreasing order of their betweenness values that are computed on the input graph and not updated after each iteration. Such an algorithm would have a time-complexity of only \(\Theta(\left\lvert\,V\,\right\rvert\times(\left\lvert\,V\,\right\rvert+\left\lvert \,E\,\right\rvert)+\left\lvert\,E\,\right\rvert\times(\left\lvert\,V\,\right\rvert+ \left\lvert\,E\,\right\rvert))=\Theta((\left\left\lvert\,V\,\right\rvert+ \left\lvert\,E\,\right\rvert)^{2})\), as the BFS algorithm needs to be run once for every vertex at the beginning of the algorithm (to determine the initial edge betweenness values) and then once for each iteration (after an edge removal) to extract the components of the graph. Figure 7 illustrates the execution of the GN-efficient algorithm on the same example graph used in Figures 4 and 6 for the NOVER and GN-original algorithms respectively. One can notice that the initial betweenness values of the two edges 4 and 5, and 5 and 6 are relatively low (value of 5.0 each). However, the removal of edges 4-6 in the first iteration increases the betweenness of the two edges 4 and 5, and 5 and 6 to 30.0 each (refer Figure 6) and no other edge has a betweenness value equal to or larger than 30.0. Hence, in the second iteration, one of these two edges (4 and 5 or 5 and 6) should have been removed (as done in the case of GN-original, Figure 6).