# A Greedy Algorithm for Neighborhood Overlap-Based Community Detection
## 3 Neighborhood OVERlap (NOVER)-Based Community Detection Algorithm
### NOVER Algorithm
(**a**) Input graph; (**b**) Betweenness 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 Betweenness score of 25.0 is removed; (**d**) At the end of Iteration 6: Remaining edges in the graph after edges 6 and 7 with Betweenness score of 7.0 is removed; (**e**) At the end of Iteration 7: Remaining edges in the graph after edges 3 and 4 with Betweenness score of 7.0 is removed; (**f**) At the end of Iteration 10: Remaining edges in the graph after edge 0–2 with Betweenness score of 5.0 is removed; (**g**) At the end of Iteration 11: Remaining edges in the graph after edges 5 and 6 with Betweenness score of 5.0 is removed; (**h**) At the end of Iteration 12: Remaining edges in the graph after edge 8–10 with Betweenness score of 5.0 is removed; (**i**) At the end of Iteration 19: Final partitioning of the network graph into communities. Louvain algorithm not guaranteed to detect a globally optimal partition. In the second step, we form an aggregated graph with each community (detected in the first step) being considered as a node; there exists a link between two nodes in the aggregated graph if there existed at least one link between the corresponding two communities and the weight of the link in the aggregated graph is the number of such cross-community links. In addition, there is a self-loop for a community (node) in the aggregated graph if there exists an edge between any two nodes within the community (one self-loop for each such edge). The algorithm proceeds to the next phase based on the aggregated graph of communities as nodes. We proceed in phases until an aggregation with the maximum modularity score is obtained. To start with (during the first phase), each node is in its own community. The time-complexity of Louvain algorithm is \(\Theta(\mid V\mid\times\log\mid V\mid)\) for a graph of \(\mid V\mid\) vertices. ## 5 Simulations

In this section, we evaluate the performance of the proposed NOVER algorithm on real-world network graphs and do a comparative analysis with the performance of the original and time-efficient variants of the Girvan-Newman algorithm (GN-original and GN-efficient) as well as with the Louvain algorithm. We consider a total of nine real-world network graphs: The US College Football Network (FN) [4] is a network of 115 football teams (each team is a node) who competed in the Fall 2000 season and there is a link between any two nodes if the corresponding teams have played against each other at least once in the past. The Dolphin Network (DN) [16] is a network of 62 dolphins (each dolphin is a node) living in Doubtful Sound, New Zealand; there is a link between any two nodes if the corresponding dolphins were seen together moving around over a period of time. The Karate Network (KN) [17] is a network of 34 members (each member is a node) of a Karate Club in a US university in the 1970s--there exists a link between two nodes if the corresponding members have been noticed interacting with each other over a period of time. The US Politics Books Network (PN) [18] is a network of 105 books (each book is a node) related to US politics sold in Amazon.com: there exists a link between any two nodes (_i.e._, books, say \(u\) and \(v\)) if customers who bought one book (say book \(u\)) also bought the other book (say book \(v\)) and _vice-versa_. The US Airport Network (AN) [19] is a network of 332 airports (each airport is a node) and the direct flight connections (edges) between them. The Erdos971 Collaboration Network (EN) [20] is a network of 472 Collaborators (nodes) who may have either published a paper directly in collaboration with [PERSON] or through a chain of collaborators leading to [PERSON]; there exists an edge between two nodes if the corresponding authors have co-authored publications.