A review: Multi-Objective Algorithm for Community Detection in Complex Social Networks

1.1. Single Objective Optimization

This type of optimization is used when there is only one objective. Other essential objectives are ignored or even have an impact on them [3].

1.2. Multi-Objective Optimization

Algorithms with a set of objectives (typically consist of two or three objectives) are named by multi-objective algorithms (MOAs). MOAs try to identify an optimal solution or more than one solution to an optimization problem by maximizing or minimizing these objectives [4].

1.3. Many-Objective Optimization

Multi-objective optimization involving more than three objectives is known as many-objective optimization algorithms [5].

As mentioned previously, the field of optimization is used for solving many different problems; one of them is community detection in complex social networks. There are many real-world complex systems that can be demonstrated as complex networks, such as technology networks, social networks, web networks, and biological networks [6]. First, we need to understand what the meaning of community is. A community is a set of entities that are more strongly connected to each other than the other entities within the network [7]. These communities need some techniques, such as optimization algorithms, to be detected within the network. The techniques of community detection play a crucial role in understanding the functionality of complex networks [8]. This process is used to find hidden structures of communities in complex networks and it can be used to find the topology structures of complex networks and understand what the functions of complex networks are [9]–[12]. In mathematics, complex networks can be demonstrated as graphs, where nodes in a graph are denoted as vertices in the network and links can be used to show the edges of a network [13]. Fig. 1 shows a simple community detection using graph theory.

Fig. 1. Example of showing community structure by a graph theory.

Nowadays, many optimization algorithms are proposed to address the issue of community detection, such as greedy algorithms and meta-heuristic algorithms. However, the greedy technique is not performing well for detecting communities in large complex networks [14]. However, meta-heuristic algorithms play a crucial role in detecting communities in complex social networks. There are many different meta-heuristic algorithms. The vast majority of meta-heuristics belong to algorithms inspired by nature, such as genetic algorithms (GAs), particle swarm optimization (PSO), and ant colony optimization [15]. A number of them belong to non-nature-inspired algorithms, for example, Tabu Search [16] and Iterated Local Search [17].

This review paper reviews some state-of-the-art algorithms based on multi-objective optimization for detecting communities in complex social networks. Furthermore, some of these approaches enhanced meta-heuristic optimizations to detect high-quality communities. Moreover, another made is a combination of the meta-heuristic algorithms to perform better quality of detection. The detail is presented in Section 3.

The rest of the paper is organized as follows: Section 2 is a research strategy; the strategy of the research is explained here. Section 3 presents a literature review; in this section, we discuss the contributions of 15 different researchers. Section 4 is methodology; in this section, the common datasets and evaluation metrics are explained. Section 5 is a comparison and discussion; this section is about the comparison between approaches in terms of objectives, some popular problems of algorithms, solutions, challenges, and future work based on gaps in the reviewed algorithms. The final section is a conclusion; the paper is concluded here.

3.1. Modified Evolutionary Algorithms

Hosseinian and Baradaran [18] proposed a new approach named a multi-objective multi-agent optimization algorithm (MAOA) for detecting community problems in social networks. This algorithm optimizes each objective simultaneously to obtain enhanced accuracy and efficiency in the detection of communities in the networks. This algorithm introduces an agent-based multi-objective for detecting communities. The agents are organized into groups of leaders and active agents. By having this, the algorithm used a grouped structure. By enhancing the agent’s environment and behaviors, the algorithm effectively facilitated the solution space exploration. Another contribution in this approach is integrating the concept of Pareto dominance to ensure the algorithm can approximate the Pareto optimal front and identify solution efficiency. Experimentally, there are two main contributions: Performance improved by using a multi-agent strategy and providing better initialization to make more applicability in large and more complex networks. Experimental results were tested on some real-world networks and compared with three meta-heuristic algorithms. The result demonstrates that the MAOA performs better in terms of accuracy and efficiency.

