# A Greedy Algorithm for Neighborhood Overlap-Based Community Detection
## 1 Introduction  
Community detection is one of the classical problems of complex network analysis. A community in a network graph is a subset of the vertices that have a relatively larger density of edges among themselves than to the rest of the vertices [1]. The quality of the partitioning of a network into communities is evaluated using a metric called the modularity score [2]; the larger the modularity score, the more appropriate is the partitioning of the vertices into communities. The problem of identifying a partition of the network into communities with the largest modularity score is NP-complete [3]. Several algorithms have been proposed in the literature for community detection and a majority of these are based on the notion of betweenness [4], defined for an edge as the fraction of the shortest paths between any two vertices going through the edge, considered over all pairs of vertices. Edges with high betweenness are typically removed to disintegrate a connected network into two or more components--each of which are considered to form a closely-knit community. Edge betweenness-based algorithms for community detection are typically considered to identify communities with a larger modularity score at the cost of a significantly larger computation time [5]. Another potential weakness of community detection algorithms could be the inability to detect smaller communities (called the resolution limit problem [6]); this weakness is more prominent in multi-level aggregation algorithms (like the Louvain algorithm [7]). To get around this bottleneck, the focus of research in the area of community detection has veered around strategies (e.g., [8; 9; 10]) that identify the critical edges (the edges that if removed will lead to the identification of closely-knit communities with high modularity score) without essentially running the time-consuming shortest path algorithms for each vertex and for each edge removal [4; 5] as well as be able to identify smaller communities that indeed exist inthe network being analyzed (in such a way that the overall sum of the modularity scores of the communities do not get significantly lowered). One edge-based criterion that can be quickly computed and at the same time appears to be quite effective for community detection is the \"neighborhood overlap\". The neighborhood overlap [11] for an edge (\(u\), \(v\)) is defined as the ratio of the number of nodes that are neighbors of both the vertices \(u\) and \(v\) to that of the number of nodes that are neighbors of at least one of the two vertices \(u\) or \(v\). As one can see from the above definition, the neighborhood overlap of an edge can be computed just based on the local neighborhood information of the end vertices of the edge and no global knowledge is required. An edge (\(u\), \(v\)) that has a smaller value for the neighborhood overlap is more likely to play a significant role in facilitating communication between \(u\) and \(v\) as well as between vertices that are in the vicinity (_i.e._, one or more hops) of \(u\) and vertices that are in the vicinity of \(v\). The sub graph of vertices involving \(u\) and the sub graph of vertices involving \(v\) are more likely to have fewer edges connecting them; otherwise, the edge (\(u\), \(v\)) would have had a larger neighborhood overlap. Edges having a lower neighborhood overlap are thus referred to as \"weak ties\" [11] and are often considered for removal to disintegrate a connected network to two or more components--each of which form a community. The currently known approach [11] of utilizing weak ties and neighborhood overlap for community detection involves fixing a threshold value for the neighborhood overlap and all edges in which neighborhood overlap is less than this threshold value are categorized as weak ties and the rest of the edges are categorized as strong ties. All of these weak ties are removed from the network and the resulting network components form the different communities for the network, referred to as the \"partition\" of the network.