# Detecting Communities in Complex Networks Using an Adaptive Genetic Algorithm and Node Similarity-Based Encoding

Authors: Sajjad Hesamipour; Mohammad Ali Balafar; Saeed Mousazadeh
Journal: Complexity
 (2023)

---

## Abstract

Detecting communities in complex networks can shed light on the essential characteristics and functions of the modeled phenomena. This topic has attracted researchers from both academia and industry. Among different community detection methods, genetic algorithms (GAs) have become popular. Considering the drawbacks of the currently usedlocus-based and solution-vector-based encodings to represent the individuals, in this article, we propose (1) a new node similarity-based encoding method, MST-based encoding, to represent a network partition as an individual, which can avoid the shortcomings of the previous encoding schemes. Then, we propose (2) a new adaptive genetic algorithm for the purpose of detecting communities in networks, along with (3) a new initial population generation function to improve the convergence time of the algorithm, and (4) a new sine-based adaptive mutation function which adjusts the mutations according to the improvement in the fitness value of the best individual in the population pool. The proposed method combines the similarity-based and modularity-optimization-based approaches to find communities in complex networks in an evolutionary framework. Besides the fact that the proposed encoding can avoid meaningless mutations or disconnected communities, we show that the new initial population generation function and the new adaptive mutation function can improve the convergence time of the algorithm. Several experiments and comparisons were conducted to verify the effectiveness of the proposed method using modularity and NMI measures on both real-world and synthetic datasets. The results show that the proposed method can find the communities in a significantly shorter time than other GAs while reaching a better trade-off in the different measures.


---

## Body

## 1. Introduction

Ever since the introduction of graphs by Leonhard Euler in the 18th century, they became a revolutionary tool to model and analyze real-world phenomena. Many complex systems have interactional features, and graphs lay the necessary ground to model them. The graphs acquired from real-world phenomena typically have characteristics that differentiate them from random graphs. One of these characteristics is the diversity of the edge density in different parts of the network. These densely interconnected components could be interpreted differently based on the context of the modeled phenomena and provide valuable information about its essence. While these subgraphs can represent individuals with common interests in social networks, they might indicate the proteins involved in a specific function on a protein interaction network. Therefore, finding these groups can provide meaningful information for experts or recommender systems to make sound decisions [1, 2]. The goal of community detection is to find a partition for the network that separates these densely connected parts from each other [3]. It must be noted that community detection differs from graph partitioning problems based on the predefined number of communities and their nodes. While these parameters are provided in graph partitioning problems in advance, they form the major dilemmas of a community detection algorithm. Therefore, a community detection algorithm should be able to find the communities of a network in the absence of knowledge about the number of communities and their nodes [4].In recent years, the popularity of community detection has increased among researchers from various fields. The need for a quality measure to evaluate the results of different methods has been answered by a measure called modularity. Modularity is a measure that evaluates the given partition for a network based on the nonrandomness of its intracommunity edges. Different methods have been proposed to maximize modularity. The GAs’ ability to solve various optimization problems has brought considerable popularity for them in finding communities. These methods start with random individuals, and through keeping and combining the fit and eliminating the weak solutions, narrow the search space to desired solutions [5]. This seemingly simple logic has been shown to be able to find remarkable results for complicated problems. In recent years, several evolutionary algorithms (EAs) have been proposed to solve community detection problems. The main disadvantage of these methods is their long convergence time. Nearly all of the GA-based and EA-based community detection algorithms can be classified in the modularity-optimization category (in Section 2, we discuss different methods in a detailed literature review).However, despite its extensive use, modularity suffers from a resolution limit problem, which indicates that it cannot detect communities smaller than a specific scale [6]. Thus, efforts to propose other measures still continue [6, 7]. Node similarity-based algorithms try to solve this problem by offering alternative measures [8, 9]. Another group of algorithms attempts to combine similarity-based and modularity-optimization-based approaches by taking advantage of each one in various stages of the community detection process.Furthermore, most of the GA-based community detection methods uselocus-based or solution-vector-based representations to encode each solution, but each of them has shortcomings such as producing disconnected communities and ineffective mutations (we discuss further details of the deficiencies of these methods in Section 4.1). In this article, we introduce a new individual encoding method, called MST-based representation to both overcome the deficiencies of the existing representations and make benefit from the characteristics of different similarity-based approaches. The new chromosome representation encodes the network’s edges instead of its nodes. First, we create a weighted copy of the network using node similarity indexes and form a binary chromosome where each gene refers to an edge in the corresponding spanning tree of the weighted graph. Zero and one values of the elements of this string indicate the occurrence of a connection or detachment at the corresponding edge of the spanning tree. Compared with the other representations, MST-based representation can reduce the search space by eliminating rare possibilities and directing the procedure towards much-appealing partitions. Also, considering the time limit as one of the major dilemmas of the EAs, this representation can perform faster compared to the other methods regarding the fact that it reduces the possible values of each gene from the number of its corresponding node’s neighbors to two (connected or detached edge). We show that considering the improvements in other parameters, the amount of information loss caused by this representation is negligible.One of the methods to accelerate the convergence time of a GA is to start the process from a nonrandom population. To further improve the convergence time of our method, we propose a new initial population generation function based on the proposed representation. The novel initial population generation function separates the network into some initial communities using a simple but effective threshold-cutting method. Results confirm that this strategy can yield better initial populations and reduce the convergence time of the algorithm.Finally, we introduce a new adaptive mutation function, called thesine-based mutation function. The sine-based mutation function creates the mutation probability distribution based on a self-adaptive control parameter and the distance of the edges from the borders of the community. The control parameter causes the distribution to change smoothly according to the improvement in the fitness value of the best individual in the population pool and introduces mutations in more appealing genes. Experiments approve the effectiveness of the proposed mutation function.We can summarize the contributions of this article as follows:(i)
A new fast GA for community detection method is proposed, which combinessimilarity-based and modularity-based approaches (Section 4)(ii)
We propose a new method to represent the individuals for community detection problems in GAs calledMST-based representation, which can tackle issues such as disconnected communities and ineffective mutations (Section 4.1)(iii)
We propose a new function to generate the initial population, which can produce close to optimal initial populations and enhance the convergence time (Section4.2)(iv)
A new adaptive mutation function, called thesine-based mutation function, is introduced, which adjusts gene mutation probabilities based on a self-adaptive adjustment parameter and directs mutation to the internal/border edges based on the improvement in the fitness value (Section 4.5)(v)
Several experiments and comparisons have been conducted that show the effectiveness of the proposed method (Section5)The rest of the article is organized as follows. In Section2, we review the existing scientific literature on community detection; in Section 3, we present some preliminaries and definitions; Section 4 focuses on the details of the proposed method; Section 5 provides the results of our method and compares its results with other well-known algorithms. Finally, we conclude the article in Section 6.


## 2. Related Work

Community detection algorithms can be categorized based on different criteria. Different methods use differentmethodological approaches to find communities by either breaking big communities into smaller ones or combining small ones into bigger ones [3, 7]. Souravlas et al. have mentioned another emerging category called data structure-based approaches [10]. On the other hand, because of the extreme richness of the different definitions of “community” in the literature, one can even categorize methods into subcategories such as density-based, vertex similarity-based, action-based, and influence propagation-based algorithms according to the ways that they define a community (it is still possible to break each of these categories into more specific subcategories).These categories are not always mutually exclusive (meaning that an algorithm might be a member of different categories at the same time), and, as it will be discussed in 2.4, some methods purposefully try to make use of the advantages of each approach in their different stages. In the following sections, we present a literature review of the community detection algorithms while dividing them into different categories of community detection algorithms.


### 2.1. Definition-Based Perspective

Newman and Girvan defined “community” based on the nonrandomness of the edges among the nodes. They proposed modularity to measure this feature in different partitions using a null random model [4]. Compared to the other measures, its lower computational complexity and higher accuracy drew the attention of the scientific society toward modularity, which resulted in numerous algorithms based on it. A plethora of research works involves methods that try to solve the community detection problem via the optimization of modularity. These methods are usually referred to as the modularity-optimization algorithms.On the reverse side of themodularity-optimization methods are the algorithms that use local structural information of the network to detect the communities. These algorithms do not focus on the optimization of a specific global measure, such as modularity. One of the widely used methods is known as the label propagation algorithm (LPA) proposed in [11]. LPA is one of the classic algorithms of community detection. LPA starts with assigning a label to each node of the network at the initial step; then, it updates the labels to the most frequent label among their neighbors in a random sequence. In this algorithm, the label of each node corresponds to the community to which the node belongs to. This process quickly ends up in the uniquely labeled subgraphs.A mutually beneficial domain with community detection is link prediction. Hence, numeroussimilarity-based methods use link prediction indexes to measure the similarities among the edges [12]. Cheng et al. show that link prediction can be used to improve the accuracy of community detection methods [8]. The authors in [13] describe some of these similarity measures in the network flow framework and show that some of these similarities are related to different kinds of network flows. As a similarity-based agglomerative method (see 2.2 for further description on agglomerative methods), Castrillo et al. defined a new similarity index based on the well-knowncosine similarity index [14]. Then, starting from the singleton communities, they merge the communities till no weak community remains. Hesamipour et al. use one of these link prediction measures named Adamic/Adar (AA) to determine the central nodes of the network and expand communities around them [9]. They find each central node based on its higher similarity score and its higher distance from other previously selected central nodes. After locating these nodes, they expand the communities around them with a game-theoretic agglomerative approach. The authors in [15] also propose a community detection method using the AA similarity measure. They use the AA to measure the similarity of nodes and form initial communities. Later, they merge these initial communities based on a specific attractiveness index.Some other methods of this category interpret the local information in a probabilistic framework. In [16], they use the proportion of neighbor nodes belonging to each community to estimate the dependency of each node on its own or on the neighbor community and propose an overlapping community detection method. To find the communities, Infomap [17] operates a random walk process and obtains the probabilities for a random walker to pass from each edge. Then, it turns the community detection problem into a minimum length encoding problem and detects the communities using Huffman encoding. In [18], a method is proposed that iteratively removes each edge of the graph to find its overall impact on each node’s entropy. They define the entropy of a specific node as the uncertainty of the destination node for a random walker if it starts from that node.With the growing acceptance of modularity and its extensive use in community detection, researchers turned their attention toward EAs, which are known to be proper algorithms to answer maximization/optimization problems. Although most of the GA-based community detection methods are categorized asmodularity-optimization methods, several methods attempt to optimize other measures. To the best of our knowledge, Bingol et al. made the first attempt to use EAs to detect the communities of a network [19, 20]. They implement the solution-vector representation method to represent each individual in the population pool [20]. A solution vector is an n-dimensional vector (n is the number of nodes) that stores the community identifier of each node in its corresponding element. First, they form the initial population by setting some nodes and their neighbors in the same communities. Later, they use modularity as a fitness function, sort individuals based on their fitness scores, and select some individuals to merge them using a crossover function. Their one-way crossover function chooses a random community from one of the parents (source parent) and transfers it to the destination parent. Finally, they apply a uniform mutation function to change the value of a random gene. In their next work, the same authors proposed a measure named community variance and employed it in a cleanup stage to promote the convergence time of their former method [19]. As we mentioned in Section 1, the goal of community detection is to find subgraphs with dense internal connections and sparse outer links. Modularity reflects both of these conditions within itself. A multiobjective EA is proposed based on these terms in [21]. Multiobjective methods attempt to optimize more than one measure simultaneously. They decompose modularity into two different objective functions to address both terms (dense internal connections and sparse outer links). Finally, they return the individual with the maximum modularity as the solution. Ying et al. used a similar multiobjective conical area EA to detect the communities [22]. Another similar multiobjective approach was also implemented in [23, 24]. GA-net is one of the famous community detection algorithms based on evolutionary methods which does not use modularity as its fitness function [25]. This method proposes a new measure, called community score, to measure the quality of the detected communities and uses it as a fitness function [25]. Yet, the proposed measure on GA-net highly depends on its internal control parameter, and its results change dramatically based on the parameter. In [26], Samie et al. propose another GA that detects communities using the community score measure (the measure proposed by Pizzuti in GA-net [25]). Their method implements an additional cleanup step to absorb some weak communities or single nodes into other communities. Zarei et al. propose a heuristic method for initial population generation, an object migration automata-based method, and a hybrid algorithm based on object migration automata and GA [27]. Their purpose to couple those methods is to avoid getting stuck in local optima.


### 2.2. Methodological Perspective

From the methodological point of view, community detection algorithms are separated intoagglomerative and divisiveclasses. While agglomerative methods start from local structures and expand them to form communities, divisive methods start from the full graph level and try to detect communities by dividing the network into communities. Newman and Girvan introduced modularity along with a divisive modularity-optimization-based community detection algorithm [4]. Their divisive method is based on discarding the edges with high betweenness values from the graph. They construct a hierarchical tree as the communities start to split after removing the edges with high betweenness values. This iterative edge removal process continues until all edges are removed, and a dendrogram is formed from top to bottom. Finally, they cut the dendrogram at a level that gives the maximum modularity. Another method proposed is to form a dendrogram from bottom to top (agglomerative) in [28]. This method is well-known as the fast greedy method. It starts from the singleton communities and merges them following a greedy strategy until no other aggregation can further improve the modularity. Blondel et al. proposed another modularity-based agglomerative method known as Louvain in [29]. Their proposed method operates at two stages; first, it starts from single node communities and merges them subjected to the increase in modularity. Second, it merges these groups of nodes at supernodes. Then, it repeats the process from the beginning on the newly generated graph until no other aggregation could increase the modularity. Later, Traag et al. proposed an improved version of the Louvain called Leiden algorithm [30]. They showed that the Louvain method can lead to disconnected communities and added a refinement stage to prevent it.


### 2.3. Data Structure-Based Perspective

The extraction of an underlying structure of the given network is a usual practice in community detection algorithms. This underlying structure is usually called askeleton network and represents a summary of the main network. The recently trending data structure-based methods are based on the idea of transforming a network to another data structure, such as a tree [10]. These methods use a new data structure either to reveal some of the hidden characteristics of the network or to reduce the complexity of the problem.In [31], the authors propose a method called EdMot. Using triangle connections, EdMot forms a new graph. Then, it finds the densely connected components of this newly formed graph and adds extra edges to them. The resultant network summarizes both lower-level and higher-level connections and highlights the communities. Another method called WATSET [32] proposes a metaheuristic way that uses a fuzzy method to create a sense graph in the first stage. In the next stage, it detects the crisp communities with the help of the new data structure.


### 2.4. Combinatorial Perspective

On the other hand, some other methods try to reach a balance betweenmodularity-optimization-based and similarity-based methods. These methods usually run in several stages and take the benefit of one of the strategies at each step. Saoud et al. [33] propose a method that creates initial communities using similarity indexes at the first stage; then, in the second stage, they utilize a modularity-optimization-based method to detect the final communities [33]. The CCGA [34] is a GA that uses the clustering coefficient to create an initial population; then, it uses modularity as the fitness function and attempts to detect communities. In [33], first, researchers assign a value to each edge based on the similarity of its end nodes. After forming the weighted graph, they remove the edges with a lower weight than a specific threshold value. As a result of this process, they obtain some disconnected groups of nodes. In a cleanup procedure, they join smaller components with larger ones. Next, they merge these larger groups based on the number of intermediate edges between them until the modularity score keeps increasing. In a similar approach in [35], they assign weights to the edges of the graph using similarity measures. Then, they find the maximum spanning tree (MST) of the weighted network. They exclude half of the lower weighted edges of this tree and obtain n−1/2 divided components. From this step on, they employ a similar approach to the previous one ([33]) to combine these components. The idea of using MSTs in community detection problems was previously applied by Wu et al. [36]. In their work [36], they estimate the distance of two nodes based on a heuristic approach and allocate a value to each edge of the graph. Then, they extract the minimum spanning tree (mST) of the network and cut the tree in a way that maximizes the distance between the two components.MSTs have been implemented in a variety of other methods and EAs [37]. In this article, we treat the MST of the network as its skeleton. Our method uses similarity indexes to assign weights to the edges of the network. Then, it uses MSTs as the basis to introduce a new representation for the individuals in the community detection problems. Finally, using a new initial population function and a novel mutation function, our method detects the communities using a modularity-optimization-based GA. Therefore, the proposed method stands between the borderlines of similarity-based and modularity-based methods while introducing a new data structure. As far as we know, MSTs have not been implemented to solve community detection problems in this way before. Even though our method is designed for undirected networks, in the case of the existence of a skeleton network (it can be any tree (cycle-less graph) that preserves the local characteristics of the network), it can be implemented on different networks such as temporal networks, directed networks, and multilayer networks [38–40].