Another approach based on a multi-objective evolutionary algorithm with decomposition (MOEA/D) is proposed by Abdulrahman et al. [19]. It is decomposing the multi-objective optimization problem into several sub-problems efficiently. The aim of this method is to balance the quality of detecting communities with the distribution of solutions through the Pareto front and find a different set of Pareto optimal solutions. MOEA/D focused on enhancing mutation operators to improve performance. Unlike the traditional mutation operator, this randomly selects a node for mutation. In this approach, the internal and external connections between nodes have been calculated. Nodes with low internal and high external connections are called positive connections and nodes with high internal and low external connections are called negative connections. The mutation operator has been applied over the positive connections. Having positive and negative connections helps the efficiency of the algorithm. A variety of real-world networks were selected to evaluate the performance of MOEA/D. The result of this approach is outperformed compared with the traditional methods. It provides a better structure for community detection in dynamic networks.

In the same year of [19], Liu et al. [20] designed an enhanced algorithm using a multi-objective evolutionary algorithm (MOEA). To optimize the process of community detection, the proposed algorithm performed a compression-based method to optimize two objectives, such as maximizing the modularity and minimizing the number of communities. The compression process was applied over the network topologies to obtain smaller networks. The main purpose of this approach is improving efficiency by compressing networks because the majority of algorithms for community detection have a problem of computational time. Furthermore, to prefer a better community structure, both initialization and mutation processes have been improved. The approach conducts extensive experiments on some datasets and the result outperforms some existing methods in terms of computational efficiency and accuracy. The proposed algorithm has the ability to exploit in the search of an optimal solution and make a balance between exploration and exploitation. The results are tested on some different datasets and compared with some state-of-the-art algorithms. The proposed algorithm obtained higher accuracy and performance.

Another paper by Shaik et al. [21] presents a novel algorithm to detect communities in complex social networks using three objectives. Optimizing three objectives is a main novelty because traditional approaches primarily focused on single or two objectives. There are two variants of a non-dominated sorting GA (NSGA) III introduced. The first is NSGA-III-KRM (kernel k-means, ratio cut, and modularity) and the second variant is NSGA-III-CCM (community score, community fitness, and modularity). Moreover, a new measurement of the ranking mechanism for Pareto solutions by using a ratio of hyper-volume to inverted generational distance is produced to enhance the Pareto set evaluation. This research addresses some limitations and improves the performance metrics of previous approaches. To evaluate the result of this algorithm, four network datasets are selected and compared with some existing state-of-the-art methods. The algorithm achieved a good result compared with other algorithms.

A new parallel MOEA (PMOEA) was proposed by Su et al. [22]. It is designed to detect communities in large-scale complex networks. The first operation performed by PMOEA is to identify communities based on specific nodes (key nodes) rather than the entire network. After that, it executes multiple copies of a MOEA to detect communities linked to each key node using a parallel mechanism. Another contribution in this approach is enhancing the mutation and crossover operators to capture a better community in the network. Through performing the parallel process, the computational efficiency and quality of detection are enhanced. Experiments of this algorithm indicate that it works better than other evolutionary and non-evolutionary algorithms, showing that it can handle networks with up to 200,000 nodes.

Based on the NSGA II algorithm, the dynamic community detection (DCD) system proposed by Alkhalec Tharwat et al. [23]. The proposed algorithm explains the growing need for community detection methods effectively in dynamic social networks. DCD is the main goal of this algorithm, while networks change over time. It utilizes a multi-objective optimization framework by using the specialty of NSGA-II and involves formulating the community detection problems in social networks where the state of networks changes over time. While the network is dynamic, the proposed algorithm identified communities at different time points. This algorithm is able to be used in various applications, such as recommender systems, analysis of social media, and retrieving information. The result of this algorithm obtained better performance compared with classical GAs.

Another approach, using a multi-objective GA (MOGA-Net), is proposed by Abbood et al. [25] for community detection in complex networks. The proposed approach uses the NSGA-II for finding globally non-dominated solutions, which guarantees that no other possible partition is superior for both objectives. The proposed algorithm introduced a novel scoring model (intra-score and inter-score). They assist the algorithm to capture better community structure. A new contribution of this approach is identifying the healthy and infected communities during COVID-19. This study compares MOGA-Net’s performance with other state-of-the-art methods using some real networks, showing how efficiently it creates accurate community structures. This algorithm also introduces a new scoring model that quantifies the density of internal connections (intra-score) and the sparsity of inter-community connections (inter-score).

