# A Memetic Algorithm Based on Adaptive Simulated Annealing for Community Detection

Jie Yang, Yifei Sun, Shi Cheng, Kun Bian, Zhuo Liu, Xin Sun, Yifei Cao

► To cite this version:

Jie Yang, Yifei Sun, Shi Cheng, Kun Bian, Zhuo Liu, et al. A Memetic Algorithm Based on Adaptive Simulated Annealing for Community Detection. 5th International Conference on Intelligence Science (ICIS), Oct 2022, Xi'an, China. pp.20-28, 10.1007/978-3-031-14903-0_3. hal-04666408

HAL Id: hal-04666408

https://hal.science/hal-04666408v1

Submitted on 1 Aug 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# A Memetic Algorithm Based on Adaptive Simulated Annealing for Community Detection

Jie Yang¹, Yifei Sun¹*, Shi Cheng², Kun Bian¹, Zhuo Liu¹, Xin Sun¹, Yifei Cao¹

¹ School of Physics and Information Technology, Shaanxi Normal University, Xi’an, China
{jieyang2021,yifeis,biankun,zhuoliu,sunxin_,yifeic}@snnu.edu.cn

² School of Computer Science, Shaanxi Normal University, Xi’an 710119, China
cheng@snnu.edu.cn

**Abstract.** The application of community detection (community discovery) has been widely used in various fields for several years. To improve the algorithm accuracy, we proposed a memetic algorithm based on an adaptive simulated annealing local search (MA-ASA). Segmented label propagation (STLP) is used for initialization and variation operations. A hierarchical idea is adopted to form an initial cluster center during initialization, and random competition is used to select the next generation of solutions. Instead of using fixed probabilities in each crossover and variation operation, we used quality differences to switch to adaptive probabilities in simulated annealing (SA) for local search to accelerate convergence. The algorithm was extensively tested and experimented with 11 artificial and 4 real networks. Compared with other 10 algorithms, the results showed that MA-ASA performs well and is highly competitive.

**Keywords:** Community detection; Memetic algorithms; Dynamic probability; Simulated annealing.

## 1 Introduction

Systems can be modeled as complex network for research, such as aviation networks, computer networks and social networks [1,2]. Community structure is defined as one that is more tightly connected internally and more sparsely connected externally [3].

Many algorithms had been proposed in the past several decades. Newman and Girvan introduced modularity for community detection (GN) [4]. Newman proposed the FN algorithm based on GN [5]. Gong et al. [6] have introduced memetic algorithms (MAs) for community detection. It was optimized by modifying the local strategy [7]. Sun et al. [8] proposed the MAPL algorithm for community division. There are evolutionary algorithms [9,10] which focus on optimizing multiple objective functions.

In this paper, we proposed a new memetic algorithm for community detection named MA-ASA. We primarily use label propagation to initialize the nodes. In each generation of selection and crossover, the poorly performing individuals are labeled for change by comparing the modularity. Secondly, dynamic probability is used to select specific variation strategies in local search. We use MA-ASA to test 4 real
world networks and 11 synthetic networks. The final results of the experiments demonstrated that MA-ASA is highly competitive.

The rest of this dissertation is organized as follows. Section 2 illustrates the complex networks and the common concepts of community detection. Section 3 presents the proposed algorithm. Section 4 provides the results and data analysis of the experiments. Section 5 summarizes the full paper and suggests possible follow-up studies.

## 2 Background

In graph theory, complex networks are usually described by a graph $G = (V, E)$, where $V$ stands for the nodes in the network and $E$ stands for the connection between nodes. If there is a connection between the node A and B, then $A_{ij} = 1$, otherwise 0.

### 2.1 Modularity

Modularity was proposed by Newman and Girvan to assess the quality of community division [4,5]. The formula is as follows:

$$Q = \sum_{i=1}^{c} \left[ \frac{l_i}{m} - \left( \frac{k_i}{2m} \right)^2 \right] \quad (1)$$

