1 Introduction

1.1 Overview

Nowadays, most of the complex real-world systems in the fields of biology, sociology, and engineering can be captured and investigated as networks of connected communities. However, the suitability of networks to represent these real-world systems has given an impressive spur to complex networks research. Some of the examples of complex networks include collaboration networks, communication networks, biological networks, transport networks, the world-wide-web, the internet, paper citation networks, neural networks, as well as metabolic and Protein-Protein Interaction networks (PPI) [1,2,3]. Generally, complex networks are a graphical representation of all the objects in a given system, where the nodes of the network represent objects, and a link between two objects represents the activities among them [4, 5]. For example, the biological collaboration between proteins can shape PPI networks, where the nodes match with the proteins and the edges match with the physical or functional interactions between them. In social networks (SNs), individuals or objects can be human beings, books, or animals. Factors such as common interest, statistical commonality or other forms of social relations, are representing connections among network’s objects. A tight intra-connection, coupled with loose inter-connections, is a key feature of the complex networks that is observed as a common tendency among entities of these communities.

In summary, community detection (CD) is a network analysis technique that seeks to detect the hidden structure of a large-scale networked dataset into separate and compact groups, where the number and size of subgroups are unknown [6]. However, the lack of a universal definition for these community structures is considered to be one of the major challenges of the field [7]. Which means that the CD problem is a fundamental issue in computer science and an ongoing challenge because many network problems like aligning, detecting, and the search for relationships are equivalent to the subgraph isomorphism problem which is known to be NP-hard that recently enjoyed a considerable interest [8,9,10]. This ultimately leads to the fact that optimal solutions are impossible to be found for all the complex networks and the quality of a solution depends strongly on the algorithm and its contents (representation, objective functions, and problem-specific operators). Due to an increase in network complexity and the consequent exponential growth of the solutions space, the typical, conventional or classical methods are no longer a sustainable form of solution. Thus, Nature Inspired Algorithms (NIAs) have been adopted in order to deal with the relevant issues and challenges of community detection. This fact has made NIAs an attractive solution and research area for dealing with complex problems by providing an effective methodology that is superior to other competing methods.

Generally, NIAs are global metaheuristic (MH) algorithms that have common characteristics. One of the first notes of interest is focusing on encoding schemes or the method in which the solutions represent inside nature-inspired community detection algorithms. This can be done via randomly sampling the search space of the problem as different candidate solutions. Consequently, these solutions are optimized in terms of single objective or multi-objective functions. Besides this key part, solution representation, there are also two key components for any metaheuristic algorithm, these are intensification and diversification which are also referred to as exploitation and exploration. Both of these concepts refer to how the search is performed. While diversification focuses on a global space to generate diverse solutions, the intensification would focus on a local space and exploiting the information available in this region, rather than a global one. Intensification aims on developing the good solutions found, for which it has to go through a selection phase in order to identify the optimal or best solution, while diversification, on the other hand, aims on increasing the diversity of the solutions via randomization, which aims on preventing the solution to be trapped in the local optimal region. Combining the two strategies allows for the solution to reach an efficiency peak which is identified and selected from a global space [11].

Metaheuristic algorithms can be classified in many ways. One way is to classify them as population-based or trajectory-based. For example, the genetic algorithm, particle swarm optimization, firefly algorithm, or the cuckoo search, are classified as a population-based algorithm. The population changes depending on the type of algorithm, while some algorithms use chromosomes as population individuals, others use particles or multiple agents as their population. There are also other avenues which they operate through a single agent, rather than multiple agents. One kind of this search is Simulated Annealing (SA) that mimics the annealing process of metals. The steps or moves trace a trajectory in the search space, with a nonzero probability that this trajectory can reach the global optimum [11].

This review focuses mainly on nature-inspired community detection algorithms that belong to the population-based category, as they are naturally parallel and efficient implementations can be realized to deal with large size networks.

1.2 Review methodology

In order to conduct this review, papers were collected from the year 2007 until 2019. We have performed a multidisciplinary search to find relevant literature on the community detection studies based on NIAs and their issues by using the keywords “community detection”, “Evolutionary and Genetic Algorithms; Memetic Algorithm; Particle Swarm Optimization; Differential Evolution; Cultural Algorithm; Firefly Algorithm; Bat Algorithm; Ant/Bee Colony Optimization; and Cuckoo Search Algorithm”, “open issues and challenges to community detection algorithms” and network pattern “signed/unsigned, static/dynamic, joint/disjoint, and multidimensional”. Then, relevant papers and articles were selected from the initial search, based on the criteria that papers were published in peer-reviewed journals or conferences and have focused on community detection based on NIA algorithm. From the papers obtained from various libraries, 30% are from conference papers, and the remaining 70% are from journals. The inclusion of conference papers was necessary due to the fact that some of the state-of-the-art techniques are presented often in conferences before they are fully turned into journals, thus, they provide a good source of identifying the direction of the research in the long term. On that note, most of the collected papers are WOS rather than Scopus, with roughly 84% of the journals being from WOS. This ensures that only high-quality techniques and journals are selected, but also includes those that provide a pattern of research.

The NIAs selected are based on a book by Yang [11], that strived to introduce the latest developments regarding all major nature-inspired algorithms, including genetic algorithms, differential evolution, as well as swarm-intelligence-based algorithms (such as particle swarm optimization and firefly algorithm), and others.

1.3 Goal and outline of paper

Community detection is a growing research domain that has a large role in solving various real-life complex problems. There are several published reviews, articles, studies, books and journals on the topic of community detection and its various methods and applications. The majority of the published reviews focus on a particular type of networks, such as social networks [12,13,14], delay tolerant networks [15], mobile phone networks [16], dynamic network [17], and others. There are other reviews based on different concepts relevant to the community detection issue such as: disjoint/overlapping communities detection and their applications in Javed et al. [18], metrics for community analysis in Chakraborty et al. [19] and evolutionary computation in Cai et al. [20] and Pizzuti [21]. In general, research on CD has a multidisciplinary nature coming from the graph theory, physics, statistics, and data mining, and this made researchers face difficulties in locating information about CD since there are many important references in various primarily related disciplines, and in particular, despite the availability of several surveys in the literature that fuels the researcher with valuable and useful information about community detection problem, there is still a lack of literature that gives a macroscopic view on NIAs-based community detection. Hence, it is so difficult to get knowledgeable about basic concepts, general developments, historical analyses, and future trends in the relevant field, and this is the very motivation for this review. In this paper, we have explored the studies collected from various libraries, most of them are WOS to get acquainted with the performance of research published in the domain, and moreover, to track its temporal evolution, and later identifying basic characteristics of the components of the proposed approaches through statistical analysis.

