# A Graph-Cut-Based Approach to Community Detection in Networks
## 4 Results
### Example 2: [PERSON]'s Karate Club Network  
One of the frequently used real-world network data is [PERSON]'s karate club network [PERSON] (1976). The karate club network represents social interactions between 34 individuals, who were the members of a karate club at a university. [PERSON] obtained the network data by observing social interactions between the members for a period of three years from 1970 to 1972. Before the study began, the club had employed an instructor ([PERSON]) for karate lessons. At the beginning of the study, there was a conflict between the instructor and the club president ([PERSON]) over the price of karate lessons. The instructor wished to raise prices while the president wanted to stabilize them. As time passed, there arose a series of factional confrontations, and then the president fired the instructor for attempting to raise lesson prices unilaterally. The supporters of the instructor resigned and formed a new organization headed by the instructor, thus completing the fission of the club. Figure 3a shows the karate club network, where each vertex represents a member of the club. Vertices 0 and 33 represent the instructor and the president, respectively; the members who belong to the group headed by the instructor after the fission are represented by blue square vertices and the members who belong to the other group are represented by orange circle vertices. An edge of the network is drawn if two individuals were observed to interact outside the normal activities of the club, i.e., if they could be said to be friends outside the club activities. Figure 3: _Cont._  
The result of the proposed MCCD algorithm is shown in Figure 3b. Comparing the result with the data shown in Figure 3a, only one vertex, which is labeled 8, is misclassified by MCCD; vertex 8 joined the organization headed by the instructor after the fission, but the MCCD algorithm predicts that it belongs to the other group. Therefore, it can be said that MCCD works well for the karate club network. Figure 3c shows the betweenness centrality values \(c_{B}(v)\) for the vertices of the network. As expected, the instructor and the president nodes have the highest values, so MCCD selects the two vertices as the _source_ and _sink_ nodes at its first iteration. The modularity values after each iteration of MCCD are shown in Figure 3d. The modularity value achieves its maximum value of 0.3715 after the first iteration, and the values quickly decrease as MCCD iterates its DIVIDE-INTO-TWO procedures. To model information flow in the karate club, [PERSON] defined a capacitated network for the club, which includes a capacity matrix \(C\) whose entries are interpreted as representing a capacity or value of maximum possible information flow between two members of the club [7]. In other words, each edge of the network has a quantified value representing the strength/weakness of friend relationship between the two end vertices. These capacity values were assigned by analyzing data of social interactions between the club members. Using this capacitated network model, [PERSON] employed the max-flow min-cut theory and applied the labeling procedure of [PERSON] [58,70,71]. To apply the algorithm, the vertices 0 and 33 of the network were manually designated as the _source_ and _sink_ nodes. [PERSON] obtained the same result as MCCD, which is expected, and explained why vertex 8 is misclassified [7]. One point to note is that, contrary to [PERSON]'s method, MCCD automatically selects the source and sink nodes and iterates the DIVIDE-INTO-TWO operation to find the best result for community detection. Many community detection algorithms that have been proposed previously used the karate club network data to verify their performances, and the modularity results of a few well-known algorithms are shown in Table 1. Most algorithms result in higher modularity values than MCCD, but the ground truth of the karate club network has the modularity value of 0.371 [6].