Where $c$ denotes the number of communities partitioned, $m$ is the total number of edges, $l_i$ is the sum of edges contained in the $i$th community and $k_i$ indicates the sum of the node degrees of the $i$th community.

### 2.2 Normalized Mutual Information

Normalized mutual information (NMI) was used to evaluate the quality of the generated solutions. The value of NMI ranges from 0 to 1. When it is equal to 1, the resulting solution is consistent with the actual division. The NMI is defined as follows:

$$NMI(A, B) = \frac{-2 \sum_{i=1}^{C_A} \sum_{j=1}^{C_B} c_{ij} \log \left( \frac{c_{ij} N}{c_i c_j} \right)}{\sum_{i=1}^{C_A} c_i \log \left( \frac{c_i}{N} \right) + \sum_{j=1}^{C_B} c_j \log \left( \frac{c_j}{N} \right)} \quad (2)$$

Where $C_A(C_B)$ is the number of communities divided into A(B), $C_i(C_j)$ is the sum of the elements of the $i$th row (jth column) of the adjacency matrix and $N$ denotes the number of network nodes.

## 3 Description of MA-ASA

### 3.1 Segmented Label Propagation

In this paper, we apply segmented label propagation (STLP) to network initialization. Assume that each node has a set of neighbors $\Omega(i) = \{x_1, x_2, ..., x_i\}$, and $L(i)$ is
denoted as the label of the *i*th node. We initialize the node labels as $L(i) = i$, i.e., $L = \{1, 2, ..., i\}$. We stratify label propagation into potential community nodes and common nodes. In the first stage (STLP-1), the nodes are divided into two layers of strong and weak nodes; while the second stage (STLP-2) is used for variation.

We filter out the nodes which are much larger than average node degrees. Assume that they are more influential individuals and radiate their labels. And these identically labeled nodes are then highly likely to be a potential community respectively.

## 3.2 Selection and Crossover Operation

In MA-ASA, we use random competitive selection to preserve the better individual. Dynamic probabilities are used to improve the overall population quality. **Fig. 1** shows an example when the dynamic crossover probability equals to 50%. The inferior performing solution evolves into a new solution after crossover pairing.

<figure><img src="image_3.png" /><figcaption>Fig. 1. The process of secondary solution updated to a new solution</figcaption></figure>

## 3.3 Mutation Operation

We adopted three different strategies which selected by adaptive probability. The first two strategies we called STLP-2. The labels are mainly updated by (a) roulette selection and (b) equal probability selection. Meanwhile, to avoid local convergence, we set a small probability event (c) to do a random update for the labels. In **Fig. 2**, the green and orange circles are the division of node 5 neighbor set. When operation (a) is taken, the mutation probability is determined by neighbors. When operation (b) is adopted, the probability is changed to the ratio of the number of circles.

<figure><img src="image_4.png" /><figcaption>Fig. 2. Node 5 variation operation description diagram</figcaption></figure>

## 3.4 Improved Simulated Annealing

Conventional SA is based on the principle of thermodynamics. We set the temperature $T=100$, the decay rate $\alpha=0.98$ and the stopping condition $T<0.1$. We improved the probability equation as follows:
$$P = \exp\left(-\frac{G(Q_{old} - Q_{new})}{T}\right) \qquad (3)$$

Where G is the fitness gain coefficient, which is associated with the number of nodes. Qnew is the fitness of the newly obtained solution of the current population and Qold means the historical optimal fitness of the current population.

**Algorithm 1: Framework of Improved Simulated Annealing**

**Input:** The population size: Np; the temperature: T; the attenuation rate: α.

**Output:** Node labels for each population

**for** (i = 1:Np)

T ← ResetOperation;

**while** (T)

pop ← Mutation(pop);

pop ← EvaluateFitness(pop);

bestQ ← MetropolisRule(pop);

T ← AttenuationOperation(α);

**end while**

**end for**

## 3.5 Framework of MA-ASA

The proposed MA-ASA algorithm in this article is composed of STLP for initialization, mutation, random competitive selection and improved simulated annealing. The algorithm framework is given in **Algorithm 2**.