There is an additional contribution by Zhu et al. [27] is a fundamental task that aids the comprehension of complex networks. The proposed approach implements a two-stage MOEA that strengthens community detection through optimizing multiple objectives simultaneously. First, in the initial stage, the individual similarity parameters are targeted to find possible communities; then, in the second stage, distinct crossover operators are employed with respect to the characteristics of the detected communities. The algorithm is developed to handle challenges arising in traditional community-detection methods, which face the complexity and dynamics of real-world networks. Furthermore, it enhanced the boundary-independent nodes by applying the second-stage strategy. They further validate their approach through extensive experiments on many datasets, showing that their algorithm performs better than the state-of-the-art approaches in both accuracy and computational efficiency.

In the study of Zhang et al. [28], a new algorithm named MMCoMO (Macro-Micro Population-Based Co-Evolutionary Multi-Objective) algorithm was proposed and it’s different than the traditional MOEAs. They worked with a single population at the first steps, which lead to a limiting balance between exploration and exploitation. On the other hand, the MMCoMO employs macro-population and micro-population as two types of population. The main contribution in this approach identified the macro and micro populations. The macro-population emphasizes exploration. During this process, the network quickly portioned to detect the approximate community structure. Meanwhile, the micro-population focuses on exploitation to achieve more precise community configurations the structures of the network through local search are refined. In addition to quality enhancement, the MMCoMO improves the computational efficiency of detecting communities compared with existing MOEAs.

After that, Cai et al. [31] provide a fast two-stage MOEA for the identification of the overlapping community in networks. The main goal of this algorithm is to discover overlapping communities using a two-stage MOEA. The first stage aims at identifying the high-quality non-overlapping communities by using the population initialization technique using the degree central nodes. It also increases the robustness of community division with respect to the existing methods. In the second stage, the algorithm picks out additional nodes from the networks that have previously been categorized in non-overlapping communities as central nodes. An information feedback model is used to adjust a fuzzy scale for thresholding to improve the identification of overlapping nodes. Another contribution in this approach is identifying a new initialization of the population using central nodes based on node degree for better partitioning. The proposed algorithm’s efficiency is tested through experiments on some different networks and compared with other algorithms based on the modularity and accuracy value of community structure and achieved higher results.

Sheykhzadeh et al. [32] proposed a novel local community detection algorithm based on node ranking in social networks. It is referred to as LCD-SN local method community detection algorithm in social networks and is designed to overcome the limitations of previous approaches that usually have low accuracy and high computational time. Node ranking means how nodes interact and are ranked relative to community nodes and their connectivity. The algorithm has been designed to look for communities of densely connected nodes and relatively scattered nodes in between communities. First-degree and second-degree neighbor nodes are used by LCD-SN to build the communities, as a result of which accuracy and determinism are improved while seed nodes are not required. The algorithm starts with node scaling and defining the important nodes with the help of local characteristics and then it creates the primary groups with the node and its first-order neighbors. Communities are identified in the last step in the process known as post-processing. The paper also presents a new measure for ranking the nodes in the network, which makes community detection even better. Experimental analysis shows that LCD-SN is useful for finding communities with a flexible approach to the trade-off between time and solution quality.

3.2. Hybrid Evolutionary Algorithms

Pérez-Peló et al. [24] present a hybrid meta-heuristic approach for detecting communities in networks by combining variable neighborhood search (VNS) and Greedy randomized adaptive search procedure (GRASP). The main contribution in this approach is improving the efficiency of search by combining VNS and GRASP. Moreover, the limitations of traditional community detection algorithms are highlighted, especially these challenges that are associated with high modularity that suffers from the limitation of resolution. Based on bi-objective community detection problems, this algorithm aims to optimize multiple objectives simultaneously, which leads to a reliable community structure. As a result, the algorithm shows effectiveness compared with the existing approaches and is good for these applications that are used for analyzing complex networks.

In this direction, Yang et al. [26] have proposed a hybrid approach to community detection in complex networks. The main contribution in this algorithm is identifying a mixed encoding strategy by combining locus-based and label-based representation. Having this combination helps the algorithm to represent a valid community structure and is more flexible. Furthermore, this study has recognized the difficulties that were posed by methods based on traditional modularity maximization, especially with regard to network topology issues and invalid solution generation. To improve these issues, this paper proposes a MOEA based on the integration of label-based and locus-based representations. The experimental results have shown that this approach outperforms existing algorithms concerning effectiveness and efficiency. These results confirm that this algorithm is a competitive approach when compared with traditional methods of community detection and consequently.

