# A Graph-Cut-Based Approach to Community Detection in Networks
## 3 Methods
### Modularity: A Quality Measure  
In most practical cases, community detection algorithms are applied to a network whose community structure is not known ahead of time. Therefore, it is necessary to have a quality measure to evaluate a community structure derived by a community detection algorithm. In other words, we need a measure to answer the question of how well the found community structure represents the underlying connection characteristics of the network.  
Even though a quality measure of community structure is needed, there exists one difficulty in defining such a measure. There is no pre-defined precise answer for the community structure of a given network; two people may have different opinions about the inherent community structure of the same network. It is hard to say that a community structure of a network is strictly better than another community structure of the same network. Examples that illustrate this difficulty are presented in Section 4.  
Although it is difficult to find a well-defined and unified quality measure to evaluate a particular division of a given network, some measures have been proposed so far. One of the widely used measures is _modularity_[25]. The modularity measure is defined as follows.  
**Definition 7**: _Given a network \(G=(V,E)\) with a community structure \(C=\{C_{1},C_{2},\ldots,C_{k}\}\), a \(k\times k\) symmetric matrix \(M\) is defined, where each element \(M_{ij}\) for \(i,j=1,\ldots,k\) is the fraction of all edges that connect vertices in community \(i\) to vertices in community \(j\). Then, the modularity measure \(Q\) of the community structure \(C\) of the network \(G\) is defined by_  
\[Q(C;G)=\operatorname{Tr}M-\left\|M^{2}\right\|\!, \tag{2}\]  
_where \(\|X\|\) is the sum of the elements of the matrix \(X\)._  
Note that the row sum \(m_{i}=\sum_{j}M_{ij}\) of the matrix \(M\) represents the fraction of edges that have at least one vertex in community \(i\) at its endpoints. If all the pre-existing edges are removed and new edges are randomly placed between vertices while preserving the row sums, the expected fraction of all the new edges that connect vertices in community \(i\) and vertices in community \(j\) equals \(m_{i}\cdot m_{j}\). Therefore, the difference between the pre-existing and the expected fraction, \(M_{ii}-m_{i}^{2}\), may be used as an indication of how strongly the vertices in the community \(i\) are connected to each other. In other words, it can measure how densely the vertices in the community \(i\) are linked. By adding these differences for all the \(k\) communities, the modularity measure can be defined as  
\[Q=\sum_{i=1}^{k}\left(M_{ii}-m_{i}^{2}\right), \tag{3}\]  
which is shown to be equal to the right side of Equation (2).  
The maximum value that \(Q\) can have is \(Q=1\), and this value indicates a network with a very strong community structure [25, 66]. The modularity \(Q\) values for networks with strong community structure usually range from about 0.3 to 0.7.  
Our proposed algorithm computes the modularity value after each division of the given network via graph cuts, and it determines the next step based on the calculated \(Q\) values. In particular, the \(Q\) value is used as a stopping criterion to stop iterations of community division. Therefore, the \(Q\) values are critical for the algorithm.