**Algorithm 2: Framework of MA-ASA**

**Input:** The adjacency matrix: A; the population size: Np; the maximum number of generations: Gmax; the initial temperature: T; the attenuation rate: α.

**Output:** The partition of the network with the largest modularity: Q.

pop ← STLP-1(pop);

pop ← EvaluateFitness(pop);

bestQ ← SaveBest(pop);

**for** (i = 1: Gmax)

**while** (Np)

pop ← Selection and Crossover operation;

**end while**

**while** (T)

pop ← LocalSearch(pop);

bestQ ← SaveBest(pop);

T ← AttenuationOperation(α);

**end while**

**end for**
# 4 Experiments and Analysis

## 4.1 Experimental Settings

The algorithm was written in C and compiled by gcc version 5.4.0 with Ubuntu 16.04. The simulation was tested on a PC with Intel (R) Core (TM) i5-10210U CPU @ 1.60 GHz 2.11 GHz, 8 GB DDR4 RAM, Microsoft (R) Windows 10 Home OS. The population size is set to 100 and the number of iterations is 200.

**Experimental networks.** The GN benchmark network [11] is a benchmark network. There exists a mixing parameter $\gamma$, which represents the percentage of each node within the community that is connected to other community nodes. In layman's terms, the larger $\gamma$ is, the more difficult it is to delineate the correct partition. 11 GN networks were generated at 0.05 intervals in the range of $\gamma$ from 0 to 0.5.

Four real-world networks were selected to test the effectiveness of MA-ASA and to compare with other algorithms. These networks are Zachary's Karate Club network (Karate) [12], Bottlenose Dolphins network (Dolphins) [13], American College Football network (Football) [11], and Jazz musicians' network (Jazz) [14]. The details of these networks are listed in Table 1. $V$, $E$ and $\bar{k}$ are the total number of nodes, the sum of edges and the average node degree of each network respectively.

<table><caption>Table 1. Topological characteristics of each real network.</caption><thead><tr><th>Networks</th><th><i>V</i></th><th><i>E</i></th><th><i>k</i></th></tr></thead><tbody><tr><td>Karate</td><td>34</td><td>78</td><td>4.59</td></tr><tr><td>Dolphins</td><td>62</td><td>159</td><td>5.13</td></tr><tr><td>Football</td><td>115</td><td>613</td><td>10.66</td></tr><tr><td>Jazz</td><td>198</td><td>2742</td><td>27.70</td></tr></tbody></table>

## 4.2 Experimental Results and Analysis

In this paper we compared the result of real network by testing with MODPSO [15], MOGA-net [16], MOEA/D-net [17], MOCD [18], Meme-net [6], GA-net [19], GN [11], NIMA [20], Louvain [21] and CNM [22].

shows the experimental results of the 4 real-world networks. Specifically, in the three networks, Karate, Dolphins, and Football, the proposed MA-ASA was able to find the clusters with the largest $Q$ value in each run. MODPSO was able to find the best partition in Karate and Football, but was unstable. Although Louvain could find the maximum $Q$ value in Football and Jazz as well, its results were also unstable. Both MA-ASA and MODPSO did not reach the maximum $Q$ value in Jazz, but were more stable than Louvain. MA-ASA had better performance than MODPSO. Fig. 3 shows the community partition of Jazz network, where the nodes are divided into four communities and painted with different colors.
<figure><img src="image_5.png" /><figcaption>Fig. 3. Partition of Jazz network through MA-ASA</figcaption></figure>