More specifically, this paper aims to perform a systematic study that reviews CD studies based on the NIAs perspective and summarizing them from different aspects such as representation, crossover, mutation, fitness function employed and type of network model viz. signed/unsigned, static/dynamic, joint/disjoint, and multidimensional. As well as providing challenges and open issues that relate to community detection algorithms, thus there is a need and requirement to produce such a survey. Finally, future trends, pathways, and research gaps are provided at the end of the research which aids other researchers in further analyze and evolve the domain.

1.4 Paper organization

This study is organized as follows: in Sect. 2 the definition of community detection in the context of complex networks is presented. The next section introduces a list of NIAs used for CD, followed by historical and statistical analysis of the relevant researches as well as highlighting the issues, challenges, and recent trends that the CD is currently facing. The final section presents a concluding remark on the whole review and provides insight into further research.

2 Community detection in complex networks

Communities in a complex network are groups of nodes, which are more intensely connected to one another when compared to the rest of the nodes in the network. Colmmunity detection is the key characteristic, which could be used to extract useful information from networks. It allows us to concentrate on the regions with some degree of autonomy within a graph. For example, it could be possible to distinguish vertices which are completely embedded within their clusters from those that are at the cluster boundary which may serve as brokers between the modules and as such, could play a significant role both in holding the modules together and in the way of spreading the processes across the network. The greatest challenge in community detection is that there are no commonly accepted protocols on the fundamental ingredients of the community itself. Therefore, community detection in large-scale networks is computationally intractable [7, 22]. These communities are composed of different densities of connections and functionality as well as a different number of nodes. The connection among nodes of the complex network can take different patterns, such as unsigned/signed in SN, static/dynamic in both social and biological networks. One way of detecting community in an unsigned social network is to consider pairs of nodes as connected and as if they are positively correlated. Such a network is said to be an unsigned network since the correlation sign is not important; even strongly negatively correlated nodes can be assumed as unconnected. As for CD in signed networks, it can be defined as an extension to the complex unsigned networks with additional positive and negative information to the connections. Communities in signed networks are not only defined by their link density but also by their link tendencies. Examples of such signed relationships are like-dislike, friendship-enmity, attraction-discouragement, agreement-disagreement, or more generally, positive-negative relationships. Slashdot news review site, Epinions consumer review site, and Wikipedia vote site are some examples of this kind of network where the relationships that representing the attitude between pairs of entities in these complex networks can’t be only positive (i.e. like) but also negative (i.e. dislike), and more intricate than the relationships in the conventional social networks [23]. Detecting the community structure at these types of networks is necessary as it reflects real social networks more realistically and allows for the determination of instabilities within the relationships, and thus, the prediction of the changes in the organization of group [21]. Another important method for analyzing networks with dynamic behavior is to analyze their evolutions over time. In fact, dynamic networks capture the changes in interconnectivity over time and allow tracing the network structure changes at different times. Thus, in the absence of any dynamic behavior, the detection will be no different than a CD in a static network, which is considered to be a relatively easier task than a CD in a dynamic network. Most studies concentrated on community tracking agree on a set of simple events that relevant to the dynamic network entities: node/edge appearing and vanishing. Such atomic and local actions can result in perturbations of the network structure at different moments in time [17]. There are continuous and ever-growing applications for CD in a dynamic network such as directions analysis in the social fields, the prediction of dynamic links, and clustering social media subscribers for good advertisement as well as facilitating the recommendations to readers, and so on [18]. Similarly, in PPI networks, detecting dynamic protein complexes can provide valuable information for therapeutic purposes through detecting proteins that carry out their functions dynamically in multiple consecutive conserved across different time-points [24].

Multilayered networks are a result of the interconnections of systems that have multiple types of connections [25,26,27]. Each layer represents a combination of different features of the network. As pointed out in Battiston et al. [26] and Kivelä et al. [27], networks with multiple types of connections provide a much more understanding of a system than monoplex networks, generated by the aggregation of these mutual interactions on a single kind of link, since each interaction can have different roles and meaning. Online social networks are intrinsically multi-dimensional since people connect and interact with each other by using a variety of social media, e-mail messages, or mobile telephone calls, and perform different activities that result in multiple relations, and consequently, multidimensional networks generate.

Generally, the presence of community structure in the social networks has enabled a wide variety of applications such as discovering fraudulent telecommunication networks activities, detecting fraudulent websites, designing network protocols in delay tolerant networks, refactoring software packages, skill acquisition in robots, dimensionality reduction in pattern recognition, and recommendation systems [4]. While from the biological side, protein complex prediction is an important issue as it provides valuable information about complex biological mechanisms in the cell, drug design, and diseases, as well as prediction of the biological functions of uncharacterized proteins and cancer detection [28].

Moreover, in real-world networks, the membership of an entity can either belong to only one community and the process is called detecting disjoint communities or can belong to several communities, so the process called detection of overlapping communities. In overlapping community detection, some individuals should be allocated into multiple groups such as a person simultaneously belongs to several groups i.e. family group, friends and colleagues group or any other interest group; as well as, in the PPI network, a protein may participate in different biological functions, thus it belonging to different complexes. Figure 1 exhibits the community detection problem under different network scenarios, in which the complex network represented as a graph that is composed of \( n \) nodes and \( e \) edges. As well as some visual examples of communities in social and biological networks are illustrated in Fig. 2 [29]. From Fig. 1 we can notice that community detection under dynamic and multilayer pattern are quite different from others. In the dynamic pattern, the community structure changes based on the time (t); while in the multilayer pattern, the network structure includes communities having different types of interactions, where designing NIAs to uncover these patterns of communities deemed a major challenging. In light of all the above-mentioned connection patterns of complex networks, a large number of nature-inspired community detection algorithms have been proposed to find optimal communities in reasonably fast time, more details in the next section.

Fig. 1
figure 1

Graphical illustration of CD. Classic common model (top left): represents an example network with two disjoint communities. Overlapping model (2nd top): represents an example network with two communities share boundary vertices, distinguished by the blue color. Signed model (top right): represents an example signed network with two communities having solid edges denote positive connections, and dashed edges denote negative connections. Dynamic model (middle): represents an example network with two communities that their structures change based on the time (t). Multilayered model (bottom): represents an example network (a) with two communities having three different types of interactions (b–d) respectively (Color figure online)

Full size image
Fig. 2
figure 2

Adapted from: [29]

Visual examples of communities in complex networks of different domains. Social networks (a Slashdot, b Epinions) that appearing on average fairly homogeneous. While in biological networks, the sets of protein-protein interactions of two organisms: a fruit fly (D. melanogaster), and b man (H. sapiens), the larger the community, the less tree-like it is.

Full size image

3 Community detection approaches: taxonomy based on NIAs

