# A Greedy Algorithm for Neighborhood Overlap-Based Community Detection
## 3 Neighborhood OVERlap (NOVER)-Based Community Detection Algorithm
### NOVER Algorithm
The Les Miserables Network (LN) [21] is a network of 77 characters that appeared in the novel Les Miserables; there exists an edge between two nodes (characters) if the corresponding characters appeared together in at least one chapter of the novel. The C. Elegans Neural Network (NN) [22] is a network of 297 neurons (nodes) in the hermaphrodite Caenorhabditis Elegans; there is an edge between two neurons if they interact with each other in the form of chemical synapses, gap junctions and neuromuscular junctions. The Citation Graph Drawing Network (CN) [23] is a network of 311 papers (nodes) published in the area of Graph Drawing (GD) in the proceedings of the GD' 1994 to GD' 2000 conferences; there exists an edge between two papers if one of the papers has cited the other paper as a reference. Though the CN network is a directed network, we modeled it as an undirected network for consistency with the other real-world networks considered as well as due to the underlying assumption of undirected edges for the community detection algorithms analyzed in this paper. All the nine real-world networks considered are modeled as undirected network graphs. Figure 8 illustrates the degree distribution of the real-world network graphs (both the probability mass function and the cumulative distribution [24]), listed in the increasing order of the spectral radius ratio for node degree. The spectral radius ratio for node degree (denoted \(\lambda_{sp}\)) for a graph [25] captures the extent of variation of the node degree with respect to the average node degree and is calculated as the ratio of the principal eigenvalue of the adjacency matrix of the graph and the average node degree (denoted \(k_{avg}\)). The value for \(\lambda_{sp}\) is always greater than or equal to 1.0. The farther the \(\lambda_{sp}\) value from 1.0, the larger the variation in node degree. The US Football Network (FN) has a \(\lambda_{sp}\) value of 1.01 (vindicating the Poisson-style degree distribution) and the degree distribution of the other real-world networks gradually becomes scale-free [26], with the US Airports Network (AN) having the largest \(\lambda_{sp}\) value of 3.22. We measure the following five performance metrics and the probability distribution: (i) Cumulative Modularity Score of the best possible communities detected by each of the algorithms; (ii) Execution time (in milliseconds) for each of the algorithms; (iii) Giant community size--Fraction of the nodes in the largest community among the communities detected; (iv) Resolution limit--Fraction of the communities of the smallest size among all the communities detected; (v) Normalized Mutual Information, NMI: Measure of the extent of similarity (evaluated as a quantitative score from 0 to 1) between the communities detected by two different algorithms; and (vi) Cumulative probability of finding a community of size less than or equal to a certain value. We also introduce a new metric called the MREN score (M-Modularity score; R-Resolution limit; E-Execution time; N-Number of nodes) to evaluate the effectiveness of a community detection algorithm with respect to balancing the tradeoffs among the metrics (modularity score, resolution limit and execution time). Quantitatively, the MREN

Figure 8: Degree distribution of the real-world Network graphs. (**a**) US football network (FN): \(\lambda_{sp}=1.01\); (**b**) Dolphin Network (DN): \(\lambda_{sp}=1.40\); (**c**) US Politics Book Network (PN): \(\lambda_{sp}=1.42\); (**d**) Karate Network (KN): \(\lambda_{sp}=1.47\); (**e**) C. Elegans Network (NN): \(\lambda_{sp}=1.68\); (**f**) Les Miserables Network (LN): \(\lambda_{sp}=1.82\); (**g**) Citation GD Network (CN): \(\lambda_{sp}=2.24\); (**h**) Erdos971 Network (EN): \(\lambda_{sp}=2.28\); (i) US Airports Network (AN): \(\lambda_{sp}=3.22\).