# A Graph-Cut-Based Approach to Community Detection in Networks
## 3 Methods
### The Divide-Into-Two Algorithm  
To find a community structure of a given network, the proposed algorithm of this paper iterates by dividing a group of vertices into two smaller groups until a stopping criterion is satisfied. Before the algorithm is described precisely, we present the procedure of dividing a group of vertices into two smaller groups in Algorithm 1, called DIVIDE-INTO-TWO.  
```
Input: A connected graph \(G=(V,E)\) Output:\(C=\{C_{1},C_{2}\}\), a partition of \(G\)
1:procedureDIVIDE-INTO-TWO(\(G\))
2:if\(|V|\leq 1\)then
3:\(C\leftarrow\{V\}\)
4:else
5: Compute betweenness centrality \(c_{B}(v)\) for all \(v\in V\)
6:\(s\leftarrow\text{arg max}_{v\in V}c_{B}(v)\)
7:\(t\leftarrow\text{arg max}_{v\in V\setminus\{s\}}c_{B}(v)\)
8:\(S\leftarrow\{v\in V\,|\,\{s,v\}\in E\}\)
9:\(T\leftarrow\{v\in V\,|\,\{t,v\}\in E\}\)
10:for all\(\{u,v\}\in E\)do
11:\(c_{uv}\gets 1\)
12:endfor
13:for all\(v\in S\)do
14:if\(v\
otin T\cup\{t\}\)then
15:\(c_{sv}\leftarrow\infty\)
16:endif
17:endfor
18:for all\(v\in T\)do
19:if\(v\
otin S\cup\{s\}\)then
20:\(c_{tv}\leftarrow\infty\)
21:endif
22:endfor
23:\(C\leftarrow\text{MINIMUM-CUT}(G,c,s,t)\)
24:endif
25:endprocedure
```  
**Algorithm 1** The DIVIDE-INTO-TWO algorithm  
After the source \(s\) and sink \(t\) are selected by the betweenness centrality computation, DIVIDE-INTO-TWO initializes the capacity values of all the edges of the network to be one. Then, it assigns infinity as the capacity to the edges that are connected to the source or sink vertices. This assignment is to prevent the edges connected to \(s\) or \(t\) from being cut by MINIMUM-CUT. The procedure forms a group of vertices \(S\) and \(T\), where vertices of \(S\) and \(T\) are neighbors of the source and sink nodes, respectively. The capacity value of infinity makes the vertices of groups \(S\) or \(T\) strongly connected to themselves, which prevents the edges from being cut by MINIMUM-CUT. All the other edges remain with a capacity of one, as initialized.  
When assigning infinity as a capacity value to edges, it should be avoided that the source \(s\) and sink \(t\) are connected by a path whose every edge has infinity as its capacity value. If there is any path connecting the source and sink vertices where all the edges of the path have infinity as capacity, then MINIMUM-CUT cannot find a cut set of finite minimum cut value. To carefully assign infinity as capacity, DIVIDE-INTO-TWO checks whether the other vertex belongs to \(S\) or \(T\), as described precisely in Algorithm 1.  
Computing the betweenness centralities via [PERSON] algorithm takes \(O(|V||E|)\) time, while the MINIMUM-CUT procedure takes \(O(|V||E|+|V|^{2}\log|V|)\) time when using the Stoer-Wagner algorithm. The Stoer-Wagner algorithm is one of the fast algorithms for finding a minimum cut from a graph. Considering these time complexities, the DIVIDE-INTO-TWO algorithm has the same time complexity as MINIMUM-CUT. Note that all the other executions of DIVIDE-INTO-TWO except for the two main procedures can be performed in linear time. For example, selecting the source and sink vertices and forming the two sets \(S\) and \(T\) can be done in linear time. Assigning capacity values to all the edges also takes linear time.