<table><caption>**Table 2.** Comparison results of modularity *Q* values in real-world networks for algorithms.</caption><thead><tr><th>Networks</th><th>Indexes</th><th>MA-ASA</th><th>MODPSO</th><th>MOGA-net</th><th>Louvain</th></tr></thead><tbody><tr><td rowspan="3">Karate</td><td>Q<sub>max</sub></td><td><strong>0.4198</strong></td><td><strong>0.4198</strong></td><td>0.4159</td><td>0.4188</td></tr><tr><td>Q<sub>ave</sub></td><td><strong>0.4198</strong></td><td>0.4182</td><td>0.3945</td><td>0.4165</td></tr><tr><td>Q<sub>std</sub></td><td><strong>0</strong></td><td>0.0079</td><td>0.0089</td><td>0.0077</td></tr><tr><td rowspan="3">Dolphins</td><td>Q<sub>max</sub></td><td><strong>0.5222</strong></td><td>0.5216</td><td>0.5034</td><td>0.5168</td></tr><tr><td>Q<sub>ave</sub></td><td><strong>0.5222</strong></td><td>0.5208</td><td>0.4584</td><td>0.5160</td></tr><tr><td>Q<sub>std</sub></td><td><strong>0</strong></td><td>0.0062</td><td>0.0163</td><td>0.0029</td></tr><tr><td rowspan="3">Football</td><td>Q<sub>max</sub></td><td><strong>0.6046</strong></td><td><strong>0.6046</strong></td><td>0.4325</td><td><strong>0.6046</strong></td></tr><tr><td>Q<sub>ave</sub></td><td><strong>0.6046</strong></td><td>0.6038</td><td>0.3906</td><td>0.6043</td></tr><tr><td>Q<sub>std</sub></td><td><strong>0</strong></td><td>0.0011</td><td>0.0179</td><td>0.0009</td></tr><tr><td rowspan="3">Jazz</td><td>Q<sub>max</sub></td><td>0.4450</td><td>0.4421</td><td>0.2952</td><td><strong>0.4451</strong></td></tr><tr><td>Q<sub>ave</sub></td><td>0.4445</td><td>0.4419</td><td>0.2929</td><td>0.4443</td></tr><tr><td>Q<sub>std</sub></td><td><strong>0.0001</strong></td><td><strong>0.0001</strong></td><td>0.0084</td><td>0.0023</td></tr></tbody></table>

<figure><img src="image_6.png" /><figcaption>Fig. 4. Average NMI of different algorithms on GN benchmark networks</figcaption></figure>
**Fig. 4** plots the comparison results of algorithms in 11 GN benchmark networks. On the graph, it can be seen that all algorithms can get the best partition when the mixing parameter $\gamma \le 0.10$. With the increase of the mixing parameter, the average NMI value starts to decrease. NIMA also has a mean NMI value of 1 at $\gamma \le 0.45$, but it drops to 0.9875 when the mixing parameter increases to 0.5. Even when the mixing parameter reaches 0.50, the MA-ASA can find the correct partition. To confirm the authenticity of the experiment, we increased the number of tests to 100 times. In 100 independent tests, when the mixing parameter reaches 0.50, its average NMI is 1, i.e., the probability of incorrect partitioning is less than 1%, which is the best performance among the various algorithms in the figure.

# 5 Conclusion

This article proposes an adaptive memetic algorithm MA-ASA to solve the community detection problem. The algorithm consists of segmented label propagation initialization, random-competition based selection and crossover, variation, and improved simulated annealing for local search. At the same time, dynamic probability is used to determine the chance of change according to its fitness. Numerous experiments show that MA-ASA is an effective method in community detection.

Although MA-ASA performs well in the experimental results, the algorithm will take long time. We should use the relevant properties to accelerate the convergence and shorten runtime. Meanwhile, we can extend MA-ASA to detect dynamic networks and use the properties of simulated annealing to avoid the premature convergence.

**Acknowledgements.** This work was supported by the National Natural Science Foundation of China (Grant No. 61703256, 61806119), Natural Science Basic Research Plan in Shaanxi Province of China (Program No. 2022JM-381, 2017JQ6070) and the Fundamental Research Funds for the Central Universities (Program No. GK201803020, GK201603014).

# References

1. Latora, V., Nicosia, V., Russo, G.: Complex Networks: Principles, Methods and Applications. 1st ed. Cambridge University Press, UK (2017).