In today’s world, nature-inspired metaheuristic algorithms, especially those based on evolutionary computation, have attracted much attention to address the community detection problem and their literature has expanded dramatically with diverse applications. One of the key principles that these techniques have in common is that they are self-organizing. This feature refers to the capability of being able to evolve and eventually, after a while, self-organizing structures emerge from the system [11].

Recently, many researchers have been trying to reach optimal solutions for the problems of CD in many network types. With the search continues and progresses, a desire for developing more universally and robust algorithms increased to address the CD issues in an efficient manner. However, designing an efficient algorithm mainly based on the objective function which can be either single objective optimization (SOO), or multi-objective optimization (MOO), depending on the requirements of the research. There are advantages and disadvantages to each of these objective functions. However, regardless of the number of criteria that are used, all of these techniques share a single principle. This principle is that all these techniques are derived in one way or another from nature or an observed behavior in nature. Whether this inspiration is on the solutions representation, the crossover, mutation, or selection operators, is dependent on the technique, but the general principle remains the same. To further elaborate on these aspects:

  • Encoding schemes: the success of an algorithm is highly dependent on its solution representation. There are several existing methods and techniques that correspond to the encoding of the division of a network in a sub-graph. These representations are often adapted from the encoding used to solve the classical data clustering problem with evolutionary methods. When designing a CD model, there needs to be an emphasis on the method in which the network is partitioned, as well as finding a way to automatically identify the number of communities.

  • Crossover (\( X \)) is regarded as a macroscopic operation on individuals. Essentially, it is used for mixing with subspace and aid in making the system converge.

  • Mutation is regarded as a microcosmic operation on individuals. While crossover focuses on the macro and the convergence, the mutation provides the main mechanism for global search. It can be generalized as a randomization or heuristic technique.

  • Selection is an important aspect that is imperative to the system’s evolution and moving forward to its next step, which pushes the system towards its optimal state. It is essentially intensive exploitation [11]. Moreover, in most studies, Heuristic Operator (HO) is being proposed to improve the quality of the community division by reducing research blindness and guiding the research process towards promising regions.

Based on existing research, there are several ways in which the CD studies can be classified. However, in tandem with the scope of this research, we propose a classification that would be based on the context of NIAs with the summarization of the significant common characteristics of these nature-inspired community detection studies. As well as trying to understand the reason behind the effectiveness of NIAs as a solution for issues faced in CD.

The following sections are a classification of NIAs and the various solution within. The way each of these categories is structured, is first an overview of the solution and its behavior, followed by their applicability on the CD problem. Each section also links to a table that lists and summarizes the studies according to techniques properties. These properties are: network type and its pattern connection, model employed, solution representation, and perturbation operators in terms of crossover and mutation, along with, if present, heuristic operators which adopted to improve the methods. The goal of this section is to provide an unbiased overview and an understanding of the various categories of NIAs as a tool used by researchers to solve the problem.

3.1 Evolutionary and genetic algorithms (EA/GA)

Evolutionary algorithms (EAs) and especially Genetic algorithms (GAs) are algorithms that revolve around generating a random population. This creates a finite number of individuals, which is in a GA scenario are called chromosomes. The structure of the aforementioned chromosomes depends on the problem that the GA is attempting to address. The quality of such entities, commonly known as chromosomes, is assessed via an objective function. This ultimately leads to fitness values of the chromosomes, then a percentage of chromosomes that have the highest fitness values are selected for the next iteration. Genetic operators of crossover and mutation are applied to the chromosomes to achieve a better population. The crossover and mutation operations are repeated until the termination criteria are met [8]. At the termination step, the algorithm produces the optimal solution(s). Essentially, GAs and EAs are efficient techniques to find the optimal solution, when compared to existing classical and traditional methods for solving NP-complete problems. This is mainly due to its robustness, operating on various representation, and good for noisy and dynamic problems. Table 1 lists studies based EA and GA that classified under the MOO, while Table 2 lists those that are SOO.

Table 1 Summarization of MOO studies based on EAs & GAs
Full size table
Table 2 Summarization of SOO studies based on EAs & GAs
Full size table

3.2 Memetic algorithms (MAs)

Memetic algorithms (MAs) were named in Moscato [30], which are evolutionary algorithms that interspersed the recombination of high-quality solutions with periods of intensive individual optimization. The denomination “memetic” for this type of algorithms was inspired by Dawkin’s concept of a meme, which represents a unit of cultural evolution that can exhibit local refinement. In MAs, a meme is generally considered as an individual learning procedure capable of performing local refinements. Many works of literature refer to memetic algorithms as an extension or hybridization of the previous genetic algorithm techniques, since it relies on evolution as a basic principle. This is ultimately due to the fact that MA combines GAs and local search procedures in order to operate. However, when it comes to CD, this technique has been proven to be more effective than traditional Genetic Algorithm on some applications of the problem. Thus, MAs are considered to be a growing and popular topic in both computer science fields and operational research domains [31,32,33]. Table 3 lists the research publications relevant to MA, as well as their related properties.

Table 3 Summarization of SOO & MOO studies based on MAs
Full size table

3.3 Particle swarm optimization (PSO)

Particle swarm optimization (PSO) attracted a large number of researchers to address the CD problem. PSO forms an exciting, ever-expanding research subject, called swarm intelligence that means working with a population of particles, which in this scenario are called a swarm of particles. These particles move and search in the state space of possible solutions in order to identify the optimal solution. The method identifies and marks each particle \( p \) based on two characteristics. The first is its position vector \( x_{p} \) in the search space, and the second is the velocity \( v_{p} \) of the vector itself. Particles are attracted towards the best position of the swarm \( Sbest_{p} \), and its personal best position \( pbest_{p} \) while moving randomly at the same time. The new velocity and position vectors are adjusted according to the following rule:

$$ v_{p}^{t + 1} = v_{p}^{t} + c_{1} \omega_{1} \left( {Sbest_{p} - x_{p}^{t} } \right) + c_{2} \omega_{2} \left( {pbest_{p} - x_{p}^{t} } \right) $$
(1)
$$ x_{p}^{t + 1} = x_{p}^{t} + v_{p}^{t + 1} $$
(2)

where \( c_{1} \) and \( c_{2} \) are acceleration parameters, and \( \omega_{1} \), \( \omega_{2} \) are random numbers taking values from 0-to-1 [34].

Based on predetermined rules, the velocity is adjusted before any movement is made. These rules inspired by the movement of a bird flock or fish school, make use of the best position visited by each particle and the global best solution produced by the swarm to drive particles to a promising region. Due to its simplicity and lack a high-level mathematical necessity, the PSO is considered as one of the most widely used and popular optimization techniques [35, 36]. Table 4 lists the most prominent studies based on PSO techniques, as well as their related properties.

Table 4 Summarization of SOO & MOO studies based on PSO algorithm
Full size table

3.4 Differential evolution (DE)

