# A Greedy Algorithm for Neighborhood Overlap-Based Community Detection
## 3 Neighborhood OVERlap (NOVER)-Based Community Detection Algorithm
### NOVER Algorithm
At the end of all the iterations, all the edges in the graph get removed and the algorithm outputs the partition (referred to as the threshold community partition) with the largest cumulative modularity score and the corresponding NOVER score of the edge (as identified across the iterations). ```
Input: Graph \(G(V,\,E)\); Neighbor List \(N(v)\) for every vertex \(v\in V\) Output: Threshold Community Partition; Threshold NOVER Score; \(\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \;\;\
```
Input:Verticesu andv;NeighborListsN(u)andN(v) Output:NOVER(u,v) AuxiliaryVariables:CommonNeighbors,TotalNeighbors Initialization:CommonNeighbors=\varphi;TotalNeighbors=\varphi BeginCompute-NOVER-Score foreveryvertexI\(\in\)N(u)andi\(\
eq\)vdoTotalNeighbors=TotalNeighbors\(\cup\){i} endforforeveryvertexi\(\in\)N(v)andi\(\
eq\)udoifi\(\
eq\)TotalNeighborsthenTotalNeighbors=TotalNeighbors\(\cup\){i} endififif\(\in\)N(u)thenCommonNeighbors=CommonNeighbors\(\cup\){i} endif endforNOVER(u,v)=|CommonNeighbors|/|TotalNeighbors| returnNOVER(u,v) EndCompute-NOVER-Score
```
**Algorithm 2** Pseudo Code to Determine Neighborhood Overlap Score for an Edge
```
Input:GraphG=(V,E);StartingVertexs;NeighborListN(v)foreveryvertexv\(\in\)V Output:VisitedVertices AuxiliaryVariables:FIFOQueue Initialization:FIF0 Queue=\(\varphi\);VisitedVertices=\(\varphi\) BeginBFS FIFOQueue=FIFOQueue\(\cup\){s} VisitedVertices=VisitedVertices\(\cup\){s} while(FIFOQueue\(\
eq\)\(\varphi\))doVertexu=Extract(FIFOQueue)//removethevertexfromthefrontoftthequeue foreveryvertexv\(\in\)N(u)doifv\(\
eq\)VisitedVerticesthenVisitedVertices=VisitedVertices\(\cup\){v} FIFOQueue=FIFOQueue\(\cup\){v} endif endfor endwhile returnVisitedVertices EndBFS
```
**Algorithm 3** Pseudo Code of the Breadth First Search Algorithm to Determine a Connected Component
```
Input:GraphG=(V,E); NeighborListN(v)foreveryvertexv\in V Output:Components AuxiliaryVariables:VerticesTraversed;VerticesNotTraversed Initialization:Components=\varphi,VerticesTraversed=\varphi,VerticesNotTraversed=V BeginFindComponents while(|VerticesTraversed|<|V|)do Vertexs=PickavetexrandomlyfromthesetVerticesNotTraversed ComponentVertexsetS=BFS(G,N,s)//BFSreturnsthesetofverticesvisited foreveryv\in\Sdo VerticesNotTraversed=VerticesNotTraversed-{v} VerticesTraversed=VerticesTraversed\(\cup\){v} endfor Components=Components\(\cup\)S endwhile returnComponents EndFindComponents
```
**Algorithm 4** Pseudo Code to Determine All the Connected Components of a Graph
```
Input:CommunityC(v1,v2,...,vn)ofnvertices;G=(V,E);NeighborListM(v) foreveryvertexv\in V Output:Community-Modularity-Score Initialization:Community-Modularity-Score=0,Modularity(u,v)foranypairu,v\in C BeginCompute-Modularity-Score foreveryvertexv\in Cdo foreveryvertexv\({}_{j}\in\)Candi<jdo if(v\({}_{i}\),v\({}_{j}\))\(\in\)then Modularity(v\({}_{i}\),v\({}_{j}\))=1-(|N(v\({}_{i}\)|\(\times\)|N(v\({}_{j}\)|/(2\times|E|))\) else Modularity(v\({}_{i}\),v\({}_{j}\))=0-(|N(v\({}_{i}\)|\(\times\)|N(v\({}_{j}\)|/(2\times|E|))\) endif Community-Modularity-Score=Community-Modularity-Score+Modularity(v\({}_{i}\),v\({}_{j}\)) endfor endfor returnCommunity-Modularity-Score EndCompute-Modularity-Score
```

**Algorithm 5** Pseudo Code to Determine the Modularity Score for a Community

The BFS algorithm takes \(\Theta(|V|+|E|)\) time to run on a graph of \(|V|\) vertices and \(|E|\) edges. We run BFS once for each iteration of the proposed NOVER algorithm and there are a total of \(|E|\) iterations (one iteration per edge removal), incurring a time-complexity of \(\Theta(|E|\times(|V|+|E|))\).