# A Graph-Cut-Based Approach to Community Detection in Networks
## 2 Prior Works  
Uncovering community structures inherent in networks can shed light on many aspects of our world because networks can model various relations and inner workings among entities and objects. Therefore, community detection in networks has received a lot of attention from many fields [2, 3, 4, 5, 6, 7], and it is rapidly evolving. Scientists and researchers from various fields have accordingly produced a large number of research articles and study results. The community detection problem has been studied mainly for static networks, but the problem has also been studied for dynamic networks as well as overlapping communities recently [8, 9, 10, 11, 12, 13, 14]. At their initial development phase, community detection algorithms concerned disjoint communities, where each vertex of a network belongs to only one community. However, many real-world networks such as social networks can have overlapping communities, so that a vertex is permitted to belong to several communities at the same time. Even though the problems for dynamic networks or overlapping communities are interesting and worth tackling, this paper limits its scope to methods for disjoint community detection of static networks. Since it is unrealistic to review all the previously proposed algorithms for community detection, only a few representative algorithms are mentioned in this section. More detailed reviews and studies regarding community detection can be accessed through several extensive review articles and books [2, 3, 4, 5, 15, 16, 17]. Even though many algorithms for community detection have been proposed so far, it seems that there is no single algorithm that can detect communities universally well for many kinds of various networks [18, 19]. Therefore, it is believed to be better to have multiple different algorithms and the apply suitable one to each particular network. Most algorithms proposed for disjoint community detection of static networks may be classified into three categories: traditional, modularity-based, and dynamic algorithms [2]. Traditional algorithms include hierarchical clustering [1, 20, 21, 22, 23, 24], Girvan-Newman (GN) algorithms [25, 26, 27, 28] and their variants [29, 30, 31], spectral clustering [32, 33, 34, 35, 36, 37, 38, 39], and graph-partitioning-based algorithms [39, 40]. Most of these algorithms are based on clustering, and they have provided basic concepts of community detection for later developments. Modularity-based algorithms include the Guimera and Amaral algorithm [41], the fast GN algorithm [27], the Clauset algorithm [42], optimization-based algorithms [43, 44, 45, 25, 46], and genetic algorithms [47, 48, 49, 50, 51]. The concept of modularity was introduced by [PERSON] and [PERSON] [25], and modularity-based algorithms try to optimize the modularity value by finding a good community structure in a network via some heuristics. The concept of modularity is briefly reviewed in Section 3. Dynamic algorithms include those that are based on spin models, random walk, and synchronization. A random walk can be used for community detection by letting an entity make random moves along the edges of a network [52; 53; 54; 55]. More details on dynamic algorithms can be found in review papers and books [2; 3; 4; 5]. Since many algorithms and methods for community detection have been proposed, the task of evaluating them becomes important as well. To measure the performance of the algorithms and methods, a few standard benchmarks of complex networks with known community structures have been devised. Among these benchmarks, the GN and LFR (Lancichinetti, Fortunato, and Radicchi) benchmarks are frequently used [56; 57]. These benchmark networks are synthesized with predetermined community structures, and an algorithm is evaluated by comparing the result of community detection to the known answer, i.e., the predetermined community structure. Besides these synthetic benchmarks, there are some real-world network data that are frequently used to evaluate community detection algorithms.