Differential evolution (DE) exhibited some merits in the optimization of the community detection problem. DE initiates the search with a population, similar to the previous algorithms. A single entity from the population, which is comprised of individuals, is selected and used as the target vector, and it is used to generate the mutant vector by the mutant operation. Basically, this type of algorithm identifies the optimized solution regardless of initial parameter values, it has a fast convergence, as well as requiring only a few control parameters. The performance of this technique is heavily reliant on the mutation scheme, and the control parameters. Although there are different mutation schemes, the following strategies are the most often used [37]: DE/rand/1, DE/best/1, DE/best/2, and DE/rand-to-best/1. The first scheme is often termed with the classic mutation strategy in DE which is based on current individual vector, while the others are variants of perturbations based on the first strategy and also used the information of the best individual in order to accelerate search process and to avoid trapping in a local best individual. While the parameters are simply characteristics required for the method to operate, such as the population size, crossover size, and the scale factor [38, 39]. Table 5 includes a list of publications that use DE as their problem-solving tool.

Table 5 Summarization of SOO studies based on DE algorithm
Full size table

3.5 Cultural algorithm (CA)

Cultural algorithm (CA) was employed as a community detection framework in order to make a knowledge-based system. The key feature of this algorithm is a belief space which stores information about the entities and guides the search direction. In other words, the cultural algorithm is a dual inheritance model which consists of two main spaces, population and culture or belief space. When it comes to CD as a problem domain, each generation of the CA model selects a group of individuals that serve to update the belief spa. Based on defined parameters in the belief space, a new population will be generated. This type of space acts as a global knowledge repository which holds information on the individuals. This knowledge is later used to guide the searching process and identifying the optimal solution. Generally, the optimization process starts by building a population with a certain number of individuals that are randomly generated based on the state space of the complex network. The solution (or individual) consists of a combination of different elements, therefore, the state space of the complex network contains the possible states for each element. After the first generation, the individual(s) with the best fitness value is selected to make a belief space. The belief space is a new state space for the network. Thus, the new individuals are generated based on the belief space. At the same time, the belief space is updated according to the state of the best-selected individual [40]. Table 6 includes a list of research publications that used CA as a tool to solve the CD problem, alongside their relevant properties.

Table 6 Summarization of SOO studies based on CA
Full size table

3.6 Fly algorithm (FA)

Firefly algorithm (FA) is a population-based optimization technique which finds its inspiration in the behavioral influence of fireflies’ flash on their mobility patterns. It assumes that fireflies are unisexual, they are attracted to other fireflies proportionally to their brightness, where the brightness is determined through the perspective of the objective function [41]. In an optimization problem, fireflies move towards brighter points to find a globally optimum solution. However, the performance of FA greatly depends on its parameters such as its attractive coefficients and random movement factor, even though it suffers from the problem of being trapped in its own local optima [42]. A firefly movement can be conceived as a general form of a swarm intelligence solver as:

$$ x_{i}^{t + 1} = x_{i}^{t} + \beta_{0} e^{{ - \gamma r_{ij}^{2} }} (x_{j}^{t} - x_{i}^{t} ) + \alpha e_{i}^{t} $$
(3)

where \( x_{i}^{t} \) represents the \( i - th \) solution (firefly) in the population at iteration \( t. \) The second term in the formula is the attractiveness function with \( r_{ij}^{{}} \) represents the distance between solution \( i\;{\text{and}}\;j \), and \( \beta_{0} ,\;{\text{and}}\;\gamma \) are parameters that balance between the intensifying and diversifying search capabilities of the algorithm. The third term concerns to randomization with parameter \( \alpha \) and \( e_{i}^{t} \) is a vector of random variables. Substantially, the key parts of FA are: the collective behavior, mutual attractiveness and random yet controlled movement of these insects, which applied on an optimization procedure [43]. Some of the research work relevant to FA, used as a tool to address CD problem, are listed in Table 7.

Table 7 Summarization of SOO & MOO studies based on FA
Full size table

3.7 Bat algorithm (BA)

As defined in Yang [44], Bat algorithm (BA) follows the echolocation of bats by using sonar echoes to detect and avoid obstacles. This type of algorithm uses a local search of individuals in order to reach a global optimum. The concept of this algorithm is based on the behavior of bats. The method in which these creatures hunt and prey at night is through echolocation as a means of identification. When the algorithm initiates, each individual or “Bat” would emit pulses, which are used to map the local area around them with a frequency that is low, but with high loudness. As the bat gets closer to its target or prey, the loudness is reduced, and the rate of pulse emission is increased. This frequency/loudness adjustment process can control the balance between the exploration and the exploitation operations of the algorithm [45]. In general terms, BA is a new metaheuristic algorithm that takes inspiration from bats in order to find its desired target solution and operates based on echolocation system to sense distance, the velocity with a fixed frequency, and loudness variations. If \( x_{i} \) is the position of the bat at time \( t \), \( f_{i} \) the frequency that moves between \( f_{min} and f_{max} \), \( v_{i} \) the velocity, i.e. the change degree of its position, \( r \) the emission rate and \( A \) the loudness, these values are updated with the rules:

$$ f_{i} = f_{min} + (f_{max} - f_{min} )\beta , v_{i}^{t + 1} = v_{i}^{t} + \left( {x_{i}^{t} - x^{*} } \right)f_{i} $$
(4)
$$ x_{i}^{t + 1} = x_{i}^{t} + v_{i}^{t} , A_{i}^{t + 1} = \alpha A_{i}^{t} , r_{i}^{t} = r_{i}^{0} \left[ {1 - \exp \left( { - \epsilon t} \right)} \right] $$
(5)

where \( x^{*} \) is the current best solution [21]. Some of the research articles based on BA are listed and summarized in Table 8.

Table 8 Summarization of SOO studies based on BA
Full size table

3.8 Ant/bee colony optimization (ACO/BCO)

Ant colony optimization algorithms (ACO) and bee colony optimization algorithms (BCO) are two popular optimization techniques inspired by ant and bee behavior. ACO metaheuristic consists of a colony of artificial ants constructing solutions iteratively by mimicking the foraging-behavior of social ants. ACO uses pheromone as a chemical messenger and the pheromone concentration as the indicator of quality solutions to a problem of interest. From an implementation point of view, solutions are related to the pheromone concentration, leading to routes and paths marked by the higher pheromone concentrations as better solutions to questions of the problem. Therefore, the two main points in ACO algorithm are the probability of choosing a route and the concentration rate of pheromone, where the probability of choosing a route from node \( i \) to node \( j \) can be expressed by the rule:

$$ p_{ij} = \frac{{\theta_{ij}^{\alpha } h_{ij}^{\beta } }}{{\mathop \sum \nolimits_{i,j = 1}^{n} \theta_{ij}^{\alpha } h_{ij}^{\beta } }} $$
(6)

