# A Greedy Algorithm for Neighborhood Overlap-Based Community Detection
## 3 Neighborhood OVERlap (NOVER)-Based Community Detection Algorithm
### NOVER Algorithm
(**a**) US Football Network (FN); (**b**) Dolphin Network (DN); (**c**) US Politics Book Network (PN); (**d**) Karate Network (KN); (**e**) C. Elegans Network (NN); (**f**) Les Miserables Network (LN); (**g**) Citation GD Network (CN); (**h**) Erdos971 Collaboration Network (EN); (**i**) US Airports Network (AN). and Dolphin network, we observe the cumulative modularity score of the Louvain algorithm to be appreciably larger than that of the NOVER algorithm. All of the above observations hold true with the execution time of the NOVER algorithm significantly lower to that of the GN-original algorithm; the difference in execution time increases with increase in the number of nodes and/or the number of edges. The GN-original algorithm is significantly slower for networks with a larger number of nodes and/or edges. The NOVER algorithm incurs an execution time that is either less than or at most equal to that of the GN-efficient algorithm for all the real-world networks, and at the same time incurs a cumulative modularity score that is always either larger or at the worst case equal to that of the GN-efficient algorithm; note that both the NOVER and GN-efficient algorithms have the same theoretical time-complexity of \(\Theta(\,|\,E\,|\,\times\,(\,|\,V\,|\,+\,|\,E|))\). Figure 4:0 Fraction of nodes in the giant component _vs._ fraction of the communities of the smallest size for the community detection algorithms on real-world Network graphs. (**a**) US Football Network (FN); (**b**) Dolphin Network (DN); (**c**) US Politics Book Network (PN); (**d**) Karate Network (KN); (**e**) C. Elegans Network (NN); (**f**) Les Miserables Network (LN); (**g**) Citation GD Network (CN); (**h**) Erdos971 Collaboration Network (EN); (i) US Airports Network (AN). Though the Louvain algorithm and GN-original algorithm appear to be respectively optimal incurring the lowest execution time and largest cumulative modularity score, we observe both these algorithms suffer from the poor resolution problem (incur lower values for the fraction of communities of smaller size), especially the Louvain algorithm. Due to the multi-level aggregation nature of the Louvain algorithm, it becomes difficult to detect communities of size lower than a certain value that could indeed contribute to a larger cumulative modularity score. On the other hand, the NOVER algorithm is able to detect communities of smaller size with an appreciably higher probability and at the same time incurs a larger cumulative modularity score that is very much comparable to that of the Louvain algorithm for seven of the nine real-world networks. Though the GN-efficient algorithm incurs a comparable value (to that of the NOVER algorithm) for the resolution limit for most of the real-world networks, there exists at least a couple of real-world networks for which the fraction of communities of smallest size detected by the GN-efficient algorithm is lower than that of the NOVER algorithm. With respect to the cumulative probability distribution of the community size (see Figure 11), we observe the community size distribution to follow a power-law pattern, similar to that of the degree distribution. We observe the NOVER algorithm to incur a larger probability of finding a community of smaller to moderate size for real-world networks with lower variation in node degree (_i.e._, spectral radius ratio for node degree \(\leqslant\)1.5). As the spectral radius ratio for node degree increases beyond 1.5, we observe the cumulative probability distribution profiles for the community sizes detected by all the community detection algorithms to overlap with each other. For networks of moderate variation in node degree, the GN-original and Louvain algorithms appear to sustain a relatively lower cumulative probability for finding a community of size less than or equal to a certain value. The original and time-efficient versions of the Girvan-Newman algorithm appear to detect giant components of relatively larger size (see Figure 12) compared to that of the Louvain and NOVER algorithms.