## 2.1. Definition-Based Perspective

Newman and Girvan defined “community” based on the nonrandomness of the edges among the nodes. They proposed modularity to measure this feature in different partitions using a null random model [4]. Compared to the other measures, its lower computational complexity and higher accuracy drew the attention of the scientific society toward modularity, which resulted in numerous algorithms based on it. A plethora of research works involves methods that try to solve the community detection problem via the optimization of modularity. These methods are usually referred to as the modularity-optimization algorithms.On the reverse side of themodularity-optimization methods are the algorithms that use local structural information of the network to detect the communities. These algorithms do not focus on the optimization of a specific global measure, such as modularity. One of the widely used methods is known as the label propagation algorithm (LPA) proposed in [11]. LPA is one of the classic algorithms of community detection. LPA starts with assigning a label to each node of the network at the initial step; then, it updates the labels to the most frequent label among their neighbors in a random sequence. In this algorithm, the label of each node corresponds to the community to which the node belongs to. This process quickly ends up in the uniquely labeled subgraphs.A mutually beneficial domain with community detection is link prediction. Hence, numeroussimilarity-based methods use link prediction indexes to measure the similarities among the edges [12]. Cheng et al. show that link prediction can be used to improve the accuracy of community detection methods [8]. The authors in [13] describe some of these similarity measures in the network flow framework and show that some of these similarities are related to different kinds of network flows. As a similarity-based agglomerative method (see 2.2 for further description on agglomerative methods), Castrillo et al. defined a new similarity index based on the well-knowncosine similarity index [14]. Then, starting from the singleton communities, they merge the communities till no weak community remains. Hesamipour et al. use one of these link prediction measures named Adamic/Adar (AA) to determine the central nodes of the network and expand communities around them [9]. They find each central node based on its higher similarity score and its higher distance from other previously selected central nodes. After locating these nodes, they expand the communities around them with a game-theoretic agglomerative approach. The authors in [15] also propose a community detection method using the AA similarity measure. They use the AA to measure the similarity of nodes and form initial communities. Later, they merge these initial communities based on a specific attractiveness index.Some other methods of this category interpret the local information in a probabilistic framework. In [16], they use the proportion of neighbor nodes belonging to each community to estimate the dependency of each node on its own or on the neighbor community and propose an overlapping community detection method. To find the communities, Infomap [17] operates a random walk process and obtains the probabilities for a random walker to pass from each edge. Then, it turns the community detection problem into a minimum length encoding problem and detects the communities using Huffman encoding. In [18], a method is proposed that iteratively removes each edge of the graph to find its overall impact on each node’s entropy. They define the entropy of a specific node as the uncertainty of the destination node for a random walker if it starts from that node.With the growing acceptance of modularity and its extensive use in community detection, researchers turned their attention toward EAs, which are known to be proper algorithms to answer maximization/optimization problems. Although most of the GA-based community detection methods are categorized asmodularity-optimization methods, several methods attempt to optimize other measures. To the best of our knowledge, Bingol et al. made the first attempt to use EAs to detect the communities of a network [19, 20]. They implement the solution-vector representation method to represent each individual in the population pool [20]. A solution vector is an n-dimensional vector (n is the number of nodes) that stores the community identifier of each node in its corresponding element. First, they form the initial population by setting some nodes and their neighbors in the same communities. Later, they use modularity as a fitness function, sort individuals based on their fitness scores, and select some individuals to merge them using a crossover function. Their one-way crossover function chooses a random community from one of the parents (source parent) and transfers it to the destination parent. Finally, they apply a uniform mutation function to change the value of a random gene. In their next work, the same authors proposed a measure named community variance and employed it in a cleanup stage to promote the convergence time of their former method [19]. As we mentioned in Section 1, the goal of community detection is to find subgraphs with dense internal connections and sparse outer links. Modularity reflects both of these conditions within itself. A multiobjective EA is proposed based on these terms in [21]. Multiobjective methods attempt to optimize more than one measure simultaneously. They decompose modularity into two different objective functions to address both terms (dense internal connections and sparse outer links). Finally, they return the individual with the maximum modularity as the solution. Ying et al. used a similar multiobjective conical area EA to detect the communities [22]. Another similar multiobjective approach was also implemented in [23, 24]. GA-net is one of the famous community detection algorithms based on evolutionary methods which does not use modularity as its fitness function [25]. This method proposes a new measure, called community score, to measure the quality of the detected communities and uses it as a fitness function [25]. Yet, the proposed measure on GA-net highly depends on its internal control parameter, and its results change dramatically based on the parameter. In [26], Samie et al. propose another GA that detects communities using the community score measure (the measure proposed by Pizzuti in GA-net [25]). Their method implements an additional cleanup step to absorb some weak communities or single nodes into other communities. Zarei et al. propose a heuristic method for initial population generation, an object migration automata-based method, and a hybrid algorithm based on object migration automata and GA [27]. Their purpose to couple those methods is to avoid getting stuck in local optima.


## 2.2. Methodological Perspective

From the methodological point of view, community detection algorithms are separated intoagglomerative and divisiveclasses. While agglomerative methods start from local structures and expand them to form communities, divisive methods start from the full graph level and try to detect communities by dividing the network into communities. Newman and Girvan introduced modularity along with a divisive modularity-optimization-based community detection algorithm [4]. Their divisive method is based on discarding the edges with high betweenness values from the graph. They construct a hierarchical tree as the communities start to split after removing the edges with high betweenness values. This iterative edge removal process continues until all edges are removed, and a dendrogram is formed from top to bottom. Finally, they cut the dendrogram at a level that gives the maximum modularity. Another method proposed is to form a dendrogram from bottom to top (agglomerative) in [28]. This method is well-known as the fast greedy method. It starts from the singleton communities and merges them following a greedy strategy until no other aggregation can further improve the modularity. Blondel et al. proposed another modularity-based agglomerative method known as Louvain in [29]. Their proposed method operates at two stages; first, it starts from single node communities and merges them subjected to the increase in modularity. Second, it merges these groups of nodes at supernodes. Then, it repeats the process from the beginning on the newly generated graph until no other aggregation could increase the modularity. Later, Traag et al. proposed an improved version of the Louvain called Leiden algorithm [30]. They showed that the Louvain method can lead to disconnected communities and added a refinement stage to prevent it.


## 2.3. Data Structure-Based Perspective

The extraction of an underlying structure of the given network is a usual practice in community detection algorithms. This underlying structure is usually called askeleton network and represents a summary of the main network. The recently trending data structure-based methods are based on the idea of transforming a network to another data structure, such as a tree [10]. These methods use a new data structure either to reveal some of the hidden characteristics of the network or to reduce the complexity of the problem.In [31], the authors propose a method called EdMot. Using triangle connections, EdMot forms a new graph. Then, it finds the densely connected components of this newly formed graph and adds extra edges to them. The resultant network summarizes both lower-level and higher-level connections and highlights the communities. Another method called WATSET [32] proposes a metaheuristic way that uses a fuzzy method to create a sense graph in the first stage. In the next stage, it detects the crisp communities with the help of the new data structure.


## 2.4. Combinatorial Perspective

On the other hand, some other methods try to reach a balance betweenmodularity-optimization-based and similarity-based methods. These methods usually run in several stages and take the benefit of one of the strategies at each step. Saoud et al. [33] propose a method that creates initial communities using similarity indexes at the first stage; then, in the second stage, they utilize a modularity-optimization-based method to detect the final communities [33]. The CCGA [34] is a GA that uses the clustering coefficient to create an initial population; then, it uses modularity as the fitness function and attempts to detect communities. In [33], first, researchers assign a value to each edge based on the similarity of its end nodes. After forming the weighted graph, they remove the edges with a lower weight than a specific threshold value. As a result of this process, they obtain some disconnected groups of nodes. In a cleanup procedure, they join smaller components with larger ones. Next, they merge these larger groups based on the number of intermediate edges between them until the modularity score keeps increasing. In a similar approach in [35], they assign weights to the edges of the graph using similarity measures. Then, they find the maximum spanning tree (MST) of the weighted network. They exclude half of the lower weighted edges of this tree and obtain n−1/2 divided components. From this step on, they employ a similar approach to the previous one ([33]) to combine these components. The idea of using MSTs in community detection problems was previously applied by Wu et al. [36]. In their work [36], they estimate the distance of two nodes based on a heuristic approach and allocate a value to each edge of the graph. Then, they extract the minimum spanning tree (mST) of the network and cut the tree in a way that maximizes the distance between the two components.MSTs have been implemented in a variety of other methods and EAs [37]. In this article, we treat the MST of the network as its skeleton. Our method uses similarity indexes to assign weights to the edges of the network. Then, it uses MSTs as the basis to introduce a new representation for the individuals in the community detection problems. Finally, using a new initial population function and a novel mutation function, our method detects the communities using a modularity-optimization-based GA. Therefore, the proposed method stands between the borderlines of similarity-based and modularity-based methods while introducing a new data structure. As far as we know, MSTs have not been implemented to solve community detection problems in this way before. Even though our method is designed for undirected networks, in the case of the existence of a skeleton network (it can be any tree (cycle-less graph) that preserves the local characteristics of the network), it can be implemented on different networks such as temporal networks, directed networks, and multilayer networks [38–40].


## 3. Definitions

In this section, we provide some insights about the preliminaries and definitions necessary to continue the discussion.


### 3.1. Graph

We useG to represent a graph. A graph is nothing but a tuple of V,E in which V refers to a set of nodes, and E is the set of edges that connect two nodes E=v,uv,u∈V2. In this article, we focus on the unweighted and undirected graphs. In these graphs, in the case of the presence of an edge such as ez∈E between two nodes v,u∈V, we will have ez=u,v=v,u. For each node v, we call the nodes which have a direct edge with v its neighbors and show them by Γv. The degree of a node is equal to the number of nodes contained in the neighborhood of that node dv=Γv. Also, we use V=n and E=m to represent the number of nodes and edges of a graph. The same definition differs slightly in the weighted networks. A weighted network is a triplet such as Gw=V,E,w consisting of a set of nodes V, a set of edges E, and a mapping function w that maps each edge to a real number w:E⟶R.


### 3.2. Community

Although there are different definitions for the notion of the community [9, 41], there seems to be a consensus on the definition of a community as the nodes are densely interconnected and have fewer outer links. Therefore, assuming Ci as the i-th community of a network, the following should apply to it:(1)∑i=1ku,vu,v∈E,u∈Ci,v∈Ci≫∑i,ju,vu,v∈E,u∈Ci,v∈Cj,i≠j.In cases where a node could become a member of more than one community, we would call them overlapping communities. In this article, we concentrate on nonoverlapping communitiesCi∩Cj=∅. Additionally, having that a node should be a member of at least one community, we have ∪i=1kCi=V. The set of nonoverlapping communities that divide a network into subgraphs is called a partition P=C1,C2,…,Ck;i≠j for i,j∈1,…,k.


### 3.3. Minimum/Maximum Spanning Trees

A minimum/maximum spanning tree is a tree derived from a weighted graph that involves all of the graph’s nodes and a subset of its edges where the sum of their weights is the minimum/maximum possible value. A spanning tree always hasE=n−1 edges where cutting each of them divides the tree. In the proposed method, we take advantage of this feature and use the terms of broken edge or border edge to denote the edges that were cut to split the spanning tree. In this article, we denote a maximum spanning tree with MST and a minimum spanning tree with mST. Naturally, one can construct both of them with the same method by simply inverting the weights of the edges. Here, we use the well-knownPrim algorithm to find the corresponding MST of a graph [42].


## 3.1. Graph

We useG to represent a graph. A graph is nothing but a tuple of V,E in which V refers to a set of nodes, and E is the set of edges that connect two nodes E=v,uv,u∈V2. In this article, we focus on the unweighted and undirected graphs. In these graphs, in the case of the presence of an edge such as ez∈E between two nodes v,u∈V, we will have ez=u,v=v,u. For each node v, we call the nodes which have a direct edge with v its neighbors and show them by Γv. The degree of a node is equal to the number of nodes contained in the neighborhood of that node dv=Γv. Also, we use V=n and E=m to represent the number of nodes and edges of a graph. The same definition differs slightly in the weighted networks. A weighted network is a triplet such as Gw=V,E,w consisting of a set of nodes V, a set of edges E, and a mapping function w that maps each edge to a real number w:E⟶R.


## 3.2. Community

Although there are different definitions for the notion of the community [9, 41], there seems to be a consensus on the definition of a community as the nodes are densely interconnected and have fewer outer links. Therefore, assuming Ci as the i-th community of a network, the following should apply to it:(1)∑i=1ku,vu,v∈E,u∈Ci,v∈Ci≫∑i,ju,vu,v∈E,u∈Ci,v∈Cj,i≠j.In cases where a node could become a member of more than one community, we would call them overlapping communities. In this article, we concentrate on nonoverlapping communitiesCi∩Cj=∅. Additionally, having that a node should be a member of at least one community, we have ∪i=1kCi=V. The set of nonoverlapping communities that divide a network into subgraphs is called a partition P=C1,C2,…,Ck;i≠j for i,j∈1,…,k.


## 3.3. Minimum/Maximum Spanning Trees

A minimum/maximum spanning tree is a tree derived from a weighted graph that involves all of the graph’s nodes and a subset of its edges where the sum of their weights is the minimum/maximum possible value. A spanning tree always hasE=n−1 edges where cutting each of them divides the tree. In the proposed method, we take advantage of this feature and use the terms of broken edge or border edge to denote the edges that were cut to split the spanning tree. In this article, we denote a maximum spanning tree with MST and a minimum spanning tree with mST. Naturally, one can construct both of them with the same method by simply inverting the weights of the edges. Here, we use the well-knownPrim algorithm to find the corresponding MST of a graph [42].


## 4. Proposed Algorithm

In this section, we illustrate the details of the proposed method. First, we start by explaining the precomputation and encoding procedure in Section4.1. Next, we describe the initial population generation method in 4.2; then, we define the details of selection, crossover, and mutation functions in Sections 4.3–4.5, respectively.


### 4.1. Representation