2. Wasserman, S., Faust, K.: Social Network Analysis. Cambridge University Press, Nov 25, page 825 (1994).

3. Li, Q., Zhong, J., Cao, Z., Wang, C.: Enhancing network embedding with implicit clustering, 452–467 (2019).

4. Newman, M.E.J., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69(2), 026113 (2004).

5. Newman, M.E.J.: Fast algorithm for detecting community structure in networks, Phys. Rev. E 69(6), 066133 (2004).

6. Gong, M., Fu, B., Jiao, L., Du, H.: Memetic algorithm for community detection in networks. Physical Review E, 84, 056101 (2011).
7. Gong, M., Cai, Q., Li, Y., Ma, J.: An improved memetic algorithm for community detection in complex networks. 2012 IEEE Congress on Evolutionary Computation (CEC), 2012.

8. Sun, X., Sun, Y., Cheng, S., Bian, K., Liu, Z.: Population Learning Based Memetic Algorithm for Community Detection in Complex Networks. In: Tan, Y., Shi, Y., Zomaya, A., Yan, H., Cai, J. (eds) Data Mining and Big Data. DMBD 2021. Communications in Computer and Information Science, vol 1454. Springer, Singapore (2021).

9. Bian, K., Sun, Y., Cheng, S., Liu, Z., Sun, X.: Adaptive Methods of Differential Evolution Multi-objective Optimization Algorithm Based on Decomposition. In: Zhang H., Yang Z., Zhang Z., Wu Z., Hao T. (eds) Neural Computing for Advanced Applications. NCAA 2021. Communications in Computer and Information Science, vol 1449, pp. 458-472. Springer, Singapore (2021).

10. Sun, Y., Bian, K., Liu, Z., Sun, X., Yao, R.: Adaptive Strategies Based on Differential Evolutionary Algorithm for Many-Objective Optimization. Discrete Dynamics in Nature and Society (2021).

11. Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America 99(12), 7821-7826 (2002).

12. Zachary, W.W.: An information flow model for conflict and fission in small groups. J. Anthropol. Res. 452-473 (1977).

13. Lusseau, D., Schneider, K., Boisseau, O.J.: The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations. Behav. Ecol. Sociobiol. 54(4), 396-405 (2003).

14. Gleiser, P., Danon, L.: Community structure in jazz. Advances in Complex Systems 6(4), 565 (2003).

15. Gong, M., Cai, Q., Chen, X., Ma, L.: Complex network clustering by multiobjective discrete particle swarm optimization based on decomposition. IEEE Trans. Evol. Comput. 18(1), 82-97 (2014).

16. Pizzuti, C.: A multiobjective genetic algorithm to find communities in complex networks. IEEE Trans. Evol. Comput. 16(3), 418-430 (2012).

17. Gong, M., Ma, L., Zhang, Q., Jiao, L.: Community detection in networks by using multi-objective evolutionary algorithm with decomposition. Phys. A 391(15), 4050-4060 (2012).

18. Shi, C., Yan, Z., Cai, Y., Wu, B.: Multi-objective community detection in complex networks, Appl. Soft Comput. 12(2), 850-859 (2012).

19. Pizzuti, C.: GA-Net: A genetic algorithm for community detection in social networks. in Proc. Parallel Problem Solving Nat. 5199, 1081-1090 (2008).

20. Liu, Z., Sun, Y., Cheng, S., Sun, X., Bian, K., Yao, R.: A Node Influence Based Memetic Algorithm for Community Detection in Complex Networks. In: Pan, L., Cui, Z., Cai, J., Li, L. (eds) Bio-Inspired Computing: Theories and Applications. BIC-TA 2021. Communications in Computer and Information Science, vol 1565. Springer, Singapore (2022).

21. Blondel, V. D., et al.: Fast unfolding of communities in large networks. Journal of Statistical Mechanics Theory & Experiment (2008).

22. Clauset, A., Newman, M.E.J., Moore, C.: Finding community structure in very large networks. Phys. Rev. E 70(6), 066111 (2004).