# A Graph-Cut-Based Approach to Community Detection in Networks
## 3 Methods
### The Proposed Algorithm  
The proposed algorithm is a divisive one, so that a given network is divided into groups of vertices in a stepwise manner. The main idea of the algorithm is that a connected network may be partitioned into two subgroups by finding a minimum cut separating the two, which is expected to reveal a good community structure of the given network. After a division of each connected component of a network, the \(Q\) value for the resulting community structure is calculated. By comparing the resulting \(Q\) value for every connected component, the algorithm selects the best partition and creates two communities out of the selected component. The algorithm iterates this process until no further improvement in the modularity value is observed. The algorithm is named MCCD (Minimum Cut-based Community Detection) and is presented precisely in Algorithm 2. ```
1:Input: A connected graph \(G=(V,E)\)
2:Output:\(C=\{C_{1},\ldots,C_{k}\}\), a community structure of \(G\)
3:procedureMCCD(\(G\))
4:\(C\leftarrow\{V\}\)
5:\(Q\gets 0\)
6:loop
7:if\(|C|=|V|\)then
8:break
9:endif
10:for\(i\gets 1\) to \(|C|\)do
11:\(\{C_{i1},C_{i2}\}\leftarrow\) DIVIDE-INTO-TWO(\(C_{i}\), \(E(C_{i})\))
12:\(Q_{i}\gets Q\Big{(}\{C_{1},\ldots,C_{i-1},C_{i1},C_{i2},C_{i+1},\ldots,C_ {|C|}\};G\Big{)}\)
13:endfor
14:\(m\leftarrow\) arg \(\max_{i}Q_{i}\)
15:if\(Q>Q_{m}\)then
16:break
17:endif
18:\(C\leftarrow\{C_{1},\ldots,C_{m-1},C_{m1},C_{m2},C_{m+1},\ldots,C_{|C|}\}\)
19:\(Q\gets Q_{m}\)
20:endloop
21:endprocedure
```  
**Algorithm 2** The MCCD algorithm Note that the locally optimal partition \(\{C_{1},\ldots,C_{m-1},C_{m1},C_{m2},C_{m+1},\ldots,C_{|C|}\}\), where \(m=\arg\max_{i}Q_{i}\), is selected at each iteration of the MCCD algorithm. The iteration repeats until a decrease in the modularity \(Q\) value is observed or each vertex has its own community, i.e., the entire network is partitioned into one-vertex communities. As illustrated in Section 4, however, the \(Q\) value starts decreasing after only a few iterations for many networks. In other words, many networks are expected to have a community structure consisting of not so many communities. Even though the MCCD algorithm stops its iteration of dividing each community into two smaller communities when it detects decreasing \(Q\) values, it is also possible to continue the iteration until a desired number of communities are obtained, via a slight modification of the algorithm. This modified algorithm is precisely presented in Algorithm 3 and is called \(k\)-MCCD. The desired number of communities \(k\), which is given as an input, is assumed to satisfy \(1\leq k\leq|V|\). As presented in Algorithm 3, \(k\)-MCCD stops its iterations when the number of communities reaches the desired number \(k\). ```
0: A connected graph \(G=(V,E)\) and a desired number of communities \(k\)
0:\(C=\{C_{1},\ldots,C_{k}\}\), a community structure of \(G\)
1:procedure\(k\)-MCCD(\(G,k\))
2:\(C\leftarrow\{V\}\)
3:\(Q\gets 0\)
4:loop
5:if\(|C|=k\)then
6:break
7:endif
8:for\(i\gets 1\) to \(|C|\)do
9:\(\{C_{i1},C_{i2}\}\leftarrow\) DIVIDE-INTO-TWO(\(C_{i}\), \(E(C_{i})\))
10:\(Q_{i}\gets Q\Big{(}\{C_{1},\ldots,C_{i-1},C_{i1},C_{i2},C_{i+1},\ldots,C_{| C|}\};G\Big{)}\)
11:endfor
12:\(m\leftarrow\arg\max_{i}Q_{i}\)
13:\(C\leftarrow\{C_{1},\ldots,C_{m-1},C_{m1},C_{m2},C_{m+1},\ldots,C_{|C|}\}\)
14:\(Q\gets Q_{m}\)
15:endloop
16:endprocedure
```  
**Algorithm 3** The \(k\)-MCCD algorithm  
As mentioned previously, the procedure DIVIDE-INTO-TWO has the time complexity of \(O(|V||E|+|V|^{2}\log|V|)\). Therefore, when MCCD calls DIVIDE-INTO-TWO(\(C_{i}\), \(E(C_{i})\)) for a community \(C_{i}\), it takes \(O(|C_{i}||E(C_{i})|+|C_{i}|^{2}\log|C_{i}|)\) time.