Most GA-based community detection methods uselocus-based representation to encode the individuals of the population [23]. In this representation, each chromosome consists of n genes referring to a node in the network. In the locus-based representation, the value of each gene gv=u refers to the identifier of one of the nodes and specifies that these two nodes belong to the same community u,v∈Ci. In practical implementations, they often change the domain of each gene to the neighborhood of the corresponding node gv∈Γv. Although using a locus-based representation may be necessary for other applications, this domain can have redundancies for a community detection problem. For example, in Figure 1(a), selecting different neighbors for node 2 would not affect the outcome because all of its neighbors belong to the same community. Yet, if a mutation happens on this node, the fitness value of the individual has to be recomputed. Besides, if we use the locus-based representation, we should make an additional random/educated choice from the scope of the neighbors of each node (gene). Another method for representing individuals is the solution-vector representation. This method also holds a gene for each node in every individual. But, in this scheme, taking into account that the graph has k communities, one has to choose a value between 1 and k for each gene, indicating the identifier of the community to which the node belongs [21, 27]. Although this method eliminates the need to label the members of a community in an additional pass, it might result in disconnected communities and violate the definition of community (3). Figure 1(b) shows such a scenario.Figure 1
Comparison of different representation schemes and their corresponding graphs. (a) An individual created by the locus-based method. As it can be seen, using this method might cause meaningless mutations, (b) an individual created by the solution-vector method. Using this method might result in separated communities, and (c) MST-based representation. This method reduces the domain of each element to binary and avoids meaningless mutations and separated communities.
(a)(b)(c)To avoid such errors, we propose a new method to encode individuals. In this method, which we callMST-based representation, with the cost of sacrificing some possible combinations of the nodes, the problems such as the effectless mutations and disconnected communities are resolved. Furthermore, by reducing the domain of a gene to a binary digit, our method brings community detection problems closer to the classic GAs [52]. To create such a representation, first, we assign a value to each edge of the graph using one of the node similarity/link prediction indexes. Table 1 lists some of the well-known and recent indexes. In the resulting weighted graph, the weight of each edge refers to the similarity of its two end nodes. After assigning weights to the edges, we find a corresponding MST of the graph. As we have described in Section 3, each MST has n−1 edges where discarding each of them splits the tree into two parts. Instead of encoding individuals based on the nodes, we encode them based on the edges. Hence, in the MST-based representation, each individual will have n−1 genes with a binary domain. The value of each gene expresses the state of the corresponding edge on the MST tree. We use 1 to indicate a broken edge and 0 to refer to a connected edge. The MST-based representation of a given partition for the example graph is shown in Figure 1(c). As illustrated in the figure, using the MST-based representation causes a significant change by each mutation where even a mutation on an internal edge such as 13and14 results in a brand new partition. It is obvious that using such a representation makes some combinations impossible. For example, because of the absence of an edge between nodes #5 and #9 in the MST, forming a community consisting of just these two nodes is impossible. Yet, considering the mutually beneficial relationship between community detection and node similarity/link prediction, having communities with less similar nodes is unlikely to be desirable [8, 12]. Therefore, considering the fact that the weight assignation process has already highlighted the edges with more similar end nodes, we can be assured that we are only neglecting the communities that might have sparse intracommunity connections. Consequently, MST-based representation can reduce the search scope of the problem. Thus, the amount of information loss caused by this representation is negligible regarding its various advantages compared to the other representations. On the other hand, this representation can be applied to different types of networks (such as temporal networks and directed networks) if an application-specificskeleton network is used instead of an mST.Table 1
Some of the widely used node similarity measures.
MeasureFormulaDescriptionCommon neighborsΓv∩ΓuA simple method that calculates the similarity of two nodes based on the number of their common neighbors [43].JaccardΓv∩Γu/Γv∪ΓuThis method brings the similarity score of two nodes between 0 and 1 by dividing the number of common neighbors among them by the number of nodes in the union of their neighborhoods [44].Cosine similarityΓv∩Γu/Γv×ΓuThis measure computes the cosine of the degree between two columns of the adjacency matrix [45].Hub promoted index (HPI)Γv∩Γu/minΓv,ΓuThis measure is designed to maximize the impact of higher-degree nodes [46].Adamic/Adar (AA)∑k∈Γv∩Γu1/logΓkThis measure reduces the impact of very high-degree nodes by summing the inverse logarithm of the degrees of nodes [47].Resource Allocation Index (RA)∑k∈Γv∩Γu1/ΓkThis measure calculates the possibility that the intermediate nodes pass the resource they have taken from u to v [48].Common neighbors degree penalization (CNDP)∑k∈Γv∩ΓuCkΓk−βC¯This method computes the similarity between two nodes using the common neighbors ofk which consist of the common neighbors of u and vCk, number of neighbors of kΓk with the power of average clustering coefficient C¯ times a constant(β, thus, we defined β=1.76) [49].Similarity-based on random walk (SRW)∑l=2TΓu/2E⋅πu,vl+Γv/2E⋅πv,ulHere, the random walk transition matrix of the graphπ is used to compute the similarity between two nodes. We have set T=5 in our experiments [50].Hybrid influence of neighbors (HIN)∑l=2TΓu¯⋅hu¯/2E⋅πu,vl+Γv¯⋅hv¯/2E⋅πv,ulThis measure is a generalization of the SRW measure which uses both the average degree and the average h-indexes of the neighbors. We have setT=5 in our experiments [51].


### 4.2. Initial Population Generation

