Multiobjective Group Search Optimization Approach for Community Detection in Networks

2. Literature Review

Detecting perfect communities of closely knit entities from complex networks have always been a keen area of interests among researchers. Figure 1 illustrate the broad categorization of the core algorithmic techniques discussed in literature for the related problem.

Figure 1.

Broad categorization of community detection methods

The initial methods to detect communities were structural which focused on finding a specific structure like cliques (fully connected subgraph), K-cores (K number of connections for a node in a subgraph) or n-cliques. These methods forced various structural restrictions on the networks and failed to evolve communities where cliquish structures or K- connections were missing.

Closely related to Community Detection methods are graph partitioning methods (Alpert et al., 1999). The classic graph partitioning methods aims at finding either balanced or equal sized partitions. The graph partitioning based methods consists of Spectral Bisection (Pothens et al., 1990) and Kernighan-Lin (KL) (Kernighan & Lin, 1970) algorithms. Spectral Bisection initially divides a network into two communities and iteratively bisect them to generate multiple communities. KL algorithm divides the overall network into two groups of randomly chosen vertices and tries to maximize a quality function q by repeatedly swapping the vertices. Spectral Bisection requires the number of communities to be fixed a-priori and KL algorithm require sizes of the groups to be fixed a-priori.