# A Greedy Algorithm for Neighborhood Overlap-Based Community Detection
## 3 Neighborhood OVERlap (NOVER)-Based Community Detection Algorithm
### NOVER Algorithm
It takes \(\Theta(|E|\times\log|E|)\) time to construct the NOVER-List (a heap) and then \(\Theta(\log|E|)\) to re-heapily it for each edge removal; the time-complexity of managing the heap is thus \(\Theta(|E|\times\log|E|)\). Thus, the time-complexity of the NOVER algorithm is \(\Theta(|E|\times\log|E|+|E|\times(|V|+|E|))=\Theta(|E|\times(|V|+|E|+\log|E|))\). But, since \(\Theta(|E|)\) is more dominating than \(\Theta(\log|E|)\), we could say the overall time-complexity of the proposed NOVER algorithm is \(\Theta(|E|\times(|V|+|E|))\). ### Example for the NOVER Algorithm

Figure 4 presents an example to illustrate the sequence of iterations of the NOVER algorithm. The Neighborhood Overlap (NOVER) scores for the edges are calculated before the beginning of the first iteration. We remove the edges (one edge removal per iteration) in the increasing order of their NOVER scores. For every edge removal, we identify the various components (each component is

a community) of the graph and calculate the modularity score of each community and thence the cumulative modularity score of the partition. If the cumulative modularity score calculated in an iteration exceeds the largest known cumulative modularity score until then (that is the largest known cumulative modularity score prior to the iteration), we update the cumulative modularity score as well as refer to the NOVER score of the edge that contributed to the largest cumulative modularity score as the Threshold NOVER score. We observe the input graph to remain as one single component for the first iteration with a cumulative modularity score of 1.89 and the Threshold NOVER score of 0.14 (corresponds to the NOVER score of the first edge removed). In the second iteration, the removal of edges 5 and 6 with a NOVER score of 0.25 disintegrated the graph into two components {0, 1, 2, 3, 4, 5} and [6, 7, 8, 9, 10] incurring a cumulative modularity score of 9.37 that is greater than the larger cumulative modularity score known until then. We update the largest cumulative modularity score to 9.37 and set the Threshold NOVER score of the edge to 0.25. In the third iteration, we remove edges 4 and 5 that has the same NOVER score as that of the currently known Threshold NOVER score; but, the removal of edges 4 and 5 disintegrates the graph into three communities, with a cumulative modularity score of 9.32, slightly less than the currently known largest cumulative modularity score. Hence, we do not update the largest cumulative modularity score at the end of the third iteration. Further, the edge removals in the subsequent iterations also do not appear to increase the cumulative modularity score

Figure 4: Example to illustrate the execution of the NOVER algorithm. (**a**) Input graph; (**b**) Neighborhood overlap values for the edges in the input graph; (**c**) At the end of Iteration 1: Remaining edges in the graph after edge 4–6 with NOVER score of 0.14 is removed; (**d**) At the end of Iteration 2: Remaining edges in the graph after edges 5 and 6 with NOVER score of 0.25 is removed; (**e**) At the end of Iteration 3: Remaining edges in the graph after edges 4 and 5 with NOVER score of 0.25 is removed; (**f**) At the end of Iteration 5: Remaining edges in the graph after edge 8-10 with NOVER score of 0.33 is removed; (**g**) At the end of Iteration 7: Remaining edges in the graph after edge 0–2 with NOVER score of 0.33 is removed; (**h**) At the end of Iteration 12: Remaining edges in the graph after edges 3 and 4 with NOVER score of 0.50 is removed; (**i**) At the end of Iteration 19: Final partitioning of the network graph into communities. of the communities (we only see a reduction in the cumulative modularity score of the communities detected in iterations 3-19). Thus, the best possible partition of the vertices into communities that could incur the largest cumulative modularity score is the partition detected at the end of the second iteration: {0, 1, 2, 3, 4, 5} and {6, 7, 8, 8, 10} with a cumulative modularity score of 9.37 and threshold NOVER edge score of 0.25.