Although GAs usually perform the search process with a pool of randomly created individuals, if we could start the process from a more rational initial population (a nonrandom pool), we could improve the convergence time of the process [19, 20]. Even though the number of nodes of each community depends on the edges among them, observations suggest that the size of the communities increases depending on the size of the network. Taking the size of the clusters/communities equal to n (n is the number of nodes) is a common hypothesis in clustering/community detection problems [53, 54]. We use this assumption to form initial individuals. First, we define a visited flag. Then, we start from a random edge. If the visited flag of the end nodes of the selected edge is not already set, we set their flags and explore other edges connected to them while counting the number of nodes that we have visited so far. We keep exploring the edges in a Breadth-First Search (BFS) order until either we encounter a broken edge (an edge whose corresponding gene has a value of 1 or the number of the nodes of the community exceeds the threshold of n. After exploring each edge, we set its end nodes’ visited flags and consider both of them as members of the same community. After reaching the determined threshold, we set the value of corresponding genes of all of the remaining edges in the queue equal to 1, meaning that these edges are broken. In case the process reaches broken edges before the number of nodes reaches n, and it cannot find a nonbroken edge to expand the community, we change the value of one of the broken edges to 0 (meaning that we connect it again). This procedure is repeated until all of the MST edges are processed. Figure 2 shows the process of forming an initial individual for the example network in Figure 1. The random selection order of edges to create an individual similar to the one in the figure is ((4, 2), (5, 8), (10, 11), (9, 8), (3, 2), (7, 8), (11, 13), (12, 11), (1, 2), (6, 10), (14, 13), (5, 4), and (5, 6)). The pseudocode for creating individuals for the initial population is given in Algorithms 1 and 2. The BFS-mod function in Algorithm-2 is a slightly modified version of the BFS algorithm that stops the procedure and returns the broken edges, the updated visited vector, and the updated chromosome after reaching the termination conditions. Experimental results prove that individuals created using this method have better fitness values and can accelerate the convergence time of the process (Section 5).Figure 2
The initial population generation procedure is explained from left to right. (a) The edge (4, 2) gets chosen, and its end nodes (the nodes connected to both ends of the edge) get assigned to the corresponding community. The edges of node 2 get processed, and the procedure reaches the predefined threshold⌈n⌉=⌈14⌉=4, stops the expansion of the community, and chooses another edge; (b) the edge (5, 8) gets chosen, and its end nodes get assigned to the community. The broken edge between 5 and 4 gets ignored, but node 6 gets added to the community. The (8, 9) edge gets processed, and, by adding node 9, the community’s size reaches the threshold value. The rest of the edges in the queue get broken. (c) The edge between 10 and 11 gets chosen, and the community gets expanded around the node 11. (d) The edge between 7 and 8 gets chosen, and because it does not reach the threshold limit, the broken edge gets reconnected. (e) (13, 14) gets chosen, and the broken edge gets reconnected because the community members fail to reach the threshold value.
(a)(b)(c)(d)(e)Algorithm 1: The pseudocode of initial population generation is explained in 4.2.
Input.MSTof the networkOutput.returns a vector representing an individual of initial populationg⟶(1)
procedureInitGen(MST)(2)
V⟶⟵ a zero vector with the length of n ⊳ indicating if a node has been visited or not(3)
g⟶⟵ a vector that represents genes of an individual ⊳ n−1 genes for n−1 edges in the MST(4)
B⟵ add a random edge to the queue(5)
whileB is not empty do(6)
edge⟵B.pop(7)
node1⟵edge.end_node0(8)
node2⟵edge.end_node1(9)
ifV⟶node1=0then(10)
b,V⟶,g⟶⟵BFS_modnode1,node2,V⟶,g⟶(11)
add the new broken edgesb to B(12)
else ifV⟶node2=0then(13)
b,V⟶,g⟶⟵BFS_modnode2,node1,V⟶,g⟶(14)
add the new broken edgesb to BAlgorithm 2: The pseudocode of the modified version of the BFS algorithm to produce initial population generation is explained in 4.2.
Input.sNode. the direction that we will start to expand the edges; nNode. the neighbor node; V⟶. the visited vector of the nodes; g⟶. the genes vector.Output.returns the new broken edgesb, updated visited vectorV⟶and the updated genes vectorg⟶(1)
procedureBFS-mod(sNode,nNode, V,g)(2)
S⟶⟵sNode(3)
N⟶⟵nNode(4)
t=0(5)
whileS⟶ is not empty do(6)
n1⟵S⟶.pop(7)
n2⟵N⟶.pop(8)
ift<nthen(9)
V⟶n1=1(10)
t=t+1(11)
for each node∈Γn1do(12)
ifV⟶nodethen(13)
addNode to S⟶(14)
addn1 to N⟶(15)
else(16)
ifg⟶n1,node=1then(17)
addn1,node to b(18)
else(19)
g⟶n1,node⟵1(20)
addn1,node to b(21)
ift<nthen(22)
randEdge⟵ a random edge from b(23)
g⟶randEdge⟵0(24)
returnb,V⟶,g⟶


### 4.3. Selection

The goal of the selection phase is to keep the appropriate individuals and discard the weak ones. A fitness function is necessary to evaluate the quality of individuals. Modularity is one of the most popular measures to determine the quality of a partition. Most GAs use this measure as their fitness function for community detection problems. The details about the modularity are described in Section5.1. One of the important characteristics of modularity is its additiveness [41]. An additive function could be written as the sum of another elementary function. In other words, for a partition such as P and an additive measure Q has an elementary function such as q., such that(2)QP=∑C∈PqC.TheqC function for modularity is expressed as(3)qC=lCm−dC2m,where m is the number of edges, C denotes a community, lC denotes the number of edges connected to the nodes of the community C, and dC represents the sum of the degrees of the nodes in C. An increase in the value of this function indicates a strong community structure. Now, we can simply replace qC in equation (2) to rewrite (11) as follows:(4)QP=∑C∈PlCm−dC2m.Using this characteristic of modularity, we reduce some of the unnecessary computations by keeping a complementary list for each individual. This list’s length is equal to the number of communities and will contain each community’s respective modularity within its elements. Therefore, in the case of the occurrence of a mutation or crossover, we would be able to only calculate the modularity of the modified communities.After obtaining the modularity value for each individual, we use the roulette wheel selection method. Using this method, the possibility of selecting an individual is equal to the ratio of its fitness value to the sum of the fitness values of all individuals. This method increases the chance of selecting better individuals based on their fitness scores. Assumingpx as the probability of selecting an individual x, we can calculate it by using the following formula:(5)px=Qx∑y∈ΩQy,where Ω indicates the population space. After calculating the probability of each individual, the cumulative probability is computed as follows:(6)px^=∑i=1xpi.Now, having chosen a random number between 0 and 1 such asr (with uniform probability), we will select the k th individual if and only if p^k−1≤r≤p^k. In our method, we keep the population space size constant through generations. In each generation, we select Ω/2 couple of individuals using the roulette wheel selection method. Then, we implement a crossover function (Section 4.4) to produce new individuals. After implementing the mutation function (Section 4.5) over a specific ratio of these individuals, we add them to the population space. Finally, we sort the resulting individuals Ω+Ω/2 based on their fitness values and select the Ω fittest one to transfer to the next generation.


### 4.4. Crossover

The crossover function is carried out to merge qualified individuals and create new ones. In [55], some common crossover functions have been reviewed. As we have described in Section 4.3, we have defined a complementary list to keep the modularity of each community in hand. Here, we use a similar method as in [56] as our crossover function. In this method, first, we sort the communities of both parents based on their modularity scores. Then, we move the corresponding genes of each of these communities to the child individual. If some of the genes of a parent community have already been assigned to the child by another community, it gets fragmented. This method iterates through all parent communities until all of the genes of the child individual are determined.Figure3 describes the crossover function step by step. It should be noted that by transmitting each community to the child individual, its modularity value also gets transmitted unless the community is fragmented. Thus, we will not need to recompute the fitness value for all communities. Instead, once the child individual is formed, we compute modularity only for the fragmented communities by using formula (4) and add the values of the rest of the communities.Figure 3
The crossover procedure to create a new individual. (a) The graph, individual, and community vector of the first parent, (b) the graph, individual, and community vector of the second parent, and (c) new individual, to create the new individual first, we sort the communities of both parents in descending order of their modularities; then, we select the communities from best to worst, respectively. TheC2,5, C2,1, and C1,3 communities get added first. Then, C1,4 gets selected, but because #10, #11, and #12 nodes are already assigned to other communities, and a new singleton community gets formed for node #6.
(a)(b)(c)


### 4.5. Mutation

A mutation function is used in GAs to add to the diversity of population space. Using this function, one or more genes of each individual gets modified. Here, we describe three different mutation functions, two constant, and one new adaptive function.


#### 4.5.1. Uniform-Based

One of the famous mutation functions is the uniform mutation function. This function assigns an equal chance for each gene to get elected for mutation. This probability would be equal to1/n−1 for the MST-based representation. To select the gene, we create a random number between 1 and n−1 (with a uniform probability). As we have mentioned previously, one of the advantages of binary representations is the reduction of the value domain for each gene. While choosing the value of the mutated gene requires a random or educated selection in the locus-based and solution-vector-based methods (selecting another neighbor in locus-based or selecting another community identifier in the solution-vector-based method), it is enough to perform a negation in a binary representation.


#### 4.5.2. Weight-Based

Also, we examined a nonuniform mutation function in our experiments. As its name suggests, a nonuniform function does not assign equal probabilities to each gene. We form this distribution based on the weights of the corresponding edges of the network’s MST. To generate the probabilities, we divide the weight of each edge into the sum of the weights of all edges of the MST. Again, we negate the value of the genes which were selected during the mutation procedure.


#### 4.5.3. Sine-Based

Yet, we also introduce a new adaptive mutation function based on the depths of the corresponding edges of each gene. As discussed in 4.1, each gene in theMST-based representation refers to an edge in the graph’s MST. In some cases, it might be meaningful to keep internal edges untouched while directing the mutations to border edges or vice versa. Our aim in this function is to examine the effectiveness of this theory. In this method, we assign the probability of each gene concerning its corresponding distance from the broken edges of its community. Figure 4 can help us describe our function. For example, Figure 4(a) shows a distribution that puts more weight on the border edges (intercommunity edges on MST) of the communities. In this figure, points with peak values indicate the border edges, and as we move to the depth of each community, the value decreases, and then it starts to rise as we move closer to the next border edge. Using a distribution similar to Figure 4(a) causes a reduction in the chance of a mutation on internal edges. The reverse situation occurs when a distribution similar to Figure 4(c) is used. Figure 4(b) displays a situation where each gene has the same chance of mutation. To form such a distribution, first, we create a vector such as w⟶ with the length of n−1 and assign the value of 1 for the corresponding elements of broken edges. Then, for each broken edge, we start to navigate the edges connecting to its end nodes in a BFS order until we reach another broken edge. For each navigated edge, we change its corresponding w⟶ value as follows:(7)w⟶i=w⟶i+α⋅2−1/d+1−α⋅1−2−1/d,where the index of the gene is denoted with i, d indicates its distance from the border edge, and α is a control parameter. Assigning 1 to α will produce a distribution such as the one shown in Figure 4(c) while α=0 will result in a distribution such as the one shown in Figure 4(a). Assigning 0.5 to the α will result in a uniform distribution. In our method, α is a self-adaptive parameter. It oscillates between 0 and 1 based on the change in the modularity of the best individual of each generation. If the fitness value of the best individual improves in the last generation, α remains unchanged while it changes as follows in the opposite condition:(8)αq=αq−1,if.fitnessimproves,sinzq,Else.zq=π6+q⋅δ⋅π,where δ is a user-defined constant to determine the length of each step and q is the index of the generation. After performing the described process using all of the broken edges of the individuals, we transform the values of the w⟶ vector between 0 and 1 and use it as the probability distribution function of the mutation function. We hypothesize that this adaptive method can result in mutations that can separate or merge the communities in a better way by adjusting the slope of the mutation probability function based on the improvement of the quality of the best individual in the pool. Figure 5 describes the effect of δ on determining α.Figure 4
The effect ofα on the shape of the probability distribution. (a) α parameter has been set equal to 0, and mutation probability is directed toward border edges, (b) setting α=0.5 results in a uniform probability distribution, and (c) shows the probability distribution of the edges when α=1. The mutation probability of inner edges is increased.
(a)(b)(c)Figure 5
Function ofαq=sinzq oscillates between 0 and 1, causing the mutation probability distribution to change. δ defines the length of each step δ=0.1.


## 4.1. Representation

Most GA-based community detection methods uselocus-based representation to encode the individuals of the population [23]. In this representation, each chromosome consists of n genes referring to a node in the network. In the locus-based representation, the value of each gene gv=u refers to the identifier of one of the nodes and specifies that these two nodes belong to the same community u,v∈Ci. In practical implementations, they often change the domain of each gene to the neighborhood of the corresponding node gv∈Γv. Although using a locus-based representation may be necessary for other applications, this domain can have redundancies for a community detection problem. For example, in Figure 1(a), selecting different neighbors for node 2 would not affect the outcome because all of its neighbors belong to the same community. Yet, if a mutation happens on this node, the fitness value of the individual has to be recomputed. Besides, if we use the locus-based representation, we should make an additional random/educated choice from the scope of the neighbors of each node (gene). Another method for representing individuals is the solution-vector representation. This method also holds a gene for each node in every individual. But, in this scheme, taking into account that the graph has k communities, one has to choose a value between 1 and k for each gene, indicating the identifier of the community to which the node belongs [21, 27]. Although this method eliminates the need to label the members of a community in an additional pass, it might result in disconnected communities and violate the definition of community (3). Figure 1(b) shows such a scenario.Figure 1
Comparison of different representation schemes and their corresponding graphs. (a) An individual created by the locus-based method. As it can be seen, using this method might cause meaningless mutations, (b) an individual created by the solution-vector method. Using this method might result in separated communities, and (c) MST-based representation. This method reduces the domain of each element to binary and avoids meaningless mutations and separated communities.
(a)(b)(c)To avoid such errors, we propose a new method to encode individuals. In this method, which we callMST-based representation, with the cost of sacrificing some possible combinations of the nodes, the problems such as the effectless mutations and disconnected communities are resolved. Furthermore, by reducing the domain of a gene to a binary digit, our method brings community detection problems closer to the classic GAs [52]. To create such a representation, first, we assign a value to each edge of the graph using one of the node similarity/link prediction indexes. Table 1 lists some of the well-known and recent indexes. In the resulting weighted graph, the weight of each edge refers to the similarity of its two end nodes. After assigning weights to the edges, we find a corresponding MST of the graph. As we have described in Section 3, each MST has n−1 edges where discarding each of them splits the tree into two parts. Instead of encoding individuals based on the nodes, we encode them based on the edges. Hence, in the MST-based representation, each individual will have n−1 genes with a binary domain. The value of each gene expresses the state of the corresponding edge on the MST tree. We use 1 to indicate a broken edge and 0 to refer to a connected edge. The MST-based representation of a given partition for the example graph is shown in Figure 1(c). As illustrated in the figure, using the MST-based representation causes a significant change by each mutation where even a mutation on an internal edge such as 13and14 results in a brand new partition. It is obvious that using such a representation makes some combinations impossible. For example, because of the absence of an edge between nodes #5 and #9 in the MST, forming a community consisting of just these two nodes is impossible. Yet, considering the mutually beneficial relationship between community detection and node similarity/link prediction, having communities with less similar nodes is unlikely to be desirable [8, 12]. Therefore, considering the fact that the weight assignation process has already highlighted the edges with more similar end nodes, we can be assured that we are only neglecting the communities that might have sparse intracommunity connections. Consequently, MST-based representation can reduce the search scope of the problem. Thus, the amount of information loss caused by this representation is negligible regarding its various advantages compared to the other representations. On the other hand, this representation can be applied to different types of networks (such as temporal networks and directed networks) if an application-specificskeleton network is used instead of an mST.Table 1
Some of the widely used node similarity measures.
MeasureFormulaDescriptionCommon neighborsΓv∩ΓuA simple method that calculates the similarity of two nodes based on the number of their common neighbors [43].JaccardΓv∩Γu/Γv∪ΓuThis method brings the similarity score of two nodes between 0 and 1 by dividing the number of common neighbors among them by the number of nodes in the union of their neighborhoods [44].Cosine similarityΓv∩Γu/Γv×ΓuThis measure computes the cosine of the degree between two columns of the adjacency matrix [45].Hub promoted index (HPI)Γv∩Γu/minΓv,ΓuThis measure is designed to maximize the impact of higher-degree nodes [46].Adamic/Adar (AA)∑k∈Γv∩Γu1/logΓkThis measure reduces the impact of very high-degree nodes by summing the inverse logarithm of the degrees of nodes [47].Resource Allocation Index (RA)∑k∈Γv∩Γu1/ΓkThis measure calculates the possibility that the intermediate nodes pass the resource they have taken from u to v [48].Common neighbors degree penalization (CNDP)∑k∈Γv∩ΓuCkΓk−βC¯This method computes the similarity between two nodes using the common neighbors ofk which consist of the common neighbors of u and vCk, number of neighbors of kΓk with the power of average clustering coefficient C¯ times a constant(β, thus, we defined β=1.76) [49].Similarity-based on random walk (SRW)∑l=2TΓu/2E⋅πu,vl+Γv/2E⋅πv,ulHere, the random walk transition matrix of the graphπ is used to compute the similarity between two nodes. We have set T=5 in our experiments [50].Hybrid influence of neighbors (HIN)∑l=2TΓu¯⋅hu¯/2E⋅πu,vl+Γv¯⋅hv¯/2E⋅πv,ulThis measure is a generalization of the SRW measure which uses both the average degree and the average h-indexes of the neighbors. We have setT=5 in our experiments [51].


## 4.2. Initial Population Generation

Although GAs usually perform the search process with a pool of randomly created individuals, if we could start the process from a more rational initial population (a nonrandom pool), we could improve the convergence time of the process [19, 20]. Even though the number of nodes of each community depends on the edges among them, observations suggest that the size of the communities increases depending on the size of the network. Taking the size of the clusters/communities equal to n (n is the number of nodes) is a common hypothesis in clustering/community detection problems [53, 54]. We use this assumption to form initial individuals. First, we define a visited flag. Then, we start from a random edge. If the visited flag of the end nodes of the selected edge is not already set, we set their flags and explore other edges connected to them while counting the number of nodes that we have visited so far. We keep exploring the edges in a Breadth-First Search (BFS) order until either we encounter a broken edge (an edge whose corresponding gene has a value of 1 or the number of the nodes of the community exceeds the threshold of n. After exploring each edge, we set its end nodes’ visited flags and consider both of them as members of the same community. After reaching the determined threshold, we set the value of corresponding genes of all of the remaining edges in the queue equal to 1, meaning that these edges are broken. In case the process reaches broken edges before the number of nodes reaches n, and it cannot find a nonbroken edge to expand the community, we change the value of one of the broken edges to 0 (meaning that we connect it again). This procedure is repeated until all of the MST edges are processed. Figure 2 shows the process of forming an initial individual for the example network in Figure 1. The random selection order of edges to create an individual similar to the one in the figure is ((4, 2), (5, 8), (10, 11), (9, 8), (3, 2), (7, 8), (11, 13), (12, 11), (1, 2), (6, 10), (14, 13), (5, 4), and (5, 6)). The pseudocode for creating individuals for the initial population is given in Algorithms 1 and 2. The BFS-mod function in Algorithm-2 is a slightly modified version of the BFS algorithm that stops the procedure and returns the broken edges, the updated visited vector, and the updated chromosome after reaching the termination conditions. Experimental results prove that individuals created using this method have better fitness values and can accelerate the convergence time of the process (Section 5).Figure 2
The initial population generation procedure is explained from left to right. (a) The edge (4, 2) gets chosen, and its end nodes (the nodes connected to both ends of the edge) get assigned to the corresponding community. The edges of node 2 get processed, and the procedure reaches the predefined threshold⌈n⌉=⌈14⌉=4, stops the expansion of the community, and chooses another edge; (b) the edge (5, 8) gets chosen, and its end nodes get assigned to the community. The broken edge between 5 and 4 gets ignored, but node 6 gets added to the community. The (8, 9) edge gets processed, and, by adding node 9, the community’s size reaches the threshold value. The rest of the edges in the queue get broken. (c) The edge between 10 and 11 gets chosen, and the community gets expanded around the node 11. (d) The edge between 7 and 8 gets chosen, and because it does not reach the threshold limit, the broken edge gets reconnected. (e) (13, 14) gets chosen, and the broken edge gets reconnected because the community members fail to reach the threshold value.
(a)(b)(c)(d)(e)Algorithm 1: The pseudocode of initial population generation is explained in 4.2.
Input.MSTof the networkOutput.returns a vector representing an individual of initial populationg⟶(1)
procedureInitGen(MST)(2)
V⟶⟵ a zero vector with the length of n ⊳ indicating if a node has been visited or not(3)
g⟶⟵ a vector that represents genes of an individual ⊳ n−1 genes for n−1 edges in the MST(4)
B⟵ add a random edge to the queue(5)
whileB is not empty do(6)
edge⟵B.pop(7)
node1⟵edge.end_node0(8)
node2⟵edge.end_node1(9)
ifV⟶node1=0then(10)
b,V⟶,g⟶⟵BFS_modnode1,node2,V⟶,g⟶(11)
add the new broken edgesb to B(12)
else ifV⟶node2=0then(13)
b,V⟶,g⟶⟵BFS_modnode2,node1,V⟶,g⟶(14)
add the new broken edgesb to BAlgorithm 2: The pseudocode of the modified version of the BFS algorithm to produce initial population generation is explained in 4.2.
Input.sNode. the direction that we will start to expand the edges; nNode. the neighbor node; V⟶. the visited vector of the nodes; g⟶. the genes vector.Output.returns the new broken edgesb, updated visited vectorV⟶and the updated genes vectorg⟶(1)
procedureBFS-mod(sNode,nNode, V,g)(2)
S⟶⟵sNode(3)
N⟶⟵nNode(4)
t=0(5)
whileS⟶ is not empty do(6)
n1⟵S⟶.pop(7)
n2⟵N⟶.pop(8)
ift<nthen(9)
V⟶n1=1(10)
t=t+1(11)
for each node∈Γn1do(12)
ifV⟶nodethen(13)
addNode to S⟶(14)
addn1 to N⟶(15)
else(16)
ifg⟶n1,node=1then(17)
addn1,node to b(18)
else(19)
g⟶n1,node⟵1(20)
addn1,node to b(21)
ift<nthen(22)
randEdge⟵ a random edge from b(23)
g⟶randEdge⟵0(24)
returnb,V⟶,g⟶


## 4.3. Selection

The goal of the selection phase is to keep the appropriate individuals and discard the weak ones. A fitness function is necessary to evaluate the quality of individuals. Modularity is one of the most popular measures to determine the quality of a partition. Most GAs use this measure as their fitness function for community detection problems. The details about the modularity are described in Section5.1. One of the important characteristics of modularity is its additiveness [41]. An additive function could be written as the sum of another elementary function. In other words, for a partition such as P and an additive measure Q has an elementary function such as q., such that(2)QP=∑C∈PqC.TheqC function for modularity is expressed as(3)qC=lCm−dC2m,where m is the number of edges, C denotes a community, lC denotes the number of edges connected to the nodes of the community C, and dC represents the sum of the degrees of the nodes in C. An increase in the value of this function indicates a strong community structure. Now, we can simply replace qC in equation (2) to rewrite (11) as follows:(4)QP=∑C∈PlCm−dC2m.Using this characteristic of modularity, we reduce some of the unnecessary computations by keeping a complementary list for each individual. This list’s length is equal to the number of communities and will contain each community’s respective modularity within its elements. Therefore, in the case of the occurrence of a mutation or crossover, we would be able to only calculate the modularity of the modified communities.After obtaining the modularity value for each individual, we use the roulette wheel selection method. Using this method, the possibility of selecting an individual is equal to the ratio of its fitness value to the sum of the fitness values of all individuals. This method increases the chance of selecting better individuals based on their fitness scores. Assumingpx as the probability of selecting an individual x, we can calculate it by using the following formula:(5)px=Qx∑y∈ΩQy,where Ω indicates the population space. After calculating the probability of each individual, the cumulative probability is computed as follows:(6)px^=∑i=1xpi.Now, having chosen a random number between 0 and 1 such asr (with uniform probability), we will select the k th individual if and only if p^k−1≤r≤p^k. In our method, we keep the population space size constant through generations. In each generation, we select Ω/2 couple of individuals using the roulette wheel selection method. Then, we implement a crossover function (Section 4.4) to produce new individuals. After implementing the mutation function (Section 4.5) over a specific ratio of these individuals, we add them to the population space. Finally, we sort the resulting individuals Ω+Ω/2 based on their fitness values and select the Ω fittest one to transfer to the next generation.


## 4.4. Crossover

The crossover function is carried out to merge qualified individuals and create new ones. In [55], some common crossover functions have been reviewed. As we have described in Section 4.3, we have defined a complementary list to keep the modularity of each community in hand. Here, we use a similar method as in [56] as our crossover function. In this method, first, we sort the communities of both parents based on their modularity scores. Then, we move the corresponding genes of each of these communities to the child individual. If some of the genes of a parent community have already been assigned to the child by another community, it gets fragmented. This method iterates through all parent communities until all of the genes of the child individual are determined.Figure3 describes the crossover function step by step. It should be noted that by transmitting each community to the child individual, its modularity value also gets transmitted unless the community is fragmented. Thus, we will not need to recompute the fitness value for all communities. Instead, once the child individual is formed, we compute modularity only for the fragmented communities by using formula (4) and add the values of the rest of the communities.Figure 3
The crossover procedure to create a new individual. (a) The graph, individual, and community vector of the first parent, (b) the graph, individual, and community vector of the second parent, and (c) new individual, to create the new individual first, we sort the communities of both parents in descending order of their modularities; then, we select the communities from best to worst, respectively. TheC2,5, C2,1, and C1,3 communities get added first. Then, C1,4 gets selected, but because #10, #11, and #12 nodes are already assigned to other communities, and a new singleton community gets formed for node #6.
(a)(b)(c)


## 4.5. Mutation

A mutation function is used in GAs to add to the diversity of population space. Using this function, one or more genes of each individual gets modified. Here, we describe three different mutation functions, two constant, and one new adaptive function.


### 4.5.1. Uniform-Based

One of the famous mutation functions is the uniform mutation function. This function assigns an equal chance for each gene to get elected for mutation. This probability would be equal to1/n−1 for the MST-based representation. To select the gene, we create a random number between 1 and n−1 (with a uniform probability). As we have mentioned previously, one of the advantages of binary representations is the reduction of the value domain for each gene. While choosing the value of the mutated gene requires a random or educated selection in the locus-based and solution-vector-based methods (selecting another neighbor in locus-based or selecting another community identifier in the solution-vector-based method), it is enough to perform a negation in a binary representation.


### 4.5.2. Weight-Based

Also, we examined a nonuniform mutation function in our experiments. As its name suggests, a nonuniform function does not assign equal probabilities to each gene. We form this distribution based on the weights of the corresponding edges of the network’s MST. To generate the probabilities, we divide the weight of each edge into the sum of the weights of all edges of the MST. Again, we negate the value of the genes which were selected during the mutation procedure.


### 4.5.3. Sine-Based

Yet, we also introduce a new adaptive mutation function based on the depths of the corresponding edges of each gene. As discussed in 4.1, each gene in theMST-based representation refers to an edge in the graph’s MST. In some cases, it might be meaningful to keep internal edges untouched while directing the mutations to border edges or vice versa. Our aim in this function is to examine the effectiveness of this theory. In this method, we assign the probability of each gene concerning its corresponding distance from the broken edges of its community. Figure 4 can help us describe our function. For example, Figure 4(a) shows a distribution that puts more weight on the border edges (intercommunity edges on MST) of the communities. In this figure, points with peak values indicate the border edges, and as we move to the depth of each community, the value decreases, and then it starts to rise as we move closer to the next border edge. Using a distribution similar to Figure 4(a) causes a reduction in the chance of a mutation on internal edges. The reverse situation occurs when a distribution similar to Figure 4(c) is used. Figure 4(b) displays a situation where each gene has the same chance of mutation. To form such a distribution, first, we create a vector such as w⟶ with the length of n−1 and assign the value of 1 for the corresponding elements of broken edges. Then, for each broken edge, we start to navigate the edges connecting to its end nodes in a BFS order until we reach another broken edge. For each navigated edge, we change its corresponding w⟶ value as follows:(7)w⟶i=w⟶i+α⋅2−1/d+1−α⋅1−2−1/d,where the index of the gene is denoted with i, d indicates its distance from the border edge, and α is a control parameter. Assigning 1 to α will produce a distribution such as the one shown in Figure 4(c) while α=0 will result in a distribution such as the one shown in Figure 4(a). Assigning 0.5 to the α will result in a uniform distribution. In our method, α is a self-adaptive parameter. It oscillates between 0 and 1 based on the change in the modularity of the best individual of each generation. If the fitness value of the best individual improves in the last generation, α remains unchanged while it changes as follows in the opposite condition:(8)αq=αq−1,if.fitnessimproves,sinzq,Else.zq=π6+q⋅δ⋅π,where δ is a user-defined constant to determine the length of each step and q is the index of the generation. After performing the described process using all of the broken edges of the individuals, we transform the values of the w⟶ vector between 0 and 1 and use it as the probability distribution function of the mutation function. We hypothesize that this adaptive method can result in mutations that can separate or merge the communities in a better way by adjusting the slope of the mutation probability function based on the improvement of the quality of the best individual in the pool. Figure 5 describes the effect of δ on determining α.Figure 4
The effect ofα on the shape of the probability distribution. (a) α parameter has been set equal to 0, and mutation probability is directed toward border edges, (b) setting α=0.5 results in a uniform probability distribution, and (c) shows the probability distribution of the edges when α=1. The mutation probability of inner edges is increased.
(a)(b)(c)Figure 5
Function ofαq=sinzq oscillates between 0 and 1, causing the mutation probability distribution to change. δ defines the length of each step δ=0.1.


## 4.5.1. Uniform-Based

One of the famous mutation functions is the uniform mutation function. This function assigns an equal chance for each gene to get elected for mutation. This probability would be equal to1/n−1 for the MST-based representation. To select the gene, we create a random number between 1 and n−1 (with a uniform probability). As we have mentioned previously, one of the advantages of binary representations is the reduction of the value domain for each gene. While choosing the value of the mutated gene requires a random or educated selection in the locus-based and solution-vector-based methods (selecting another neighbor in locus-based or selecting another community identifier in the solution-vector-based method), it is enough to perform a negation in a binary representation.


## 4.5.2. Weight-Based

Also, we examined a nonuniform mutation function in our experiments. As its name suggests, a nonuniform function does not assign equal probabilities to each gene. We form this distribution based on the weights of the corresponding edges of the network’s MST. To generate the probabilities, we divide the weight of each edge into the sum of the weights of all edges of the MST. Again, we negate the value of the genes which were selected during the mutation procedure.


## 4.5.3. Sine-Based

Yet, we also introduce a new adaptive mutation function based on the depths of the corresponding edges of each gene. As discussed in 4.1, each gene in theMST-based representation refers to an edge in the graph’s MST. In some cases, it might be meaningful to keep internal edges untouched while directing the mutations to border edges or vice versa. Our aim in this function is to examine the effectiveness of this theory. In this method, we assign the probability of each gene concerning its corresponding distance from the broken edges of its community. Figure 4 can help us describe our function. For example, Figure 4(a) shows a distribution that puts more weight on the border edges (intercommunity edges on MST) of the communities. In this figure, points with peak values indicate the border edges, and as we move to the depth of each community, the value decreases, and then it starts to rise as we move closer to the next border edge. Using a distribution similar to Figure 4(a) causes a reduction in the chance of a mutation on internal edges. The reverse situation occurs when a distribution similar to Figure 4(c) is used. Figure 4(b) displays a situation where each gene has the same chance of mutation. To form such a distribution, first, we create a vector such as w⟶ with the length of n−1 and assign the value of 1 for the corresponding elements of broken edges. Then, for each broken edge, we start to navigate the edges connecting to its end nodes in a BFS order until we reach another broken edge. For each navigated edge, we change its corresponding w⟶ value as follows:(7)w⟶i=w⟶i+α⋅2−1/d+1−α⋅1−2−1/d,where the index of the gene is denoted with i, d indicates its distance from the border edge, and α is a control parameter. Assigning 1 to α will produce a distribution such as the one shown in Figure 4(c) while α=0 will result in a distribution such as the one shown in Figure 4(a). Assigning 0.5 to the α will result in a uniform distribution. In our method, α is a self-adaptive parameter. It oscillates between 0 and 1 based on the change in the modularity of the best individual of each generation. If the fitness value of the best individual improves in the last generation, α remains unchanged while it changes as follows in the opposite condition:(8)αq=αq−1,if.fitnessimproves,sinzq,Else.zq=π6+q⋅δ⋅π,where δ is a user-defined constant to determine the length of each step and q is the index of the generation. After performing the described process using all of the broken edges of the individuals, we transform the values of the w⟶ vector between 0 and 1 and use it as the probability distribution function of the mutation function. We hypothesize that this adaptive method can result in mutations that can separate or merge the communities in a better way by adjusting the slope of the mutation probability function based on the improvement of the quality of the best individual in the pool. Figure 5 describes the effect of δ on determining α.Figure 4
The effect ofα on the shape of the probability distribution. (a) α parameter has been set equal to 0, and mutation probability is directed toward border edges, (b) setting α=0.5 results in a uniform probability distribution, and (c) shows the probability distribution of the edges when α=1. The mutation probability of inner edges is increased.
(a)(b)(c)Figure 5
Function ofαq=sinzq oscillates between 0 and 1, causing the mutation probability distribution to change. δ defines the length of each step δ=0.1.


## 5. Results and Discussion

In this section, we present the results of the proposed method on standard datasets and measure the outcomes with NMI and modularity; then, we compare the results with those of other state-of-the-art algorithms and discuss the advantages of the proposed method. Both of these measures are widely used in community detection literature. We use both real-world and synthetic networks to compare the performance of the proposed method.


### 5.1. Measures

NMI and modularity are commonly used measures to qualify the results of community detection algorithms. These measures are defined as follows:


#### 5.1.1. Normalized Mutual Information (NMI)

For the datasets that have ground-truth information, it is expected that a community detection algorithm will produce similar outputs as the real-world observations. NMI measures how close the ground truth and the results are. TakingC^=C^1,C^2,…,C^k as the ground-truth data, and C=C1,C2,…,Cq as the detected communities, NMI is calculated as follows:(9)NMIC,C^=2IC,C^HC+HC^,where IC,C^ and HC are the mutual information of C and C^ and the entropy of C, respectively, and it could be calculated as follows:(10)IC,C^=HC+HC^−HC,C^,HC=−∑i=1qCinlogCin,HC,C^=−∑i=1q∑j=1kCi∩Cj^nlogCi∩Cj^n,where n represents the number of nodes in the graph.


#### 5.1.2. Modularity

This measure was proposed by Newman and Girvan in [4] and is one of the most popular quality functions applied to measure the quality of a partition. It is defined as follows:(11)Q=12m∑i∑jAi,j−Pi,jδCi,Cj,where A is the adjacency matrix, m is the number of the edges of the graph, P is a null model matrix and its elements are computed as Pi,j=Γi×Γj/2m; ei,j∈E, and δCi,Cj is a function that returns 1 whenever Ci and Cj are the same and 0 otherwise.


### 5.2. Datasets

Nine real-world and seven synthetic datasets are used to evaluate the performance of the proposed algorithm. Table2 summarizes the characteristics of the real-world datasets, and Table 3 provides the parameters used to generate the synthetic networks. The details of these datasets are described in the following.Table 2
The summarized information of the real-world datasets which we use to compare the performance of the proposed method;n indicates the number of nodes of the graph, m denotes the number of edges of the network, and μd is the average degree of each node.
NetworknmμdGround truthKarate34784.59YDolphins623185.13YPolbooks1058828.40YFootball115123210.71YJazz198548427.70NPolblogs149095456.40YPower4941131882.67NCA-HepTh9877259985.74NPGP10680243164.55NTable 3
Parameters for generating benchmark LFR networks;n indicates the number of nodes in the network, μd is the average node degree, the maximum node degree is represented by dmax, μ shows the value of the mixing parameter, γ denotes the exponent of the power law distribution for degree distribution, and β represents the exponent of the power law distribution for community sizes, the minimum community size and the maximum community size are denoted by Cmin and Cmax, respectively. LFR-μ is used for the purpose of showing the effect of changing the mixing parameter μ.
NetworknμddmaxμγβCminCmaxLFR-150350.1212525LFR-2100015200.120500500LFR-3100020300.121100500LFR-425001002000.1225001000LFR-550002004000.12210002000LFR-6100001005000.12210005000LFR-μ50020350−0.72250100


#### 5.2.1. Zachary Karate Club

This dataset models the interactions between karate club members in an American university. Each node in this network denotes one club member, and each edge represents the existence of a relationship between two members outside of the club. This network involves 34 nodes and 78 edges. The club members get divided after a discrepancy between the club manager and coach [57].


#### 5.2.2. Dolphins Interaction Network

Bottlenose dolphins were studied in Doubtful Sounds of New Zealand for several years by Lusseau [58]. 62 nodes of this network represent the dolphins, and an edge between them indicates that they were seen together for more than the expected amount of time.


#### 5.2.3. American College Football Network

Mostly known as afootball network, this dataset is the result of modeling the matches that took place among the teams of 12 different conferences in a season of American college football games. On an average, each team is more likely to have a match with the teams from its conference (7 intraconference and 4 interconference matches). The ground-truth state of this dataset divides the 115 nodes of the network into 12 communities in which each community represents a conference [59].


#### 5.2.4. Political Books

Amazon.com recommends similar products to its customers. This dataset represents the recommendation network of political books on this website. Books are categorized into three groups based on their content, namely, liberal, neutral, and conservative [60].


#### 5.2.5. Political Blogs

Adamic and Glance conducted a study on the Internet blogs a few months preceding the 2004 presidential elections of the United States of America and created this dataset. In this graph, each node represents a blog, and an edge takes place between two nodes if they have a hyperlink to each other. Here, the aim is to divide the 1490 nodes into two communities denoting the political inclination of each blog [61].


#### 5.2.6. Power Network

This network shows the power network of the western states of the United States of America. In this graph, each node represents a generator, a transformer, or a substation, and each edge represents a power supply line between two points. This dataset does not have ground-truth data [62].


#### 5.2.7. Jazz Musicians Network

This dataset represents jazz musicians based on their collaboration. Each of the 2742 edges of this graph represents the collaboration of jazz musicians in the same band or having a common musician in the band [63].


#### 5.2.8. Pretty-Good Privacy (PGP)

This dataset is the network of the users of the Pretty-Good Privacy program, a program that is used for transmitting encrypted e-mails and files. Each of the 10,680 nodes depicts a user, and these nodes are connected by 24,316 edges, each representing a bidirectional signature between two users [64].


#### 5.2.9. Collaboration Network of Arxiv High Energy Physics Theory (Ca-HepTh)

The dataset models the scientific collaboration among scientists. It covers the articles submitted to the High Energy Physics-Theory category. Each node depicts a scientist, and each edge represents the existence of a coauthored article. This dataset consists of 9,877 nodes connected by 51,971 edges [65].


#### 5.2.10. Synthetic LFR Networks

Lancichinetti, Fortunato, and Radicchi proposed a method to generate synthetic networks for evaluating community detection algorithms’ performance [66]. Their method is abbreviated as LFR. In their proposed method, node degree and community size distribution follow a power law distribution and create networks with similar characteristics to the real networks. Degree and community size exponents are depicted by γ and β, respectively. Also, they defined a mixing parameter μ that controls the ratio of the edges between communities. We have generated 7 synthetic LFR networks of different sizes for our experiments (we use LFR-μ to show the effect of changing the mixing parameter on the performance of the algorithms). The details of the generated networks are given in Table 3, and Figure 6 shows the way the algorithms react to different μ values.Figure 6
Comparison of the results of the proposed method with some of the recent community detection algorithms based on their response to differentμ values of LFR networks. (a) Comparison of modularity value for LFR-μ dataset, (b) Comparison of NMI value for LFR-μ dataset.
(a)(b)


### 5.3. Experiments and Comparisons

In this section, we evaluate the effect of each of the parameters on the performance of different phases of the proposed algorithm and discuss the advantages and disadvantages of the proposed method compared with other methods. We have conducted extensive performance evaluation experiments and compared the results of the proposed method with some of the recent and classic community detection algorithms. Also, we picked the algorithms from different categories, includingmodularity-optimization-based, similarity-optimization-based, and GA-based methods, to give a broad picture of the performances of different algorithms. The methods which we use for the purpose of comparison are Louvain [29], Leiden [30], fast greedy [28], Infomap [17], LP [11], LocalGame [9], CCGA [34], CACD [22], GA-net [25], FluidCom [67], EdMot [31], WMW [14], WATSET [32], and CoreExpansion [68]. We use NMI and modularity measures in our comparisons and conduct experiments on nine real-world and seven synthetic networks. First, we explain the effects of different internal approaches and parameters. Then, we direct the discussion toward the advantages and disadvantages of our method compared to the other algorithms.


#### 5.3.1. Representation

As we described in Section4.1, to construct the MST trees for the MST-based representations, we use node similarity measures to assign weights on the edges of graphs. Naturally, the MSTs will be different based on the applied similarity index because each measure highlights certain characteristics. To determine the best similarity index, we applied the indexes presented in Table 1 to the karate dataset. We used different similarity indexes from recent and classic literature and various categories. The resultant MST trees, and the final partitions, are shown in Figure 7. The bolded edges in this figure represent the MST edges. Figure 8 compares the results based on NMI and modularity. As it can be seen from Figure 7, the cosine and Jaccard similarity indexes perform similarly to each other, and their results have a better balance in terms of NMI and Q. It can be noticed from Figure 7 that the generated results are directly related to the corresponding MST trees. Specifically, by looking at the edges of node #5 and comparing them with the edges of the same node in different trees, one can understand the impact of each similarity measure. In all of the proceeding experiments, we use the Jaccard similarity to generate MST trees both because of its simplicity and its higher accuracy.Figure 7
This figure illustrates the impact of different similarity measures on the resultant MST tree and the final partition of the algorithm over the Zachary karate club dataset. (a) Common neighbors, (b) Jaccard, (c) Cosine, (d) HPI, (e) Adamic/Adar, (f) RA, (g) CNDP, (h) SRW, and (i) HIN.
(a)(b)(c)(d)(e)(f)(g)(h)(i)Figure 8
Comparison of the results of the proposed method for different similarity measures in the karate network.


#### 5.3.2. Initial Population Generation

As we explained in Section4.2, we create the initial populations by splitting the MST tree into communities of n nodes. This method can result in very effective initial populations which involve near-optimum individuals. To evaluate the effectiveness of the initial population generation function, we compare the qualities of the initial populations generated by the proposed method with a random initial population generation method. Figure 9 compares the modularities of the best individuals and the average modularities of the initial populations for each approach. It can be seen that the proposed method performs considerably better than the random method. On the other hand, in Figure 10, generation 0 depicts the quality of the best individuals for four different algorithms; 1) the proposed algorithm, 2) CCGA, 3) CACD, and 4) GA-Net. While GA-net’s initial population is generated using a random function, CACD and CCGA use their initial population generation functions. As illustrated in Figure 10, our initial population generation function produces near-optimal individuals. The method of splitting the graph or data into clusters of n nodes/points has been already implemented in various clustering/community detection algorithms, but no other community detection method has implemented this method to generate initial populations for GAs.Figure 9
Comparison of the performance of the proposed initial population generation function (P) with random initial population generation function (Rand).Figure 10
Comparison of the results of the proposed method with other GAs on the Polbooks dataset. We ran all of the methods by a population size of 100 for 300 generations.