3.3. Swarm Intelligence Algorithms

As a part of swarm intelligence, Li [29], proposed a new overlapping community detection algorithm based on subgraph structures and multiple objective optimization techniques. The main contribution in this approach is transforming overlapping nodes into clique nodes. Due to the possible overlap in real-world communities, the algorithm herein proposed employs the k-core decomposition to find maximum cliques, which form the building blocks for the weighted graph. Instead of randomly initializing the population, the proposed algorithm leverages the k-core decomposition for better initial community partitioning. The algorithm integrates a PSO to improve search accuracy and convergence speed. The result of this algorithm compared with similar community detection algorithms on some real-world networks and demonstrated a decent performance.

Then, Yu et al. [30] introduced a new algorithm named multi-objective pigeon-inspired optimization (MOPIO). This algorithm performed three main steps: Initialization, search, and mutation methods. It starts by constructing a solution representation of the community structure to evaluate two objective functions to assess community quality. The main contribution of this research is integrating pigeon-inspired optimization for community detection. It enhanced the applicability of the algorithm for complex networks. Furthermore, to address the problem of misclassification of boundary nodes, they proposed a novel strategy through the mutation process. The result of this work is evaluated based on different networks and it performs better for detecting community structures compared with other existing approaches. This algorithm not only enhanced the accuracy of community detection but also offered a framework compactable with various networks.

4.1. Common Networks

The networks that are used by each study consist of a different number of nodes and edges. Each node is strongly connected with others in the same community and weakly with other nodes in the different community. The connections between nodes are called edges [7]. This number of edges and nodes defines the size of the networks. Furthermore, in some of these networks, the number of communities was detected using a ground truth [33]. Table 3 shows the properties of some common networks that are used by the papers.

TABLE 3: Some different size of common real-world networks

4.2. Metrics for Evaluating the Results

Q modularity and normalized mutual information (NMI) are two main metrics that are used to evaluate community detection in social networks. All of the studies in this review paper used these two metrics to evaluate the result of detecting communities for each network that was used in their paper.

The modularity Q, which can be computed without knowledge of the actual community labels of a network, was chosen as a measure of quality for the communities; a higher Q value indicates better performance in community detection [42]. The formula of modularity Q was defined as below.

k and M show the number of detected communities and edge’s number in a network, respectively. Then, l_s is a number of edges for each node in the community i, and d_s is a total degree of nodes in the same community [42].

However, using truth grounds, the NMI was used in order to measure how similar the detected and real communities were. Greater value of NMI shows better performance in detecting communities [43]. The following is the definition of the NMI formula.

In partitions A and B, CA and C^B present the number of communities, C shows the confusion matrix, and C_i,j is a shared node between community i of A and community j of B. C_i. or C_.j determines the total elements of C in row i or column j, while the number of nodes in the network is n [43].

5.1. Compare Objectives used by Algorithms

All of the studies that were selected in this review paper used a MOA for detecting communities in the networks. Moreover, most of them used the MOA for optimizing two objectives instead of one that optimized three objectives. The number of objectives and their types are explained in Table 4. Furthermore, Fig. 3 explains the most frequent objectives used by the algorithms.

Fig. 3. The most frequent objectives used by the algorithms.

TABLE 4: Demonstrates the number and type of objectives that optimized by the papers in the literature

According to Fig. 3, modularity is the most frequently used by the algorithms. Then RC comes as the most commonly used after modularity. The modularity is used to measure the quality of network partitions and a RC is a solution to achieve as few as possible connections between the communities [21].

5.2. Problem Definition of Community Detection and Limitations

5.2.1. Overlapping communities

Refer to a problem in which one node simultaneously belongs to multiple communities [44]. Most of the studies in this review paper solved the mentioned problem. Fig. 4 shows the overlapping communities in the network.

Fig. 4. Overlapping communities [45].

5.3. Addressing Limitations

5.4. Challenges and Future Work

According to the limitations that were explained in the previous sub-section, there are many challenges and future works.