where the parameters \( \alpha \; {\text{and}}\; \beta \) determine the relative influence of the trail information and the visibility, \( \theta_{ij} \) is the pheromone concentration of the route between \( i\;{\text{and}}\; j \), while \( h_{ij} \) is a heuristic function that reflects the tendency of selecting the edge from \( i \;{\text{to}}\; j \) [46].

Whereas BCO simulates the intelligent foraging behavior of honey bees to solve optimization problems. The model consists of two essential components: the nectar source and the bee colony. A nectar source represents a possible solution to the optimization problem. The nectar amount of a nectar source corresponds to the quality of the solution. The colony of bees consists of three groups of bees: employed bees, onlookers, and scouts which are flying in a D-dimensional search space to find the optimum solution. Employed bees are associated with a particular nectar source which is exploited by employed bees. Onlookers search nectar source which is shared by employed bees. Scouts search new nectar source when a nectar source is abandoned. The search process of BCO is directed by cooperation and conversion of the bee colony, the goal is to find the largest food source [47]. In other words, the BCO optimization algorithm starts with the employee bees that keep a food source in their mind when they leave from the hive to share the food source information with onlookers on dance area. Then, onlookers determine the food source by watching employee bees’ dances and trying to improve this source. An employee bee becomes a scout in case of abandoning the food source in order to explore new food sources randomly. The percentage of scout, employee and experienced employee are usually determined manually [48]. Both ACO and BCO lack to crossover operation that makes them relatively slow when it comes to convergence, but they are effective when it comes to search space exploration. However, the slowness limits the subspace exploitation, in fact, lack of crossover operation is a common occurrence in some metaheuristic algorithms [11]. Table 9 lists some of the ACO and BCO studies proposed as CD optimization models.

Table 9 Summarization of MOO & SOO studies based on ACO/BCO algorithm
Full size table

3.9 Cuckoo search (CS)

At first, Cuckoo search algorithm was proposed by Yang and Deb [49, 50], it is the same other evolutionary algorithms that are population-based search procedure and seeking for the best solutions. After that, a new cuckoo search algorithm is proposed by Yang and Deb [51] for formulating multiobjective optimization problems and for solving structural design problems. The merits of the cuckoo search algorithm, compared with other heuristic algorithms, is that the search process mainly focused on adopting the Lévy flights, employing a combination of vectorized mutation, crossover by permutation, to ensure the possibility and universality of searching the optimal solutions, and the diversity of the new solutions. Studies based on Cuckoo search (CS) algorithm are listed in Table 10.

Table 10 Summarization of MOO & SOO studies based on CS algorithm
Full size table

CS operates by imitating the breeding behavior that is observed in Cuckoos. This type of breeding relies on brood parasitism of some their species. CS uses three steps in order to find the optimal solution: The first step involves, each cuckoo, at the same time, lays a number of eggs at different nests chosen randomly. In the second step, the new population that will pass to the next generations, are the best nests with high quality of eggs. Finally, in the third step, the nests are abandoned based on a certain probability, after that a new nest with a number of eggs will be constructed. Several studies indicate that this algorithm could outperform both PSO and GA in certain circumstances [52].

4 Results and discussion

The taxonomy as well as the list of published papers that are included in Tables 1, 2, 3, 4, 5, 6, 7, 8, 9 and 10 provide a vast array of information that has a macro analysis in order to identify the trends and nuances of the field. This is an important step, as the previous section focused on how each NIA managed in CD domain with listing their key characteristics. In this section, the aim is to understand the pattern of interest, use that information in order to provide a brief prediction, as well as identifying the current trends in NIAs as a whole.

4.1 Historical analysis of the classification

The first examination, is presenting a historical and chronological view of the published articles from the Tables presented in Sect. 3. There are several statistics that can be drawn from the tables to understand the direction of CD research in the context of nature-inspired algorithms clearly, and also, to present useful information help researchers to choose in which direction they can orient their future research.

Figure 3 depicts the growth rate of the published items over the last thirteen years. Based on Fig. 3, it can be observed that there has been a steady increase since 2007. Although the increase does not follow a linear pattern of growth, it still indicates a maintained interest over the years. The year 2019 has only six recorded publication, due to the fact that the yearly cycle has only begun as of the writing of this review, although, it is included in Fig. 3 bar chart, it may not convey a quite accurate look of the situation.

Fig. 3
figure 3

The chronological distribution of the number of articles in “nature-inspired community detection algorithms (NI-CDA)” in literature published over the past 13 years

Full size image

This information can be used in order to predict or forecast the direction of the publication. Thus, Fig. 4 represents the expected forecasts for the years 2019, 2020 and 2021. The forecast chart uses Seasonal Based Exponential Smoothing (ETS-AAA) algorithm for the prediction model, with existing time-based data which is set up from years 2007 till 2018. This is due to the fact that 2019 has not yet completed its cycle, and thus, the six publications cannot be used as a data point. Using 2019 as a data point would create an error to the forecast process and generate an inaccurate result. As it is observed in Fig. 3, the publication numbers, although increasing, are not following a linear or predictable pattern of growth. Thus, the forecast could shed some light into the future of the nature-inspired community detection algorithms as a research topic.

Fig. 4
figure 4

Forecast chart for the years 2019 to 2021, the color blue is the existing data, while the color orange is the expected forecast. Colors yellow and grey represent: the upper confidence bound and the lower confidence bound, respectively (Color figure online)

Full size image

Based on the observations, the forecast model predicts an overall growth, even though the low confidence bound dictates a fall for the years 2019 and 2020, it predicts that eventually, it will grow. This is an expected growth for nature-inspired algorithms due to their capability to solve the CD problem effectively, and the field growth would seep into all research areas that expected to be attracted pointedly towards addressing the related issues using NIA as a problem-solving tool.

4.2 Analysis network pattern and encoding schemes

In this section, the aim is to identify the various forms of properties and categories related to the community subnetwork and networks as a whole, in the listed references that are included in the Tables provided in Sect. 3, and break them down into their numerical representation. This would aid in identifying the main factors and types that are most popularly used, and help in identifying the trend in which the research work can be progressed and expanded. There is also a chance of identifying each of these selections and provide a justification as to why they are popular in contrast to the other provided types and categories.

Table 11 depicts the statistics related to the kind of community detection (overlap/non-overlap) in various connection patterns of the network (dynamic, multilayer, singed, synthetic (only), and unsigned/static). Along with the percent of studies that tackled different cases of community detection in one study, such as separated & overlapping or singed & unsigned.

Table 11 Statistic related to the kind of community detection in various connection patterns of network
Full size table

These properties were mentioned earlier in all the previous Tables listed in Sect. 3, however, they were considered and analyzed to provide a macro overview and to allow for the identification of the most popular and most used type of CD in the related community network (see Table 11). In this observation, the bulk of the values is with Unsigned SN/Biological Network.