#### 5.3.3. Mutation Function

The next influencing factor is the mutation function. To examine the effectiveness of the proposed mutation function, we conducted several experiments on the jazz dataset and compared the results based on the convergence time and the modularity score. The obtained results are shown in Figure11(a). To generate the outcomes, we ran 100 experiments while setting the stop criteria to exceed the modularity of 0.435 or observing no improvement in the modularity of the best individual for 50 consecutive generations. At first glance, we can see that the uncertainty of the number of generations to reach a solution is the highest at the weight-based mutation function. This function has a higher mean value and longer whiskers than the other functions. Also, this method has more upper outliers. Hence, we can conclude that this method performs weaker than the others. Considering its higher mean value, the main reason for its poor performance is its nonuniform probability distribution; thus, it has a higher tendency to get stuck in local optima, which might result in higher convergence time. On the other hand, the mean values (110.5 and 111) and the upper outliers of both sine-based and uniform-based functions are similar. But, the uniform-based function’s box is more compact than the sine-based function’s. Therefore, we can say that the deviations in the uniform function are less than those of the sine-based function, and its results are closer to the mean. Yet, it is apparent that the box of the sine-based method stands lower than that of the uniform-based method, and its lower whisker is longer than the whisker of the uniform-based method which means that the sine-based function can converge faster than the uniform-based method. Therefore, from Figure 11, we can conclude that the sine-based method performs almost 25% faster than the uniform-based method.Figure 11
Comparison of variations of the generation count and modularity for 3 different mutation functions. 100 experiments were performed over the Jazz dataset for each function, while the stopping criteria was, exceeding the modularity of 0.435, or seeing no improvement on the maximum modularity of each generation on 50 respective generations. (a) Box plots of the number of generations and (b) box plots of the maximum modularity of each experiment.
(a)(b)When comparing the variations of the modularity scores of the mutation functions, we observe that all of them have similar mean values, but theweight-based method has higher variations compared to the others. Again, this might have resulted from the nonuniform probability distribution, which results in getting stuck in local optima. Therefore, this method performs poorly both in terms of convergence time and the modularity score. Yet, comparing the sine-based and uniform-based functions shows that both of the boxes have similar upper sides, whereas the lower whisker of the sine-based distribution is considerably shorter than that of the uniform-based distribution, and it almost stands at the same value than where the lower side of the uniform-based method stands. This means that the likelihood of observing lower modularity is almost 25% lower when we use the sine-based method instead of the uniform-based one. This shows that our hypothesis in Section 4.5 was correct, and the sine-based mutation function can reduce the convergence time by changing the mutation probability distribution of the genes with a smoothly changing adaptive function and directing mutation probabilities to the border and central edges of each community. The box plots of the modularity variations are shown in Figure 11(b).Consequently, we can conclude that thesine-based method can produce better and faster outcomes. It should be considered that this advantage does not come without a cost. For the sine-based method, we have to perform a set of calculations, such as assigning a depth value for each edge. Therefore, using the sine-based function can be a cost-effective choice for small datasets.


