# A Greedy Algorithm for Neighborhood Overlap-Based Community Detection
## 3 Neighborhood OVERlap (NOVER)-Based Community Detection Algorithm
### NOVER Algorithm  
Our objective in this paper is to develop a formal and organized algorithm for using the NOVER scores to determine a highly modular partitioning of the vertices into communities instead of adopting a trial-and-error approach to determine a partitioning of the vertices into communities based on each possible threshold NOVER value for the edges. In this pursuit, we propose that instead of fixing a threshold NOVER value and removing the edges with NOVER value less than the threshold to obtain a partition, we would rather iteratively remove one edge at a time (in the increasing order of their NOVER values) and evaluate the cumulative modularity score of the resulting partition. As we remove the edges, one at a time, we keep track of the partition that has resulted in the largest cumulative modularity score; at the end, the algorithm returns the partition with the largest cumulative modularity score (referred to as the _Threshold Community Partition_). Though the proposed algorithm is greedy and is not guaranteed to give the optimal partition for all graphs, we observe the algorithm to determine partitions with cumulative modularity scores that are only at most 60% less than that determined using the well-known Girvan-Newman edge betweenness-based algorithm for community detection, and incurs a time-complexity that is significantly less than that of the Girvan-Newman algorithm (the actual execution time of the NOVER algorithm could be as low as 1% of the execution time of the original Girvan-Newman algorithm). Moreover, on the basis of the NMI scores [12], we observe the communities detected with the NOVER algorithm to be significantly similar (with respect to the composition) to those detected with the Girvan-Newman algorithm. The proposed algorithm is described as follows (see Algorithm 1 for the high-level pseudo code of the entire algorithm and Algorithms 2-5 for the pseudo codes of the various sub routines). We compute the NOVER scores (Algorithm 2 presents the pseudo code for computing the NOVER scores) of the edges only once, before the first iteration, and store them in a sorted order in a heap-based priority queue, NOVER-List (the edge with the smallest NOVER score is the root of the heap). In each iteration, we remove the edge with the lowest NOVER score (among the edges existing for that iteration) and run the Breadth First Search (BFS) algorithm (see Algorithm 3 for the pseudo code of BFS to determine a connected component) to obtain the various connected components of the graph (see Algorithm 4 for the pseudo code to determine all the connected components of a graph). Note that due to the removal of an edge, the number of components (each component is a community) of a graph could be different  
Figure 3: Motivating example to illustrate the impact of not choosing an appropriate threshold value for the neighborhood overlap score to partition the Network into communities. (**a**) A greedy approach of removing all edges with NOVER score less than or equal to the threshold; (**b**) A better partition of the vertices into communities with a relatively larger cumulative modularity score. than what existed prior to the removal of the edge. A component of a graph is the largest connected subgraph such that inclusion of an additional vertex makes the sub graph disconnected [15]. We compute the modularity scores for each of the resulting communities (see Algorithm 5 for the pseudo code to determine the modularity score for a community) and also compute the cumulative modularity score of the partition (set of communities). We continue with each of the iterations, as described above, and keep track of the partition with the largest cumulative modularity score obtained across the iterations and also keep track of the NOVER score of the edge whose removal lead to the identification of the partition with the largest cumulative modularity score.