# A Greedy Algorithm for Neighborhood Overlap-Based Community Detection
## 3 Neighborhood OVERlap (NOVER)-Based Community Detection Algorithm
### NOVER Algorithm
score for a community detection algorithm run on a particular network is calculated as the ratio of the product of the cumulative modularity score of the communities detected and the Resolution limit to that of the product of the logarithm of the execution time (in milliseconds) and the number of nodes in the network. The inclusion of the number of nodes in the network as part of the calculation of the MREN score facilitates to make the score as a global measure of evaluating the effectiveness of a community detection algorithm. We claim that larger the MREN score (_i.e._, farther away the score is from 0.0), the larger the effectiveness of the algorithm with respect to balancing the tradeoffs among modularity optimization, resolution limit and execution time. In the case of the NOVER algorithm, we also measure the Threshold NOVER score for weak tie classification. The community detection algorithms were implemented in Java. We take into consideration only the time needed to execute all the steps of the algorithms and not the time incurred to read

Figure 9: Cumulative modularity score _vs._ execution time for the community detection algorithms on real-world Networks 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). the network graph file (containing the node and edge information) and print the results. Hence, the execution time measured is a direct measure of the theoretical time-complexity of the algorithms as presented in Section 4. The simulations were run on a computer with Intel Core i7-2620M CPU @ 2.70 GHz and an installed memory (RAM) of 8 GB. Figures 9 and 10 respectively present the values for the execution time _vs._ cumulative modularity score and fraction of the communities of the smallest size _vs._ cumulative modularity score obtained for the community detection algorithms in each of the real-world networks. Figure 11 displays the cumulative probability of finding a community of various size under each of the community detection algorithms for the real-world networks studied. Figure 10: Cumulative modularity score _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). The Louvain algorithm incurs the smallest execution time for all the real-world networks, as its execution time is theoretically proportional to \(\Theta(\,|\,V\,|\,\times\,\log\,|\,V\,|\,)\) whereas the execution time of the GN-original algorithm is theoretically proportional to \(\Theta(\,|\,E\,|\,\times\,|\,V\,|\,(\,|\,V\,|\,+\,|\,E\,|\,))\). The GN-original algorithm takes the longest execution time for all the real-world networks, but at the same time incurs the largest cumulative modularity score for eight of the nine real-world networks. The Louvain algorithm incurs the largest cumulative modularity score for only the US Airports Network. The cumulative modularity score incurred with the NOVER algorithm is significantly larger than that of the Louvain algorithm for two of the nine real-world networks (US Football network and US Politics Book network) whose spectral radius ratio for node degree is in the lower range (\(\Lambda_{sp}\leq 1.5\)). For five of the nine real-world networks, the NOVER algorithm incurs a cumulative modularity score that is very much comparable to that of the Louvain algorithm. Only for the US Airports network

Figure 11: Cumulative probability distribution for finding a community of certain size in real-world Network graphs.