#### 5.3.4. Comparisons

Tables4 and 5 provide the results of the comparisons of the proposed method with the other methods based on NMI and modularity measures. We used the Jaccard similarity to assign weights to edges and the sine-based mutation function to perform mutations in our experiments. To run all of the GA-based methods, we set the population size to 100 for small networks and 300 for large ones. We ran all of the GA-based algorithms for 300 generations several times and recorded the best outcome. In our method, we set δ=0.1 in our experiments.Table 4
Comparison of the results of real-world datasets of the proposed method with other methods based on NMI and modularity (Q) measures.
NetworkKaratePolbooksPolblogsFootballDolphinsPowerJazzPGPCa-HepAverageQNMIQNMIQNMIQNMIQNMIQQQQQ¯NMI¯Proposed method0.420.600.520.570.430.450.600.820.520.730.930.440.860.750.6070.634CACD0.420.940.530.760.340.640.580.890.520.900.770.430.790.660.560.826CCGA0.420.690.520.530.370.330.550.700.520.730.900.420.840.530.5630.596GA-net0.400.630.430.400.350.300.600.910.420.580.640.370.600.530.480.56WATSET0.371.00.490.560.430.480.580.890.480.730.790.280.800.690.5450.73FluidCom0.350.580.440.480.430.450.580.890.380.460.890.420.820.680.5540.572EdMot0.420.600.530.530.290.360.600.880.520.780.940.440.870.770.5980.63WMW0.400.540.470.430.400.280.390.690.490.690.610.320.670.570.480.526LocalGame0.371.00.510.550.400.680.580.890.510.730.900.280.790.630.550.77Leiden0.420.690.520.520.430.630.600.870.530.770.940.440.880.770.6140.696CoreExpansion0.370.840.440.630.340.640.560.730.510.530.850.280.810.670.540.67Louvain0.420.590.520.510.430.630.600.880.520.480.930.440.880.820.6170.618Fast greedy0.380.690.500.530.430.650.550.700.500.610.930.440.850.780.5950.636Infomap0.400.700.520.490.420.480.600.920.520.500.820.280.800.730.5650.618LP0.400.700.500.570.430.690.600.920.500.690.810.280.810.740.5630.714In each column, the highest value is in bold.Table 5
Comparison of the results of synthetic networks of the proposed method with other methods based on NMI and modularity (Q) measures.
NetworkLFR-1LFR-2LFR-3LFR-4LFR-5LFR-6AverageQNMIQNMIQNMIQNMIQNMIQNMIQ¯NMI¯Proposed method0.610.540.431.00.821.00.701.00.531.00.661.00.620.92CACD0.540.800.431.00.821.00.580.870.110.570.110.480.430.79CCGA0.590.560.240.330.640.750.10.370.10.20.10.10.300.39GA-net0.520.430.240.420.610.850.200.300.10.10.10.10.300.37WATSET0.590.650.431.00.821.00.701.00.531.00.661.00.620.94FluidCom0.540.800.431.00.740.820.580.860.10.440.180.590.420.75EdMot0.620.610.431.00.821.00.701.00.531.00.661.00.660.93WMW0.520.430.240.420.740.960.701.00.531.00.661.00.570.80LocalGame0.491.00.431.00.821.00.701.00.531.00.661.00.601.0Leiden0.500.610.431.00.821.00.701.00.531.00.661.00.610.93CoreExpansion0.560.610.200.340.700.940.540.850.150.300.240.330.400.56Louvain0.470.390.431.00.821.00.701.00.531.00.661.00.600.90Fast greedy0.620.660.431.00.810.990.690.990.531.00.661.00.620.94Infomap0.600.540.431.00.821.00.701.00.531.00.661.00.620.92LP0.560.800.431.00.821.00.701.00.531.00.661.00.620.97In each column, the highest value is in bold.In real-world datasets, the comparisons show that the proposed method can produce competitive results on both NMI and modularity measures. It can be seen that the proposed method outperforms the other GA-based methods in almost all of the experiments in terms of the modularity scores. Our method results in an average of 0.607, while the best modularity is achieved by the Louvain algorithm at 0.617. On the other hand, while our method’s average NMI value is 0.634 and for Louvain it is 0.618. The best NMI value belongs to the CACD, with an NMI of 0.826 and a modularity of 0.56. In general, there is only one method (Leiden) that simultaneously performs better than our method in both modularity and NMI. The proposed method performs better in either one or both of the measures when it is compared with the average values of the other methods.Looking at the synthetic datasets, our method can reach the highest modularity and NMI values among the GAs with a modularity of 0.62 and an NMI of 0.92. The proposed method’s advantages become obvious as the network size increases. This is especially noticeable in the LFR5 and LFR6 datasets, which have a very high number of intercommunity edges. The reason for the other GA-based methods’ poor performance in these datasets is that they uselocus-based representation and keep testing different neighbors; therefore, they need both larger populations and more generations to reach better results. The proposed method lags behind EdMot in average modularity and LocalGame in average NMI values.Figure10 shows another significant analysis of the different GA-based community detection algorithms. This figure shows the modularity of the best individuals of each GA-based method on the Polbooks dataset over several generations. For this dataset, we set the generation size to 100 and let the methods run for 300 generations. Generation number 0 depicts the performance of initial population generation functions. While the best individual of our initial population has a modularity of 0.5 (almost equal to the final modularity), the closest method (CCAD) can produce individuals with maximum modularity of 0.43. Furthermore, while our method converges at the 20th generation at 0.5234, CCAD can only beat our method in the 148th generation, reaching convergence at the 189th generation at a modularity of 0.5266. The next two algorithms can never find better partitions, even on the 300th generation. Therefore, comparisons prove that the proposed algorithm can produce better results in a shorter period of time in comparison with other GAs. It is worth mentioning that the GA-net’s high fluctuations are the result of its fitness function. As explained in Section 2, this method does not use modularity as its fitness function (CACD and CCGA are both modularity-optimization-based methods).In LFR networks,μ defines the ratio of the intercommunity edges. A higher value of μ means that there are more edges between the nodes that belong to different communities instead of the nodes within the same community. In Figure 6, we compare the effect of the μ parameter on the outcomes of different methods. It is apparent from the figure that an increase in μ decreases modularity on almost all of the algorithms. This is because having more intercommunity edges is exactly the opposite of the way that modularity defines a community. LocalGame, a similarity-based method, because of its dependency on the distance between communities, falls immediately to 0 in both measures as soon as μ exceeds 0.5. CCGA and CACD’s modularity values behave almost identically to the changes in the μ parameter, but CACD results in higher NMI values. Yet, even though CACD’s NMI value stays the highest at μ=0.7, its NMI and modularity values start to decrease very quickly at μ=0.1. The proposed method’s NMI and modularity remain the highest as long as μ is below 0.4 and starts to decline after exceeding 0.5 though it remains the second-best method for almost all other μ values, and its NMI stays higher than EdMot’s at μ=0.7. Comparing the results shows that the proposed algorithm can produce acceptable outcomes when the mixing parameter changes.Extensive comparisons of different methods on both real-world and synthetic datasets show that the proposed method can produce competitive results with state-of-the-art algorithms.


## 5.1. Measures

NMI and modularity are commonly used measures to qualify the results of community detection algorithms. These measures are defined as follows:


### 5.1.1. Normalized Mutual Information (NMI)

For the datasets that have ground-truth information, it is expected that a community detection algorithm will produce similar outputs as the real-world observations. NMI measures how close the ground truth and the results are. TakingC^=C^1,C^2,…,C^k as the ground-truth data, and C=C1,C2,…,Cq as the detected communities, NMI is calculated as follows:(9)NMIC,C^=2IC,C^HC+HC^,where IC,C^ and HC are the mutual information of C and C^ and the entropy of C, respectively, and it could be calculated as follows:(10)IC,C^=HC+HC^−HC,C^,HC=−∑i=1qCinlogCin,HC,C^=−∑i=1q∑j=1kCi∩Cj^nlogCi∩Cj^n,where n represents the number of nodes in the graph.


### 5.1.2. Modularity

This measure was proposed by Newman and Girvan in [4] and is one of the most popular quality functions applied to measure the quality of a partition. It is defined as follows:(11)Q=12m∑i∑jAi,j−Pi,jδCi,Cj,where A is the adjacency matrix, m is the number of the edges of the graph, P is a null model matrix and its elements are computed as Pi,j=Γi×Γj/2m; ei,j∈E, and δCi,Cj is a function that returns 1 whenever Ci and Cj are the same and 0 otherwise.


## 5.1.1. Normalized Mutual Information (NMI)

For the datasets that have ground-truth information, it is expected that a community detection algorithm will produce similar outputs as the real-world observations. NMI measures how close the ground truth and the results are. TakingC^=C^1,C^2,…,C^k as the ground-truth data, and C=C1,C2,…,Cq as the detected communities, NMI is calculated as follows:(9)NMIC,C^=2IC,C^HC+HC^,where IC,C^ and HC are the mutual information of C and C^ and the entropy of C, respectively, and it could be calculated as follows:(10)IC,C^=HC+HC^−HC,C^,HC=−∑i=1qCinlogCin,HC,C^=−∑i=1q∑j=1kCi∩Cj^nlogCi∩Cj^n,where n represents the number of nodes in the graph.


## 5.1.2. Modularity

This measure was proposed by Newman and Girvan in [4] and is one of the most popular quality functions applied to measure the quality of a partition. It is defined as follows:(11)Q=12m∑i∑jAi,j−Pi,jδCi,Cj,where A is the adjacency matrix, m is the number of the edges of the graph, P is a null model matrix and its elements are computed as Pi,j=Γi×Γj/2m; ei,j∈E, and δCi,Cj is a function that returns 1 whenever Ci and Cj are the same and 0 otherwise.


## 5.2. Datasets

Nine real-world and seven synthetic datasets are used to evaluate the performance of the proposed algorithm. Table2 summarizes the characteristics of the real-world datasets, and Table 3 provides the parameters used to generate the synthetic networks. The details of these datasets are described in the following.Table 2
The summarized information of the real-world datasets which we use to compare the performance of the proposed method;n indicates the number of nodes of the graph, m denotes the number of edges of the network, and μd is the average degree of each node.
NetworknmμdGround truthKarate34784.59YDolphins623185.13YPolbooks1058828.40YFootball115123210.71YJazz198548427.70NPolblogs149095456.40YPower4941131882.67NCA-HepTh9877259985.74NPGP10680243164.55NTable 3
Parameters for generating benchmark LFR networks;n indicates the number of nodes in the network, μd is the average node degree, the maximum node degree is represented by dmax, μ shows the value of the mixing parameter, γ denotes the exponent of the power law distribution for degree distribution, and β represents the exponent of the power law distribution for community sizes, the minimum community size and the maximum community size are denoted by Cmin and Cmax, respectively. LFR-μ is used for the purpose of showing the effect of changing the mixing parameter μ.
NetworknμddmaxμγβCminCmaxLFR-150350.1212525LFR-2100015200.120500500LFR-3100020300.121100500LFR-425001002000.1225001000LFR-550002004000.12210002000LFR-6100001005000.12210005000LFR-μ50020350−0.72250100


### 5.2.1. Zachary Karate Club

This dataset models the interactions between karate club members in an American university. Each node in this network denotes one club member, and each edge represents the existence of a relationship between two members outside of the club. This network involves 34 nodes and 78 edges. The club members get divided after a discrepancy between the club manager and coach [57].


### 5.2.2. Dolphins Interaction Network

Bottlenose dolphins were studied in Doubtful Sounds of New Zealand for several years by Lusseau [58]. 62 nodes of this network represent the dolphins, and an edge between them indicates that they were seen together for more than the expected amount of time.


### 5.2.3. American College Football Network

Mostly known as afootball network, this dataset is the result of modeling the matches that took place among the teams of 12 different conferences in a season of American college football games. On an average, each team is more likely to have a match with the teams from its conference (7 intraconference and 4 interconference matches). The ground-truth state of this dataset divides the 115 nodes of the network into 12 communities in which each community represents a conference [59].


### 5.2.4. Political Books

Amazon.com recommends similar products to its customers. This dataset represents the recommendation network of political books on this website. Books are categorized into three groups based on their content, namely, liberal, neutral, and conservative [60].


### 5.2.5. Political Blogs

Adamic and Glance conducted a study on the Internet blogs a few months preceding the 2004 presidential elections of the United States of America and created this dataset. In this graph, each node represents a blog, and an edge takes place between two nodes if they have a hyperlink to each other. Here, the aim is to divide the 1490 nodes into two communities denoting the political inclination of each blog [61].


### 5.2.6. Power Network

This network shows the power network of the western states of the United States of America. In this graph, each node represents a generator, a transformer, or a substation, and each edge represents a power supply line between two points. This dataset does not have ground-truth data [62].


### 5.2.7. Jazz Musicians Network

This dataset represents jazz musicians based on their collaboration. Each of the 2742 edges of this graph represents the collaboration of jazz musicians in the same band or having a common musician in the band [63].


### 5.2.8. Pretty-Good Privacy (PGP)

