Multiobjective Group Search Optimization Approach for Community Detection in Networks

Multiobjective Group Search Optimization Approach for Community Detection in Networks

Nidhi Arora (Kalindi College, University of Delhi, Delhi, India) and Hema Banati (Dyal Singh College, University of Delhi, Delhi, India)
Copyright: © 2016 |Pages: 21
DOI: 10.4018/IJAEC.2016070103


Various evolving approaches have been extensively applied to evolve densely connected communities in complex networks. However these techniques have been primarily single objective optimization techniques, which optimize only a specific feature of the network missing on other important features. Multiobjective optimization techniques can overcome this drawback by simultaneously optimizing multiple features of a network. This paper proposes MGSO, a multiobjective variant of Group Search Optimization (GSO) algorithm to globally search and evolve densely connected communities. It uses inherent animal food searching behavior of GSO to simultaneously optimize two negatively correlated objective functions and overcomes the drawbacks of single objective based CD algorithms. The algorithm reduces random initializations which results in fast convergence. It was applied on 6 real world and 33 synthetic network datasets and results were compared with varied state of the art community detection algorithms. The results established show the efficacy of MGSO to find accurate community structures.
Article Preview

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.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2019): Forthcoming, Available for Pre-Order
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing