# A Greedy Algorithm for Neighborhood Overlap-Based Community Detection
## 3 Neighborhood OVERlap (NOVER)-Based Community Detection Algorithm
### NOVER Algorithm
## 4 Girvan-Newman Algorithm for Edge Betweenness-Based Community Detection

In this section, we briefly review the working of the well-known Girvan-Newman algorithm for edge betweenness-based community detection [PERSON] (1998). The betweenness of an edge is a measure of the fraction of the number of shortest paths going through the edge among all the shortest paths existing between a pair of nodes, considered across any two nodes in the network graph. ### Procedure to Compute the Edge Betweenness

The Girvan-Newman algorithm involves three phases to calculate the betweenness of the edges: (i) We run the Breadth First Search (BFS) algorithm starting from every node in the graph and determine BFS-trees rooted at every node; (ii) For each such BFS-tree rooted at a particular node \(r\), we determine the number of shortest paths from node \(r\) to every other node in the network. The number of shortest paths from the root to itself is 1; the number of shortest paths for a node \(v\) (at a level \(l>0\) in the BFS-tree rooted at node \(r\)) from the root \(r\) (the root is considered to be at level 0) is the sum of the number of shortest paths from the root node \(r\) to the predecessor nodes \(u\) (at level \(l-1\) in the BFS-tree rooted at node \(r\)) in the original graph; (iii) For each of the BFS-trees, we determine the amount of flow from the root node (say node \(r\)) to all the other vertices and thereby determine the amount of flow going through each edge. For each BFS tree, to begin with, we assume one unit of flow originates at each node. We start with the node at the bottommost level and proceed one level at a time, all the way to the root node. For each BFS tree, except the root node, a node at level \(l\) aggregates the flow along the edges to nodes at level \(l+1\), adds its own one unit of flow and proportionally divides the final aggregated flow to its predecessors at level \(l-1\) in the original graph (based on the number of shortest paths originating from the root node to the predecessor). The total flow through an edge is the sum (for directed graph) or half of the sum (for undirected graph) of the flows determined through that edge when BFS is run from every vertex in the graph. We illustrate the calculation of flow on each edge of a BFS-tree in Figure 5 on an example graph. We explain the procedure to compute the flow values using a sample BFS tree in Figure 5. Consider the BFS tree rooted at node A. There is only one node (node D) at the bottommost level. Let 1 unit of flow start from node D. Node D gets two of its shortest paths to the root node A through node F and one shortest path through node G. Hence, node D sends 2/3 of the flow to node F and 1/3 of the flow to node G. Node F adds the 2/3 flow received to its own one unit of flow (considered to originate at itself) and splits the resulting 1.67 units of flow equally to its two predecessor nodes B and E (as each of them contribute one shortest path from the root node A) and sends 0.835 to each of nodes B and E. Node G merely adds the 0.33 flow units to the one unit of flow originating at itself and sends 1.33 to nodes B. Node B aggregates the 1.33 and 0.835 units of flow coming along the edges from nodes at the lower level and adds its own one unit of flow and sends 3.165 units of flow to node A. Node E simply adds one unit of flow to the 0.835 units of flow received from node F and sends 1.835 units of flow to node A. Original Version of Girvan-Newman Algorithm for Community Detection with Larger Cumulative Modularity Score

The Edge Betweenness-based Girvan-Newman algorithm for community detection is an iterative algorithm that removes one edge per iteration (the edge with the largest betweenness at the beginning of the iteration is removed) and computes the cumulative modularity score of the resulting component(s); as before, each component is considered a community. The partition that incurs the largest cumulative modularity score is kept track of during each iteration.