To complete the view more clearly, Fig. 5 presents another statistic based on the kind of network that addressed in the study which can be either social, biological or both. It can be concluded from Table 11 and Fig. 5 that most studies in this domain (CD based on NIAs) have concentrated on uncovering non-overlapping communities in unsigned social networks due to their considerable wide applications.

Fig. 5
figure 5

Statistic related to the kind of network

Full size image

For other connection patterns of complex network i.e. signed/dynamic in SN, static/dynamic in a biological network, and the overlapping communities in both social and biological network, such community structure definition is yet not well explored. Being able to detect community structures from these kinds of networks is an essential and ongoing research topic, that will attract more researchers to highlight and address several of the existing issues and challenges in this domain by presenting more efficient solutions that have significant contribution in many real applications.

For instance, signed communities and community detection in the area of signed networks allows for the determination of the relationship instabilities, and, thus, using it as a means of predicting the changes that occur in a group [21]. From another side, CD in protein biological network aids in detecting proteins that take part in different biological processes, prediction of the biological functions of uncharacterized proteins, as well as in therapeutic purposes [28], while CD in a dynamic network helps in capturing the modifications of interconnections over time and allows tracing the network structure changes at different times.

Table 12 presents the encoding schemes (solution representation) proposed in the collected articles. As shown in Table 12, the greater part of CD studies based on NIAs focused on using “Label-based representation” or “Locus-based representation”, due to their ability to naturally map the community detection problem by automatically determining the number of encoded communities k in each solution. Furthermore, they are ideal for the designing of genetic operators as the standard crossover and mutation operations will not breed invalid genotypes. Using label-based representation, a partition of the network \( N \) is encoded as an integer string \( \varvec{x} = \left\{ {\varvec{x}^{1} ,\varvec{x}^{2} , \ldots ,\varvec{x}^{\varvec{n}} } \right\} \), where \( n \) denotes the number of the vertices and \( x^{i} \) is the integer cluster identifier of vertex \( v_{i} \), whose value lies between \( 1 \) and \( n \) [139]. In locus-based representation, each individual \( G \) is represented by \( n \) genes \( \left\{ {\varvec{G}_{1} ,\varvec{ G}_{2} ,\varvec{ } \ldots ,\varvec{ G}_{\varvec{n}} } \right\} \) and each \( G_{i} \) can take j value, one of the adjacent nodes of node \( i \), then interpreted as a link between nodes \( i \) and \( j. \) However, a decoding step is necessary for the locus representation to identify all the components of the corresponding graph [124, 136].

Table 12 Statistic related to the kind of encoding schemes (solution representation)
Full size table

4.3 Genetic operators analysis

In terms of genetics operators namely, crossover (\( X \)) and mutation, Table 13 and Table 14 view the related statistics which are extracted from the collected articles. As view in Table 13, several studies excluded the crossover, as the authors mentioned that crossover may result in disconnected components or create too many explorations that disturb the potentially good solutions. However, the numbers in the column “No” in Table 13 which are (16: “Uniform X”, 15:” Two-way X/Two-point X”, and 8: “One-way X/One-point X/Single-point X”), referred to the most preferred operators which were employed in the majority of studies.

Table 13 Statistic related to the kind of crossover operator
Full size table
Table 14 Statistic related to the kind of mutation operator
Full size table

The authors state that these types of crossovers greatly improved the global search capability of the domain, as well as enhancing the convergence factor. Especially, the crossover operator is related to the representation schemes used in the framework, such as the medoid-based representation uses a one-point crossover, the label-based representation uses one-point or two-point crossover [139, 150], and the standard uniform crossover fits well for the locus-based representation [136]. Based on the observations, One-way X fixes the roles of the parents between the source and the destination chromosomes. Generally, the offspring values are the same values of destination chromosome excepting some positions, where a random node is selected in the source, and the child chromosome is created first by transferring the community label i of the node selected earlier (in the source) to the destination chromosome, then transferring all nodes in source that have the same community label i to destination chromosome [186].

In two-way \( X \), two offspring generated by exchanging the roles of source and destination of the parent chromosomes [150]. To employ uniform \( {\text{X}} \), a random binary vector of length equal to the number of nodes in the network is used. After that, the offspring is generated by selecting gene from the first parent if the value of binary vector equal \( 1 \), otherwise the gene is selecting from second parent [1].

As regards to the kind of mutation, Table 14 depicts that several studies did not use explicit mutation, a mutation in some NIAs is not as simple an action as mutate allele value as in genetic algorithms. In fact, the lack of explicit crossover or mutation is common in some metaheuristic algorithms. This may explain the observations or fact that many new algorithms can indeed provide a competitive guarantee of the global optimality, but have a significant number of iterations compared with algorithms that used genetic operators such as GA or DE. Looking closely, genetic operators may appear in some subtle way in some algorithms for instance in BCO algorithm randomization is carried out by scout bees and employed bees, and both are mainly mutation [11].

Mutation can take different forms; this can be explained due to the variations in encoding schemes. Several studies focused on “neighbor mutation”, that guarantees that each mutated gene is linked only with one of its neighbors. This method can cause one of two effects. Which both relate to the state of a community, by either splitting a single community or combine two communities together and ultimately modify the community structure. This is considered to be both an effective and simple method, which is apt for “locus based representation” [136]. While “random mutation”, second largest percentage, be apt for the “label-based/ medoid-based representation”, where randomly change the membership of a node by assigning it to one of the other existing communities [128, 139, 140].

4.4 Optimization models analysis

It should be noted that some of the included studies use a single objective function, as opposed to others that use a multi-objective optimization model. Figure 6 illustrates the statistical ratio between studies that use the two optimization models. Using these different models allows for the quality of a community to be measured and how well the connections within the same community, and between different communities.

Fig. 6
figure 6

Statistic related to the kind of optimization model

Full size image

The main differing factor between the two optimization categories is that SOO uses a single criterion in order to perform the optimization task, while the MOO uses multiple criteria to optimize contradictory objectives simultaneously and perform the search process [187].

There are benefits and drawbacks to each of these aforementioned optimization models. Naturally, most of the real-life problems are characterized by contradictory objectives that need to be simultaneously satisfied therefore optimizing multiple objectives allows at the same time evaluation the community structure from different perspectives. Ultimately, the model outputs a set of representative solutions and the decision maker’s responsibility to select the final solution using some domain information or based on subjective preference.

Single objective optimization model, on the other hand, identifies a single best solution that gives insights on the graph organization, but it still prone to some basic challenges such as restricting the solution to a given community structure property since only one objective function is considered. Additionally, if the single objective algorithms return a single fixed community partition, that partition may not be suitable for the networks with multiple structures.