This dataset is the network of the users of the Pretty-Good Privacy program, a program that is used for transmitting encrypted e-mails and files. Each of the 10,680 nodes depicts a user, and these nodes are connected by 24,316 edges, each representing a bidirectional signature between two users [64].


### 5.2.9. Collaboration Network of Arxiv High Energy Physics Theory (Ca-HepTh)

The dataset models the scientific collaboration among scientists. It covers the articles submitted to the High Energy Physics-Theory category. Each node depicts a scientist, and each edge represents the existence of a coauthored article. This dataset consists of 9,877 nodes connected by 51,971 edges [65].


### 5.2.10. Synthetic LFR Networks

Lancichinetti, Fortunato, and Radicchi proposed a method to generate synthetic networks for evaluating community detection algorithms’ performance [66]. Their method is abbreviated as LFR. In their proposed method, node degree and community size distribution follow a power law distribution and create networks with similar characteristics to the real networks. Degree and community size exponents are depicted by γ and β, respectively. Also, they defined a mixing parameter μ that controls the ratio of the edges between communities. We have generated 7 synthetic LFR networks of different sizes for our experiments (we use LFR-μ to show the effect of changing the mixing parameter on the performance of the algorithms). The details of the generated networks are given in Table 3, and Figure 6 shows the way the algorithms react to different μ values.Figure 6
Comparison of the results of the proposed method with some of the recent community detection algorithms based on their response to differentμ values of LFR networks. (a) Comparison of modularity value for LFR-μ dataset, (b) Comparison of NMI value for LFR-μ dataset.
(a)(b)


## 5.2.1. Zachary Karate Club

This dataset models the interactions between karate club members in an American university. Each node in this network denotes one club member, and each edge represents the existence of a relationship between two members outside of the club. This network involves 34 nodes and 78 edges. The club members get divided after a discrepancy between the club manager and coach [57].


## 5.2.2. Dolphins Interaction Network

Bottlenose dolphins were studied in Doubtful Sounds of New Zealand for several years by Lusseau [58]. 62 nodes of this network represent the dolphins, and an edge between them indicates that they were seen together for more than the expected amount of time.


## 5.2.3. American College Football Network

Mostly known as afootball network, this dataset is the result of modeling the matches that took place among the teams of 12 different conferences in a season of American college football games. On an average, each team is more likely to have a match with the teams from its conference (7 intraconference and 4 interconference matches). The ground-truth state of this dataset divides the 115 nodes of the network into 12 communities in which each community represents a conference [59].


## 5.2.4. Political Books

Amazon.com recommends similar products to its customers. This dataset represents the recommendation network of political books on this website. Books are categorized into three groups based on their content, namely, liberal, neutral, and conservative [60].


## 5.2.5. Political Blogs

Adamic and Glance conducted a study on the Internet blogs a few months preceding the 2004 presidential elections of the United States of America and created this dataset. In this graph, each node represents a blog, and an edge takes place between two nodes if they have a hyperlink to each other. Here, the aim is to divide the 1490 nodes into two communities denoting the political inclination of each blog [61].


## 5.2.6. Power Network

This network shows the power network of the western states of the United States of America. In this graph, each node represents a generator, a transformer, or a substation, and each edge represents a power supply line between two points. This dataset does not have ground-truth data [62].


## 5.2.7. Jazz Musicians Network

This dataset represents jazz musicians based on their collaboration. Each of the 2742 edges of this graph represents the collaboration of jazz musicians in the same band or having a common musician in the band [63].


## 5.2.8. Pretty-Good Privacy (PGP)

This dataset is the network of the users of the Pretty-Good Privacy program, a program that is used for transmitting encrypted e-mails and files. Each of the 10,680 nodes depicts a user, and these nodes are connected by 24,316 edges, each representing a bidirectional signature between two users [64].


## 5.2.9. Collaboration Network of Arxiv High Energy Physics Theory (Ca-HepTh)

The dataset models the scientific collaboration among scientists. It covers the articles submitted to the High Energy Physics-Theory category. Each node depicts a scientist, and each edge represents the existence of a coauthored article. This dataset consists of 9,877 nodes connected by 51,971 edges [65].


## 5.2.10. Synthetic LFR Networks

Lancichinetti, Fortunato, and Radicchi proposed a method to generate synthetic networks for evaluating community detection algorithms’ performance [66]. Their method is abbreviated as LFR. In their proposed method, node degree and community size distribution follow a power law distribution and create networks with similar characteristics to the real networks. Degree and community size exponents are depicted by γ and β, respectively. Also, they defined a mixing parameter μ that controls the ratio of the edges between communities. We have generated 7 synthetic LFR networks of different sizes for our experiments (we use LFR-μ to show the effect of changing the mixing parameter on the performance of the algorithms). The details of the generated networks are given in Table 3, and Figure 6 shows the way the algorithms react to different μ values.Figure 6
Comparison of the results of the proposed method with some of the recent community detection algorithms based on their response to differentμ values of LFR networks. (a) Comparison of modularity value for LFR-μ dataset, (b) Comparison of NMI value for LFR-μ dataset.
(a)(b)


## 5.3. Experiments and Comparisons

In this section, we evaluate the effect of each of the parameters on the performance of different phases of the proposed algorithm and discuss the advantages and disadvantages of the proposed method compared with other methods. We have conducted extensive performance evaluation experiments and compared the results of the proposed method with some of the recent and classic community detection algorithms. Also, we picked the algorithms from different categories, includingmodularity-optimization-based, similarity-optimization-based, and GA-based methods, to give a broad picture of the performances of different algorithms. The methods which we use for the purpose of comparison are Louvain [29], Leiden [30], fast greedy [28], Infomap [17], LP [11], LocalGame [9], CCGA [34], CACD [22], GA-net [25], FluidCom [67], EdMot [31], WMW [14], WATSET [32], and CoreExpansion [68]. We use NMI and modularity measures in our comparisons and conduct experiments on nine real-world and seven synthetic networks. First, we explain the effects of different internal approaches and parameters. Then, we direct the discussion toward the advantages and disadvantages of our method compared to the other algorithms.


### 5.3.1. Representation

As we described in Section4.1, to construct the MST trees for the MST-based representations, we use node similarity measures to assign weights on the edges of graphs. Naturally, the MSTs will be different based on the applied similarity index because each measure highlights certain characteristics. To determine the best similarity index, we applied the indexes presented in Table 1 to the karate dataset. We used different similarity indexes from recent and classic literature and various categories. The resultant MST trees, and the final partitions, are shown in Figure 7. The bolded edges in this figure represent the MST edges. Figure 8 compares the results based on NMI and modularity. As it can be seen from Figure 7, the cosine and Jaccard similarity indexes perform similarly to each other, and their results have a better balance in terms of NMI and Q. It can be noticed from Figure 7 that the generated results are directly related to the corresponding MST trees. Specifically, by looking at the edges of node #5 and comparing them with the edges of the same node in different trees, one can understand the impact of each similarity measure. In all of the proceeding experiments, we use the Jaccard similarity to generate MST trees both because of its simplicity and its higher accuracy.Figure 7
This figure illustrates the impact of different similarity measures on the resultant MST tree and the final partition of the algorithm over the Zachary karate club dataset. (a) Common neighbors, (b) Jaccard, (c) Cosine, (d) HPI, (e) Adamic/Adar, (f) RA, (g) CNDP, (h) SRW, and (i) HIN.
(a)(b)(c)(d)(e)(f)(g)(h)(i)Figure 8
Comparison of the results of the proposed method for different similarity measures in the karate network.


### 5.3.2. Initial Population Generation

As we explained in Section4.2, we create the initial populations by splitting the MST tree into communities of n nodes. This method can result in very effective initial populations which involve near-optimum individuals. To evaluate the effectiveness of the initial population generation function, we compare the qualities of the initial populations generated by the proposed method with a random initial population generation method. Figure 9 compares the modularities of the best individuals and the average modularities of the initial populations for each approach. It can be seen that the proposed method performs considerably better than the random method. On the other hand, in Figure 10, generation 0 depicts the quality of the best individuals for four different algorithms; 1) the proposed algorithm, 2) CCGA, 3) CACD, and 4) GA-Net. While GA-net’s initial population is generated using a random function, CACD and CCGA use their initial population generation functions. As illustrated in Figure 10, our initial population generation function produces near-optimal individuals. The method of splitting the graph or data into clusters of n nodes/points has been already implemented in various clustering/community detection algorithms, but no other community detection method has implemented this method to generate initial populations for GAs.Figure 9
Comparison of the performance of the proposed initial population generation function (P) with random initial population generation function (Rand).Figure 10
Comparison of the results of the proposed method with other GAs on the Polbooks dataset. We ran all of the methods by a population size of 100 for 300 generations.


### 5.3.3. Mutation Function

The next influencing factor is the mutation function. To examine the effectiveness of the proposed mutation function, we conducted several experiments on the jazz dataset and compared the results based on the convergence time and the modularity score. The obtained results are shown in Figure11(a). To generate the outcomes, we ran 100 experiments while setting the stop criteria to exceed the modularity of 0.435 or observing no improvement in the modularity of the best individual for 50 consecutive generations. At first glance, we can see that the uncertainty of the number of generations to reach a solution is the highest at the weight-based mutation function. This function has a higher mean value and longer whiskers than the other functions. Also, this method has more upper outliers. Hence, we can conclude that this method performs weaker than the others. Considering its higher mean value, the main reason for its poor performance is its nonuniform probability distribution; thus, it has a higher tendency to get stuck in local optima, which might result in higher convergence time. On the other hand, the mean values (110.5 and 111) and the upper outliers of both sine-based and uniform-based functions are similar. But, the uniform-based function’s box is more compact than the sine-based function’s. Therefore, we can say that the deviations in the uniform function are less than those of the sine-based function, and its results are closer to the mean. Yet, it is apparent that the box of the sine-based method stands lower than that of the uniform-based method, and its lower whisker is longer than the whisker of the uniform-based method which means that the sine-based function can converge faster than the uniform-based method. Therefore, from Figure 11, we can conclude that the sine-based method performs almost 25% faster than the uniform-based method.Figure 11
Comparison of variations of the generation count and modularity for 3 different mutation functions. 100 experiments were performed over the Jazz dataset for each function, while the stopping criteria was, exceeding the modularity of 0.435, or seeing no improvement on the maximum modularity of each generation on 50 respective generations. (a) Box plots of the number of generations and (b) box plots of the maximum modularity of each experiment.
(a)(b)When comparing the variations of the modularity scores of the mutation functions, we observe that all of them have similar mean values, but theweight-based method has higher variations compared to the others. Again, this might have resulted from the nonuniform probability distribution, which results in getting stuck in local optima. Therefore, this method performs poorly both in terms of convergence time and the modularity score. Yet, comparing the sine-based and uniform-based functions shows that both of the boxes have similar upper sides, whereas the lower whisker of the sine-based distribution is considerably shorter than that of the uniform-based distribution, and it almost stands at the same value than where the lower side of the uniform-based method stands. This means that the likelihood of observing lower modularity is almost 25% lower when we use the sine-based method instead of the uniform-based one. This shows that our hypothesis in Section 4.5 was correct, and the sine-based mutation function can reduce the convergence time by changing the mutation probability distribution of the genes with a smoothly changing adaptive function and directing mutation probabilities to the border and central edges of each community. The box plots of the modularity variations are shown in Figure 11(b).Consequently, we can conclude that thesine-based method can produce better and faster outcomes. It should be considered that this advantage does not come without a cost. For the sine-based method, we have to perform a set of calculations, such as assigning a depth value for each edge. Therefore, using the sine-based function can be a cost-effective choice for small datasets.


### 5.3.4. Comparisons

Tables4 and 5 provide the results of the comparisons of the proposed method with the other methods based on NMI and modularity measures. We used the Jaccard similarity to assign weights to edges and the sine-based mutation function to perform mutations in our experiments. To run all of the GA-based methods, we set the population size to 100 for small networks and 300 for large ones. We ran all of the GA-based algorithms for 300 generations several times and recorded the best outcome. In our method, we set δ=0.1 in our experiments.Table 4
Comparison of the results of real-world datasets of the proposed method with other methods based on NMI and modularity (Q) measures.
NetworkKaratePolbooksPolblogsFootballDolphinsPowerJazzPGPCa-HepAverageQNMIQNMIQNMIQNMIQNMIQQQQQ¯NMI¯Proposed method0.420.600.520.570.430.450.600.820.520.730.930.440.860.750.6070.634CACD0.420.940.530.760.340.640.580.890.520.900.770.430.790.660.560.826CCGA0.420.690.520.530.370.330.550.700.520.730.900.420.840.530.5630.596GA-net0.400.630.430.400.350.300.600.910.420.580.640.370.600.530.480.56WATSET0.371.00.490.560.430.480.580.890.480.730.790.280.800.690.5450.73FluidCom0.350.580.440.480.430.450.580.890.380.460.890.420.820.680.5540.572EdMot0.420.600.530.530.290.360.600.880.520.780.940.440.870.770.5980.63WMW0.400.540.470.430.400.280.390.690.490.690.610.320.670.570.480.526LocalGame0.371.00.510.550.400.680.580.890.510.730.900.280.790.630.550.77Leiden0.420.690.520.520.430.630.600.870.530.770.940.440.880.770.6140.696CoreExpansion0.370.840.440.630.340.640.560.730.510.530.850.280.810.670.540.67Louvain0.420.590.520.510.430.630.600.880.520.480.930.440.880.820.6170.618Fast greedy0.380.690.500.530.430.650.550.700.500.610.930.440.850.780.5950.636Infomap0.400.700.520.490.420.480.600.920.520.500.820.280.800.730.5650.618LP0.400.700.500.570.430.690.600.920.500.690.810.280.810.740.5630.714In each column, the highest value is in bold.Table 5
Comparison of the results of synthetic networks of the proposed method with other methods based on NMI and modularity (Q) measures.
NetworkLFR-1LFR-2LFR-3LFR-4LFR-5LFR-6AverageQNMIQNMIQNMIQNMIQNMIQNMIQ¯NMI¯Proposed method0.610.540.431.00.821.00.701.00.531.00.661.00.620.92CACD0.540.800.431.00.821.00.580.870.110.570.110.480.430.79CCGA0.590.560.240.330.640.750.10.370.10.20.10.10.300.39GA-net0.520.430.240.420.610.850.200.300.10.10.10.10.300.37WATSET0.590.650.431.00.821.00.701.00.531.00.661.00.620.94FluidCom0.540.800.431.00.740.820.580.860.10.440.180.590.420.75EdMot0.620.610.431.00.821.00.701.00.531.00.661.00.660.93WMW0.520.430.240.420.740.960.701.00.531.00.661.00.570.80LocalGame0.491.00.431.00.821.00.701.00.531.00.661.00.601.0Leiden0.500.610.431.00.821.00.701.00.531.00.661.00.610.93CoreExpansion0.560.610.200.340.700.940.540.850.150.300.240.330.400.56Louvain0.470.390.431.00.821.00.701.00.531.00.661.00.600.90Fast greedy0.620.660.431.00.810.990.690.990.531.00.661.00.620.94Infomap0.600.540.431.00.821.00.701.00.531.00.661.00.620.92LP0.560.800.431.00.821.00.701.00.531.00.661.00.620.97In each column, the highest value is in bold.In real-world datasets, the comparisons show that the proposed method can produce competitive results on both NMI and modularity measures. It can be seen that the proposed method outperforms the other GA-based methods in almost all of the experiments in terms of the modularity scores. Our method results in an average of 0.607, while the best modularity is achieved by the Louvain algorithm at 0.617. On the other hand, while our method’s average NMI value is 0.634 and for Louvain it is 0.618. The best NMI value belongs to the CACD, with an NMI of 0.826 and a modularity of 0.56. In general, there is only one method (Leiden) that simultaneously performs better than our method in both modularity and NMI. The proposed method performs better in either one or both of the measures when it is compared with the average values of the other methods.Looking at the synthetic datasets, our method can reach the highest modularity and NMI values among the GAs with a modularity of 0.62 and an NMI of 0.92. The proposed method’s advantages become obvious as the network size increases. This is especially noticeable in the LFR5 and LFR6 datasets, which have a very high number of intercommunity edges. The reason for the other GA-based methods’ poor performance in these datasets is that they uselocus-based representation and keep testing different neighbors; therefore, they need both larger populations and more generations to reach better results. The proposed method lags behind EdMot in average modularity and LocalGame in average NMI values.Figure10 shows another significant analysis of the different GA-based community detection algorithms. This figure shows the modularity of the best individuals of each GA-based method on the Polbooks dataset over several generations. For this dataset, we set the generation size to 100 and let the methods run for 300 generations. Generation number 0 depicts the performance of initial population generation functions. While the best individual of our initial population has a modularity of 0.5 (almost equal to the final modularity), the closest method (CCAD) can produce individuals with maximum modularity of 0.43. Furthermore, while our method converges at the 20th generation at 0.5234, CCAD can only beat our method in the 148th generation, reaching convergence at the 189th generation at a modularity of 0.5266. The next two algorithms can never find better partitions, even on the 300th generation. Therefore, comparisons prove that the proposed algorithm can produce better results in a shorter period of time in comparison with other GAs. It is worth mentioning that the GA-net’s high fluctuations are the result of its fitness function. As explained in Section 2, this method does not use modularity as its fitness function (CACD and CCGA are both modularity-optimization-based methods).In LFR networks,μ defines the ratio of the intercommunity edges. A higher value of μ means that there are more edges between the nodes that belong to different communities instead of the nodes within the same community. In Figure 6, we compare the effect of the μ parameter on the outcomes of different methods. It is apparent from the figure that an increase in μ decreases modularity on almost all of the algorithms. This is because having more intercommunity edges is exactly the opposite of the way that modularity defines a community. LocalGame, a similarity-based method, because of its dependency on the distance between communities, falls immediately to 0 in both measures as soon as μ exceeds 0.5. CCGA and CACD’s modularity values behave almost identically to the changes in the μ parameter, but CACD results in higher NMI values. Yet, even though CACD’s NMI value stays the highest at μ=0.7, its NMI and modularity values start to decrease very quickly at μ=0.1. The proposed method’s NMI and modularity remain the highest as long as μ is below 0.4 and starts to decline after exceeding 0.5 though it remains the second-best method for almost all other μ values, and its NMI stays higher than EdMot’s at μ=0.7. Comparing the results shows that the proposed algorithm can produce acceptable outcomes when the mixing parameter changes.Extensive comparisons of different methods on both real-world and synthetic datasets show that the proposed method can produce competitive results with state-of-the-art algorithms.