To make full use of network linkage information and to guide the search direction towards feasible solutions, different kinds of heuristic operators are proposed. Because using only genetic operators can oftentimes result in solutions that assign nodes to the wrong community.

For example, the simulated annealing method has adopted in some studies as a heuristic method in order to expedite the convergence speed and avoid falling into a local optimal situation [116, 150]. Another example is an effective local search based mutation algorithm presented in Liu et al. [117] which operates with the aid of a concept called marginal gene to overcome the drawbacks of traditional mutation methods. Figure 7 illustrates the proportion of the existing studies that have the heuristic operator inside NIA in contrast with those that lack it.

Fig. 7
figure 7

Statistic related to classify studies based on adopting/not adopting heuristic operators

Full size image

4.5 NIAs classification analysis

The final statistic presented in Fig. 8 is related to the distribution of NIAs methods that have used as CD problem-solving tools in the collected studies. For the sack of completeness, Fig. 9 illustrates the development timeline for NIAs as well as community detection. As viewed in Figs. 8 and 9, GA and EA have a significant contribution in addressing CD problems where they have attracted the interest of many researchers since approximately 2007 until now. Authors regarded them as powerful search and optimization techniques due to their ability to provide a simple but efficient method for solving many NP-hard optimization problems [21, 188, 189], hence have gained more popularity compared with other methods.

Fig. 8
figure 8

Statistic related to the distribution of methods of NIAs for CD in complex network

Full size image
Fig. 9
figure 9

The development timeline for NIAs as well as CD pattern

Full size image

On the other hand, due to the rapidly expanding in the literature, other different NIAs have adopted to solve CD challenges where notable progress, around the same period, in the related domain was noted by the development of ACO&BCO, PSO, and MAs. As researchers continued trying to find universally better algorithms, more and more NIAs-based CD have been developed in the last few years, i.e. DE, FA, CS, BA, and CA-based CD to address most challenges of CD, not all. Therefore, the search is still on, and there is still a need to be developed such algorithms based on the available resources, the expertise of the decision-maker, and the type of problem. On the other hand, concerning the timeline of the CD pattern, we can see that there is further investigation and search are needed regarding complex networks at different levels signed, dynamic, and overlap.

After presenting and summarizing state-of-art-studies and clarify with useful statistics, now can answer the question that was asked at the beginning “why NIAs is so efficient to solve CD problem in a complex network?”

4.6 Summary of the results

Closely speaking, CD problem has turned even more complicated due to the fact that communities emerge in the network in various forms such as joint/disjoint, static/dynamic, singed/unsigned and multilayer network [7, 8, 19 and 53].

This problem, due to its complexity, may not be properly solved by the conventional optimization methods and as such, CD problems have been solved using NIAs. Since NIAs have capability in providing simple methodology and efficacious at the same time, to solve complex problems, by defining a few basic concepts: an appropriate representation for the given problem, the objective function that be optimized, in either minimization or maximization language, and how to evolve the population (set of individuals) for a while, according to a set of constraints or rules, to generate the organization structures from the system.

From another side, the relaxed nature of these nature-inspired methods is proved to be essential for competitively transcending the limits of other approaches in solving CD problem by producing acceptable solutions in a reasonably practical time when an exhaustive search for the exact solution is impractical to solve such complex problems, and that’s why the popularity of NIAs has notably increased in the related domain.

Compared to conventional MH methods, NIAs are characterized by a number of merits:

  1. 1.

    They are notable for their global searching abilities and good local learning, as well as their remarkable success in resolving a wide range of CD problems.

  2. 2.

    Capability to determine the number of communities automatically during the search process, as well as

  3. 3.

    A problem-specific knowledge can be incorporated inside the method, for instance, using heuristic-perturbation operators instead of random ones, or using a biased initialization, that would allow for a more effective exploration of the search space of possible solutions.

  4. 4.

    They are population-based models be naturally parallel and efficient implementations can be performed to deal with large scale networked dataset [20, 21].

  5. 5.

    Community detection problem is one of the real-world problems, that naturally has conflicting objectives (minimizing inter-connections and maximize intra-connections) requiring to be satisfied simultaneously, therefore, NIAs are more suitable to solve them than other classical approaches.

Although a lot of NIAs have been successfully developed to detect the community structures in complex networks, according to the no free lunch (NFL) theory [190], there is no one-for-all method that can deal with all kinds of networks. Different networks have different space-time properties. When designing algorithms to solve the CD problem, one should take into account the special properties of the networks. Over and above, designing effective and fast algorithms is worth thinking and more interest especially when dealing with the big data [21].

5 Challenges, open issues and future recommendation

CD is a growing research topic that has several issues that are still open and not fully addressed. These problems are not only limited to the theoretical contribution, but also in empirical evaluation and prospects. Overall, the concept of detecting community in a network is considered to be qualitatively intuitive.

However, to make any method able to adequately analyze the network structures, the specifications need to be clear, quantitative and not vague when it comes to the community structure. The subgraphs are only identifiable when the community itself is defined. However, on a practical view and when it comes to the computational concept, defining community is considered to be out of reach even for small systems. In the following subsections, some key challenges and issues facing CD problem are presented, in which some of them related how to collect and process real-life networks with their ground-truth partitions to validate the performance of the NIAs accurately (as described in Sect. 5.1 and 5.2).

In one way or another, CD is an ill-defined problem, as stated in the literature, since there are no typical accepted protocols on the fundamental ingredients such as defining the community itself [7]. Thus, developing a reliable objective function(s) reflects the main feature of the community (minimize inter-connections and maximize intra-connections) is a broad issue (as shown in Sect. 5.3).

However, employing only objective function(s) inside NIAs to detect communities may not be adequate to represent the real community structure due to the limitation in functions’ topological properties. Thus to address this issue need to invest the knowledge of the problem in modeling fitness function and in designing locally heuristic operators (please see Sect. 5.4). Moreover, the representation of the algorithm components can be enhanced by addressing the critical issue regarding some nodes having irregular properties (as described in Sect. 5.5).

On the other hand, there are several crucial issues on CD problem must investigate in future that related to exploiting the temporal characteristics of community structure (community evolution over-time), and modeling multiple types of connections among entities to provide deep insights about the communities (as shown in Sect. 5.6 and 5.7). Moreover, detecting communities in real large scale networks, that have many communities characterized by complex volume and large cardinality, required developing scalable NIAs with efficient parallel implementation to address the curse of dimensionality issue in these large real networks at the lowest possible time (as described in Sect. 5.8 and 5.9). Additionally, the real networks are characterized by heterogeneity of topological that is considered a discrete issue for the CD algorithm since real networks from various domains differ in some networked characteristics (volume and cardinality) depending on the nature of the system that reflected it (please see Sect. 5.10).