## 5.3.1. Representation

As we described in Section4.1, to construct the MST trees for the MST-based representations, we use node similarity measures to assign weights on the edges of graphs. Naturally, the MSTs will be different based on the applied similarity index because each measure highlights certain characteristics. To determine the best similarity index, we applied the indexes presented in Table 1 to the karate dataset. We used different similarity indexes from recent and classic literature and various categories. The resultant MST trees, and the final partitions, are shown in Figure 7. The bolded edges in this figure represent the MST edges. Figure 8 compares the results based on NMI and modularity. As it can be seen from Figure 7, the cosine and Jaccard similarity indexes perform similarly to each other, and their results have a better balance in terms of NMI and Q. It can be noticed from Figure 7 that the generated results are directly related to the corresponding MST trees. Specifically, by looking at the edges of node #5 and comparing them with the edges of the same node in different trees, one can understand the impact of each similarity measure. In all of the proceeding experiments, we use the Jaccard similarity to generate MST trees both because of its simplicity and its higher accuracy.Figure 7
This figure illustrates the impact of different similarity measures on the resultant MST tree and the final partition of the algorithm over the Zachary karate club dataset. (a) Common neighbors, (b) Jaccard, (c) Cosine, (d) HPI, (e) Adamic/Adar, (f) RA, (g) CNDP, (h) SRW, and (i) HIN.
(a)(b)(c)(d)(e)(f)(g)(h)(i)Figure 8
Comparison of the results of the proposed method for different similarity measures in the karate network.


## 5.3.2. Initial Population Generation

As we explained in Section4.2, we create the initial populations by splitting the MST tree into communities of n nodes. This method can result in very effective initial populations which involve near-optimum individuals. To evaluate the effectiveness of the initial population generation function, we compare the qualities of the initial populations generated by the proposed method with a random initial population generation method. Figure 9 compares the modularities of the best individuals and the average modularities of the initial populations for each approach. It can be seen that the proposed method performs considerably better than the random method. On the other hand, in Figure 10, generation 0 depicts the quality of the best individuals for four different algorithms; 1) the proposed algorithm, 2) CCGA, 3) CACD, and 4) GA-Net. While GA-net’s initial population is generated using a random function, CACD and CCGA use their initial population generation functions. As illustrated in Figure 10, our initial population generation function produces near-optimal individuals. The method of splitting the graph or data into clusters of n nodes/points has been already implemented in various clustering/community detection algorithms, but no other community detection method has implemented this method to generate initial populations for GAs.Figure 9
Comparison of the performance of the proposed initial population generation function (P) with random initial population generation function (Rand).Figure 10
Comparison of the results of the proposed method with other GAs on the Polbooks dataset. We ran all of the methods by a population size of 100 for 300 generations.


## 5.3.3. Mutation Function

The next influencing factor is the mutation function. To examine the effectiveness of the proposed mutation function, we conducted several experiments on the jazz dataset and compared the results based on the convergence time and the modularity score. The obtained results are shown in Figure11(a). To generate the outcomes, we ran 100 experiments while setting the stop criteria to exceed the modularity of 0.435 or observing no improvement in the modularity of the best individual for 50 consecutive generations. At first glance, we can see that the uncertainty of the number of generations to reach a solution is the highest at the weight-based mutation function. This function has a higher mean value and longer whiskers than the other functions. Also, this method has more upper outliers. Hence, we can conclude that this method performs weaker than the others. Considering its higher mean value, the main reason for its poor performance is its nonuniform probability distribution; thus, it has a higher tendency to get stuck in local optima, which might result in higher convergence time. On the other hand, the mean values (110.5 and 111) and the upper outliers of both sine-based and uniform-based functions are similar. But, the uniform-based function’s box is more compact than the sine-based function’s. Therefore, we can say that the deviations in the uniform function are less than those of the sine-based function, and its results are closer to the mean. Yet, it is apparent that the box of the sine-based method stands lower than that of the uniform-based method, and its lower whisker is longer than the whisker of the uniform-based method which means that the sine-based function can converge faster than the uniform-based method. Therefore, from Figure 11, we can conclude that the sine-based method performs almost 25% faster than the uniform-based method.Figure 11
Comparison of variations of the generation count and modularity for 3 different mutation functions. 100 experiments were performed over the Jazz dataset for each function, while the stopping criteria was, exceeding the modularity of 0.435, or seeing no improvement on the maximum modularity of each generation on 50 respective generations. (a) Box plots of the number of generations and (b) box plots of the maximum modularity of each experiment.
(a)(b)When comparing the variations of the modularity scores of the mutation functions, we observe that all of them have similar mean values, but theweight-based method has higher variations compared to the others. Again, this might have resulted from the nonuniform probability distribution, which results in getting stuck in local optima. Therefore, this method performs poorly both in terms of convergence time and the modularity score. Yet, comparing the sine-based and uniform-based functions shows that both of the boxes have similar upper sides, whereas the lower whisker of the sine-based distribution is considerably shorter than that of the uniform-based distribution, and it almost stands at the same value than where the lower side of the uniform-based method stands. This means that the likelihood of observing lower modularity is almost 25% lower when we use the sine-based method instead of the uniform-based one. This shows that our hypothesis in Section 4.5 was correct, and the sine-based mutation function can reduce the convergence time by changing the mutation probability distribution of the genes with a smoothly changing adaptive function and directing mutation probabilities to the border and central edges of each community. The box plots of the modularity variations are shown in Figure 11(b).Consequently, we can conclude that thesine-based method can produce better and faster outcomes. It should be considered that this advantage does not come without a cost. For the sine-based method, we have to perform a set of calculations, such as assigning a depth value for each edge. Therefore, using the sine-based function can be a cost-effective choice for small datasets.


## 5.3.4. Comparisons

Tables4 and 5 provide the results of the comparisons of the proposed method with the other methods based on NMI and modularity measures. We used the Jaccard similarity to assign weights to edges and the sine-based mutation function to perform mutations in our experiments. To run all of the GA-based methods, we set the population size to 100 for small networks and 300 for large ones. We ran all of the GA-based algorithms for 300 generations several times and recorded the best outcome. In our method, we set δ=0.1 in our experiments.Table 4
Comparison of the results of real-world datasets of the proposed method with other methods based on NMI and modularity (Q) measures.
NetworkKaratePolbooksPolblogsFootballDolphinsPowerJazzPGPCa-HepAverageQNMIQNMIQNMIQNMIQNMIQQQQQ¯NMI¯Proposed method0.420.600.520.570.430.450.600.820.520.730.930.440.860.750.6070.634CACD0.420.940.530.760.340.640.580.890.520.900.770.430.790.660.560.826CCGA0.420.690.520.530.370.330.550.700.520.730.900.420.840.530.5630.596GA-net0.400.630.430.400.350.300.600.910.420.580.640.370.600.530.480.56WATSET0.371.00.490.560.430.480.580.890.480.730.790.280.800.690.5450.73FluidCom0.350.580.440.480.430.450.580.890.380.460.890.420.820.680.5540.572EdMot0.420.600.530.530.290.360.600.880.520.780.940.440.870.770.5980.63WMW0.400.540.470.430.400.280.390.690.490.690.610.320.670.570.480.526LocalGame0.371.00.510.550.400.680.580.890.510.730.900.280.790.630.550.77Leiden0.420.690.520.520.430.630.600.870.530.770.940.440.880.770.6140.696CoreExpansion0.370.840.440.630.340.640.560.730.510.530.850.280.810.670.540.67Louvain0.420.590.520.510.430.630.600.880.520.480.930.440.880.820.6170.618Fast greedy0.380.690.500.530.430.650.550.700.500.610.930.440.850.780.5950.636Infomap0.400.700.520.490.420.480.600.920.520.500.820.280.800.730.5650.618LP0.400.700.500.570.430.690.600.920.500.690.810.280.810.740.5630.714In each column, the highest value is in bold.Table 5
Comparison of the results of synthetic networks of the proposed method with other methods based on NMI and modularity (Q) measures.
NetworkLFR-1LFR-2LFR-3LFR-4LFR-5LFR-6AverageQNMIQNMIQNMIQNMIQNMIQNMIQ¯NMI¯Proposed method0.610.540.431.00.821.00.701.00.531.00.661.00.620.92CACD0.540.800.431.00.821.00.580.870.110.570.110.480.430.79CCGA0.590.560.240.330.640.750.10.370.10.20.10.10.300.39GA-net0.520.430.240.420.610.850.200.300.10.10.10.10.300.37WATSET0.590.650.431.00.821.00.701.00.531.00.661.00.620.94FluidCom0.540.800.431.00.740.820.580.860.10.440.180.590.420.75EdMot0.620.610.431.00.821.00.701.00.531.00.661.00.660.93WMW0.520.430.240.420.740.960.701.00.531.00.661.00.570.80LocalGame0.491.00.431.00.821.00.701.00.531.00.661.00.601.0Leiden0.500.610.431.00.821.00.701.00.531.00.661.00.610.93CoreExpansion0.560.610.200.340.700.940.540.850.150.300.240.330.400.56Louvain0.470.390.431.00.821.00.701.00.531.00.661.00.600.90Fast greedy0.620.660.431.00.810.990.690.990.531.00.661.00.620.94Infomap0.600.540.431.00.821.00.701.00.531.00.661.00.620.92LP0.560.800.431.00.821.00.701.00.531.00.661.00.620.97In each column, the highest value is in bold.In real-world datasets, the comparisons show that the proposed method can produce competitive results on both NMI and modularity measures. It can be seen that the proposed method outperforms the other GA-based methods in almost all of the experiments in terms of the modularity scores. Our method results in an average of 0.607, while the best modularity is achieved by the Louvain algorithm at 0.617. On the other hand, while our method’s average NMI value is 0.634 and for Louvain it is 0.618. The best NMI value belongs to the CACD, with an NMI of 0.826 and a modularity of 0.56. In general, there is only one method (Leiden) that simultaneously performs better than our method in both modularity and NMI. The proposed method performs better in either one or both of the measures when it is compared with the average values of the other methods.Looking at the synthetic datasets, our method can reach the highest modularity and NMI values among the GAs with a modularity of 0.62 and an NMI of 0.92. The proposed method’s advantages become obvious as the network size increases. This is especially noticeable in the LFR5 and LFR6 datasets, which have a very high number of intercommunity edges. The reason for the other GA-based methods’ poor performance in these datasets is that they uselocus-based representation and keep testing different neighbors; therefore, they need both larger populations and more generations to reach better results. The proposed method lags behind EdMot in average modularity and LocalGame in average NMI values.Figure10 shows another significant analysis of the different GA-based community detection algorithms. This figure shows the modularity of the best individuals of each GA-based method on the Polbooks dataset over several generations. For this dataset, we set the generation size to 100 and let the methods run for 300 generations. Generation number 0 depicts the performance of initial population generation functions. While the best individual of our initial population has a modularity of 0.5 (almost equal to the final modularity), the closest method (CCAD) can produce individuals with maximum modularity of 0.43. Furthermore, while our method converges at the 20th generation at 0.5234, CCAD can only beat our method in the 148th generation, reaching convergence at the 189th generation at a modularity of 0.5266. The next two algorithms can never find better partitions, even on the 300th generation. Therefore, comparisons prove that the proposed algorithm can produce better results in a shorter period of time in comparison with other GAs. It is worth mentioning that the GA-net’s high fluctuations are the result of its fitness function. As explained in Section 2, this method does not use modularity as its fitness function (CACD and CCGA are both modularity-optimization-based methods).In LFR networks,μ defines the ratio of the intercommunity edges. A higher value of μ means that there are more edges between the nodes that belong to different communities instead of the nodes within the same community. In Figure 6, we compare the effect of the μ parameter on the outcomes of different methods. It is apparent from the figure that an increase in μ decreases modularity on almost all of the algorithms. This is because having more intercommunity edges is exactly the opposite of the way that modularity defines a community. LocalGame, a similarity-based method, because of its dependency on the distance between communities, falls immediately to 0 in both measures as soon as μ exceeds 0.5. CCGA and CACD’s modularity values behave almost identically to the changes in the μ parameter, but CACD results in higher NMI values. Yet, even though CACD’s NMI value stays the highest at μ=0.7, its NMI and modularity values start to decrease very quickly at μ=0.1. The proposed method’s NMI and modularity remain the highest as long as μ is below 0.4 and starts to decline after exceeding 0.5 though it remains the second-best method for almost all other μ values, and its NMI stays higher than EdMot’s at μ=0.7. Comparing the results shows that the proposed algorithm can produce acceptable outcomes when the mixing parameter changes.Extensive comparisons of different methods on both real-world and synthetic datasets show that the proposed method can produce competitive results with state-of-the-art algorithms.


## 6. Conclusions

In this article, we proposed a new method to detect communities in complex networks using an adaptive evolutionary approach. We introduce a new encoding scheme, using node similarity indexes and MSTs, which does not have the disadvantages of the previous representations such as resulting in separate communities and meaningless mutations. Also, we have introduced a new method to generate initial populations. This method can enhance the convergence time and quality of the initial population drastically. Furthermore, an adaptivesine-based mutation function was introduced, which changes the mutation probability of each gene based on the depth of its corresponding edge in MST. The new mutation function can help to reach better and faster results.Several experiments were conducted on real-world and synthetic networks, and the results were compared with other community detection algorithms. Results show that the proposed method can perform better and faster than the existing GA-based methods and produce comparable results with the state-of-the-art methods on both NMI and modularity measures.Evaluation of the impact of different similarity measures along with the extraction of application-specific skeleton networks, instead of MSTs, to be used in various types of networks (such as temporal networks and directed networks) are among the possible future works of this article.



---

*Source: 4796536-2023-02-28.xml*