Last but not least, further investigation is necessary as regards to biological networks at different levels static/dynamic, overlap/non-overlap, and more efforts to include biological information inside the NIA framework, to improve the accuracy of solutions. Under other conditions, novel ideas are required to tackle overlapping community detection, such as new representation schemes to efficiently deal with overlapping communities.

5.1 Validation issues

One of the top challenges and issues of CD is to be able to evaluate the quality of identified communities, via different algorithms. Currently, artificial networks are used in order to test the algorithms. However, such networks have desired structural properties which are oftentimes not representative of the real world networks. Thus, in an ideal situation, real networks need to be used to compare the performance of different CD algorithms besides artificial networks. Theoretically, it is possible to validate the accuracy of the algorithm in the discovery of a robust community structure through removal, or addition of links in the real network [18, 191].

5.2 Availability of real and live dataset

The second problem is also a common validation issue which researchers face it in many aspects and disciplines that fall into the community detection domain. This is mainly due to the fact that collecting real and live data is extremely difficult and requires several steps involved threads of validity and privacy, and in-depth pre-processing of the data. Raw and live datasets need to be parsed and processes, as an additional and critical step before building a network from a real-known dataset based on observed relations. With the rise of interest in dynamic community detection, the need for a live and dynamic dataset has never been more important. However, in most cases, this is a relatively impossible task and obtaining such data is considered to be a task of utmost difficulty.

5.3 Objective function

The choice of an objective function is another critical issue in CD problem for obtaining good solutions. Though many efforts based on NIAs have been directed to address this issue as single-objective optimization functions and obtaining good results on both artificial and real-world networks. However, in some scenarios, there can be multiple competing objectives that aim to address the same problem. The intuitive notion of community is that the number of edges inside a community should be far higher than the number of edges connecting with remaining nodes of the graph. This scenario creates two of negatively correlated objectives which differ greatly from one another. The objectives are, to minimize external links, and maximize the internal links. Therefore, selection a meaningful objective function(s) is a broad issue and the point of competition among the proposed algorithms.

5.4 Cross- fertilization

Despite the success of the proposed NIAs in tackling CD problem, the characteristic components of many, if not most, of them are still in their more or less traditional forms. They employed the problem knowledge domain in designing very generally single objective or multi-objective function only, they did not exploit any possible heuristic to enhance the performance of their models. In future, more attention should be taken to invest domain-knowledge of the problem not only in fitness function but also by cross-fertilizing the method with heuristic operators, in order to guide the search process towards promising regions.

5.5 Community-irregular property

Some nodes in the real network follow community-irregular property have been considered in some studies as community-less nodes (i.e. a node has weak intra-relation with other nodes of its correct community comparing with nodes of other communities). There is a need to propose aware efficient algorithms is not disturbed by these nodes in the network.

5.6 Temporal analysis

Time is another issue, as most of the proposed solutions work based of a static network, however, in a dynamic environment the network and the system are ever changing and evolving over time, and the process of detecting communities in such networks requires adapting with the network structure changes. Thus, it is imperative to study the time’s characteristics and facets more deeply with regards to the communities of a network in a dynamic environment. Although there are several studies investigating time aspect in single layer graphs, but when it comes to multilayer networks, there is still very little research was proposed [61]. Thus, the study in a multilayer network is considered to be a highly important issue that is extremely complex and requires more research to address its various sub-challenges.

5.7 Multidimensional analysis

One of the most interesting topics that are discussed earlier was the multilayer networks. With their growth in popularity, there is a need for new approaches to address these types of networks [192]. However, based on recent research, multilayer networks are a growing trend and the development of CD methods in this domain still in its beginning stages [27].

5.8 Scalability of community detection algorithms

Scalability is an important issue that is especially of concern in the age of big data. The current existing algorithms have a tendency to reduce the dimensionality of the data before the patterns are properly identified. Two recent advances were done in the existing algorithms to be able to tackle the big data problems, which are Online or Streaming Clustering techniques. Ultimately, the algorithms are required to become even more efficient, scalable, versatile, and able to handle the growing size of network data with the lowest possible cost thru improving the speed and accuracy of relevant performance parameters since real-world networks’ growth is inevitable.

5.9 Time consuming

Regardless of where they are implemented, the NIAs have always been known as a time-consuming process. Thus, many researchers and developers prefer to use the classical and traditional approaches rather than the NIAs, since time is considered to be a very crucial element. This is particularly the case when the networks get extremely large, and the quality may start to falter. This is a vital issue as the technological age is notably moving towards big data and the requirements for heavy data management for millions of nodes are imperative. In order to accelerate the response time, there is a need for developing parallel implementations. Evolutionary methods have default parallel characteristics that can be developed in order to be more competitive with other available methods in terms of time and quality. Researchers can also reduce the time and space requirements by using more efficient representation forms such as variable length chromosomes [21].

5.10 Heterogeneity of real-world networks

The lack of a unique definition of “community”, has made it difficult for algorithms to be able to address CD challenges in all type of networks. For instance, both social and mobile networks, have a completely different definition for community, and cluster, thus making it difficult for a single algorithm to be able to identify and adapt with both scenarios without any extra readjustment. This differentiation or heterogeneity in real-world networks creates a direct challenge for all CD algorithms [193].

6 Conclusions

The aim of this review was to provide a complete overview of community detection based on nature-inspired algorithms in complex networks. To achieve this goal, several steps had to be taken. First, since NIA is an important aspect of this process, they are required to be elaborated and explained. Thus, the first step is to categorize and classify NIAs as well as list all relevant published researches that use any of the NIA as a major tool for processing. The second step is to connect these algorithms to how they serve as a solution for community detection. Once this distinction is done, they are statistically broken down and summarized based on their common key components. With each aspect of the summarization, the outstanding inclinations in the relevant aspect were discussed.

The results and discussion of this research are divided into several categories. The first is the historical analysis of the various subcategories which provides an overview of the growing interest in the field as a whole. It also allows predicting that the field is on a positive incline, and will continue to grow, although steadily, rather than sharply.

The second group of statistical analysis corresponds to the various representation of the categories in numerical and ratio form. This allows to see the popularity of one group or kind over the others and help to know which areas are lacking to study, and which areas are over-represented.

The aim of these statistics is to illustrate the focus and direction of the researchers on methods and approaches used to select the basic characteristics of NIA. This information would enable future researches to determine effective characteristics related to their research, as well as accurately selecting: network type and its complexity, solution representation kind, genetic operators’ kind, and model type based on the number of objective functions. Then, injecting the proposed method with a heuristic operator to enhance its performance, as recommended. Following that, we highlighted the open issues and future desirable developments relevant to this field.

Finally, the review can serve as a guiding point for researchers and scholars of the domain interested in approaching the problem of community detection with computational models inspired by evolution in nature by providing a complete overview and classification that can familiarize them with the most important aspects of this domain.