Research on complex network community identification based on partially optimized genetic algorithm

Abstract

The research of complex networks has become a hot research field, and has been successfully applied in many fields such as social network analysis, protein network analysis, and link prediction. In this paper, the traditional genetic algorithm has strong randomness and weak search ability in the community identification method. A complex network community recognition algorithm based on local optimization genetic algorithm is proposed. The method uses label propagation strategy to produce a certain precision. The initial population; a combined one-way crossover strategy is proposed to avoid destroying the original excellent community structure in the cross process; the local heuristic mutation strategy is used to ensure the accuracy of the identification community, and the overall optimization ability of the algorithm is realized. Finally, the effectiveness of the algorithm is verified by experiments.

Keywords

Genetic algorithm complex network community identification

1. Introduction

At present, the research of complex networks has become a hot research field, attracting the attention of researchers from computer, mathematics, biology, physics and sociology. In recent years, scholars in different fields have proposed many kinds of classic community identification methods. For example, the algorithm based on split GN [1] is only applicable to small complex networks, CPM algorithm based on faction penetration [2], LC algorithm based on edge clustering [3], LPA algorithm based on label propagation [4], based on seeds The extended LFM algorithm [5], the BGLL algorithm based on modularity optimization [6] and the FN algorithm based on local modularity optimization [7]. At present, the community recognition method based on modularity Q (Modularity) has become one of the mainstream methods in the field of community identification. Such algorithms actually transform the community recognition problem into a function optimization problem. However, the Q function has the problem of not being able to identify the resolution limit of a very small community structure. The research shows that solving the maximum module degree problem is a NP complete problem. Therefore, genetic algorithm, as the most effective method to solve NP problem, has been widely applied to the field of community identification. For example, the LPA algorithm was proposed by Zhu et al. in 2002. It is a graph-based semi-supervised learning method. The basic idea is to use the tag information of the marked nodes to predict the tag information of the unmarked nodes. The advantage is that the operation efficiency is high, and the time complexity of the algorithm is O (n), where n is the number of edges in the network. The disadvantage is that there is a defect that the randomness is too high, which affects the quality of community identification. The CDGA algorithm proposed by Tasgin et al. [8] proposed a one-way crossover strategy to maximize the optimal community structure in the individual, and combined the neighboring node initialization population and the random mutation strategy to complete the community identification. The GANET algorithm proposed by Pizzuti [9] introduced the graph-based coding method into the field of community identification, and adopted the strategy of uniform crossover, random variation and elite selection to complete the community identification task. He Dongxiao et al. proposed CCGA algorithm, using string encoding as the encoding method of the algorithm, using Markov random walk method to initialize the population, combined with Q function to propose clustering fusion crossover strategy between multiple bodies, and using local The mutation strategy completes the community identification task. The MEME-NET algorithm proposed by Gong et al. [10] further processed the excellent individuals obtained by the genetic algorithm through the hill climbing algorithm to obtain a better community structure. Based on the genetic algorithm, Shang et al. [11] further optimized the excellent individuals through simulated annealing algorithm to obtain a better community structure. Based on the CDGA algorithm, Shi et al. introduced a single-way crossover operation based on string coding strategy to the graph-based coding strategy to design a genetic algorithm that can deal with large-scale networks [12]. The above mentioned algorithms are based on the community identification method of genetic algorithm, but there are still some defects such as slow convergence rate and easy to fall into local optimal solution, which affects the quality of community identification. The analysis is due to the randomness of the algorithmic operation and the use of destructive crossover and mutation strategies. However, genetic algorithms are not suitable for large-scale complex networks. The community identification problem based on genetic algorithm should find a suitable coding method, the coding method should be simple, and it is suitable for the operation of mutation and crossover operator, and need to pay attention to the design of the operator, the initial population and the elimination mechanism. At the same time, the design of mutation and crossover operation should consider ensuring that good genes can be transmitted to the next generation. Consider the diversity of the next generation.

From the above analysis, we can see that it is very important to explore the initial population method with higher accuracy and reasonable crossover and mutation strategy when using genetic algorithm to accomplish community identification task. Based on this, this paper proposes a complex network community recognition algorithm based on local optimization genetic algorithm. First, the use of tag propagation for population initialization improves the accuracy of initializing individual populations. Secondly, in view of the traditional cross-cutting strategy, it is easy to destroy the defects of the existing excellent community structure, improve the single-way crossover strategy, and propose a combined one-way crossover strategy. Finally, a local heuristic mutation strategy is proposed for the problem that the traditional mutation strategy has greater randomness and weak local optimization ability.

2. Community identification based on partially optimized genetic algorithm

2.1 The choice of objective function

The module Q-function is a quantitative index to evaluate the quality of the network community structure. At present, this index has been generally accepted by researchers in the field of community identification. Therefore, Q function is taken as the objective function of POGA algorithm. The main idea of Q function is to evaluate the difference between the size of the community structure and the stochastic network whose node degree is stable. If the Q function value is larger, the closer the internal connections in the community are, the higher the community structure quality is. On the contrary, the lower the quality of community structure, the module function $Q$ can be expressed as Eq. (1):

$\displaystyle Q=\sum\limits_{i}(e_{ii}-a_{i}^{2})$ (1)

where $e_{ii}$ represents the proportion of all edges in the same community $i$ that both nodes of one edge occupy, and $a_{i}$ represents the proportion of all edges in the network $i$ that at least one node occupies in the community $i$ .

The average conductivity function is to evaluate the loose connection between communities. Its function is defined as follows.

Let $S$ be a set of nodes in network $N$ , $V$ be a community, and its community $V$ conductivity function $C(P)$ may be defined as Eq. (2):

$\displaystyle C(P)=\frac{1}{k}\sum\limits_{i=1}^{k}{\phi(V_{i})}$ (2)

where $P$ represents a community identification result of a complex network, $P=\{{V_{1},V_{2},\ldots,V_{k}}\}$ , $k$ represents the number of communities in the network, $V_{i}$ represents the $i$ -th community in the network, and $\phi(V_{i})$ represents the conductivity. It can be found that the lower the value of $C(P)$ , the looser the connection between the communities and the clearer the community structure.

2.2 Encoding

When using genetic algorithm to accomplish the task of community identification, the solution of the problem is transformed into the chromosomes or individuals in the genetic algorithm through coding operations. Coding operation is the basis of genetic algorithm to deal with the problem, is an individual phenotype conversion to genotype process, which determines the individual’s genotype through which decoding mode conversion to phenotype, while the subsequent crossover, mutation and other genetic operations The choice also has important implications. In complex networks, an individual’s code is an array or string of bits used to represent some sort of result, also called chromosomes. The position of a gene in a chromosome is called a locus or a gene and it also means that one of the complex networks Node, chromosome corresponds to a division of the complex network, the chromosome solution space corresponding to all possible methods of division, from the resulting solution space corresponding to the chromosome called coding; from one of the mapping of chromosomes into the solution space is called decoding. Currently, the coding methods used in community mining algorithms based on genetic algorithms are based on string-based coding [14] and on the basis of genetic code [15]. In this paper, we use a coding method based on the position of a gene to represent an individual in a population composed of several network communities, that is, an individual code represents the result of dividing an online community.

2.3 Initialize the population

Only when each individual in the initial population has a certain degree of accuracy is it possible to give full play to the advantages of genetic algorithm optimization. Therefore, based on the idea of label propagation, an iterative label propagation method is used to generate the initial population. The idea of label propagation is that in a complex network, each node should belong to the same community as most of its neighbors, which can be expressed as Eq. (3):

$\displaystyle l_{i}=\arg\max_{l}\sum\limits_{j\in\textit{adj}(i)}\delta(l_{j},l)$ (3)

where $\textit{adj}(i)$ denotes the neighbor node set of node $i$ . Therefore, the use of an iterative label propagation process specific operation. First, initialize tags for all nodes in the network. Second, the asynchronous updating method is adopted, and the label of each node in the network performs the label updating operation according to the Eq. (3) only once. It can be seen that it is very easy to reach a consensus by labeling the tight nodes when propagating the network through an iterative label propagation. The same nodes with the same label will form a community, so that a primitive population with a certain precision can be generated.

2.4 Cross operation

When using genetic algorithm to solve community detection problems, the cross-operation has some particularity. When cross-operation is performed, a group of closely related genes are crossed to the next generation instead of individual genes. The closely related genes represent a community. Therefore, you can’t use the traditional single point and multi-point cross method, but the use of single cross and multi-channel cross. The one-way crossover algorithm proposed by Tasgin et al. [8] in this paper is improved, which is called combined one-way interleaving. The aim of improvement is to make the new individuals after crossover retain the largest community structure characteristics of the intersection of two parents. The definition of the merged one-way crossover operation is defined as follows: Let $A$ and $B$ be any two individuals, $A$ as the source individual and $B$ as the target individual. $C^{B}(n)$ is the set of nodes in the community to which node $n$ belongs in individual $B$ , and $C^{A}(n)$ is the set of nodes in the same community with node $n$ in individual $A$ . $L$ is a set of initial community identifiers, $L(B)$ is a set of community identifiers in the individual $B$ , and $L^{B}(n)$ is a community identifier of the node $n$ in the individual $B$ . When making a cross operation, first select a node in the individual $A$ as the intersection position. Let node $n$ be selected as a cross location; then, all nodes included in $C^{B}(n)\cup C^{A}(n)$ in individual $B$ are cross-connected. Assign each node an existing label different from that of the individual $B$ , i.e. $L^{B}(m)\leftarrow L\forall m\in C^{B}(n)\cup C^{A}(n),L\in\{{L-L_{B}}\}$ . Therefore, the merger of single cross can retain the characteristics of the community structure of the previous generation, and the characteristics of the community structure become more prominent in the new individual.

2.5 Mutation operation

For complex network community identification problems, genetic algorithms often use random variation, lack of necessary information for mutation operations, and lack of effective control over the evolutionary direction of mutation operations. As a result, individual evolutionary speed is slow and the optimization effect is not good. For the above reasons, genetic algorithms are difficult to apply to community identification of large-scale networks. In this paper, aiming at the complex network community identification process, a local dynamical heuristic function is constructed to inspire the evolutionary direction of mutation operation and thus improve the individual evolution speed and recognition accuracy. The POGA algorithm uses the conductivity function $C(P)$ as the objective function. Conductivity is the average of the probability of each community separation, reflecting the ability of communities to communicate in complex networks and reflects a dynamic characteristic of complex networks. The smaller the conductivity, the more reasonable is the division of community structure.

Definition 1: Community $V_{i}$ internal $in\_\textit{vol}(V_{i})$ defined as: $in\_\textit{vol}(V_{i})=\sum\nolimits_{x\in V_{i},y\in V_{i}}A_{xy}$ .

Definition 2: The $\textit{vol}(V_{i})$ of Community $V_{i}$ is defined as: $\textit{vol}(V_{i})=\sum\nolimits_{x\in V_{i},y}A_{xy}$ .

Definition 3: $n$ is a node, $C$ is a community, $n\notin C$ , $n$ and $C$ in the node there is an edge. When the node $n$ community identifier changes from $l$ to $l^{\prime}$ , the internal degree $in\_\textit{vol}(C)$ of community $C$ does not change.

From Definition 3, we can see that the relationship between node community identity change and its neighbor community internal degree. In mutation operations, a node is separated from the current community that contains it and then merges into a nearer neighborhood to the node. Analyzing this process from the viewpoint of network dynamics can be considered as the process of passing the community identifier from the neighbor community to the current node. I.e., the community identifier of node $i$ changes from $L(V_{(i)})$ to $L(V_{(j)})$ , where $V_{(i)}$ represents the community containing node $i$ and $e_{ii}$ represents the community identifier of node $i$ . Conductivity changes in the division of complex online communities due to the spread of community identifiers. When a community identifier is transmitted from one community to an edge node of a neighboring community, the number of sides connecting the two communities is changes. Therefore, a function $h(C_{i},C_{j})$ was introduced to assess the communicability of community identifiers between two communities, which is defined as Eq. (4):

$\displaystyle h(C_{i},C_{j})=\frac{1}{2}\left(\frac{in\_\textit{vol}(C_{i})}{% \textit{vol}(C_{i})}+\frac{in\_\textit{vol}(C_{j})}{\textit{vol}(C_{j})}\right)$ (4)

where $C_{i}$ and $C_{j}$ are two adjacent communities. The $h(C_{i},C_{j})$ function is the average of the cohesion probabilities of two neighboring communities. When the community identity reaches a stable state, the community structure expressed by the community identifier is the community structure of the network.

Definition 4: When the number of communities is constant, the conductivity function $C(P)$ decreases monotonously with $h(V_{i},V_{j})$ , $P$ is a partition, and $V_{i}$ and $V_{j}$ are adjacent communities. Among them $V_{i}\in P$ , $V_{j}\in P$ , $P=\{{V_{1},V_{2},\ldots,V_{k}}\}$ .

From Definition 4, when $h(V_{i},V_{j})$ is used as the inspiration of community identifier, $C(P)$ will be smaller when the community identifier propagates in the direction of increasing $h(V_{i},V_{j})$ . In this case, the community structure obtained is more excellent. When a community identifier is broadcast on the web, it has the highest probability of being spread in the same community. Based on this, a local heuristic mutation strategy is proposed in this paper. Suppose that the $i$ -th gene of individual $I$ and node $i$ are selected to be mutated, and the adjacent community identifier set of node $i$ is $L_{n}(i)$ , only one community identifier needs to be selected in $L_{n}(i)$ , Considering the community identifiers of all neighbor nodes of node $i$ , $h(V_{i},V_{j})$ is used as the heuristic function to select the label with the largest $h$ value to propagate to the current node. That is expressed by the expression: $L_{i}\leftarrow\arg\max_{L}\{{h(V_{i},V_{L})L\in L_{n}(i)}\}$ , where $L_{i}$ is the community identifier of node $i$ .

The local heuristic mutation algorithm based on $h$ function is described in detail as follows.

Algorithm: Local Heuristic Variation Strategy.

Input: Individual to be mutated $R$ , Position of mutated gene Pos.

Output: Individual $R$ after mutation.

1. for $k=$ 1 to $n$ // $n$ is the number of nodes

2. List $=$ NeiLabel (pos, $R$ ) //Find nodes neighbor community identifier set

3. $m=$ length (List) //Calculate the queue length

4. for $i=$ 1 to $m$

5. $t=h(V_{\textit{pos}}$ , $V_{\textit{List}[i]})$ //Calculate $h$ function

6. if ( $t>\max{\_}h$ )

7. $\max{\_}h=t$

8. $L=$ Label ( $V_{\textit{List}[i]}$ )

9. Change the position of $R$ in pos to $L$

10. Return $R$

The time complexity of the LHVS algorithm is $O(Cn)$ , where $C$ is a constant and $n$ is the number of network nodes.

2.6 Partially optimized genetic algorithm framework

In order to preserve excellent individuals in genetic algorithms, a good population selection strategy is indispensable. Reference is made to the literature [13] for population selection. The basic idea is to select the $P$ individuals with the largest objective function from the population of the parent and the population resulting from the crossover and mutation as the population of the offspring. In this paper, the POGA algorithm is proposed based on the label propagation strategy, combined one-way cross strategy and local heuristic mutation strategy. Specific algorithm described in detail below.

Procedure POGA

Input: $N$ , $P$ // $N$ represents a complex network, $P$ is the size of the population

Output: C //The best online community structure

Begin

1. I $\leftarrow$ The initial population is generated by the label propagation method

2. tempMaxQ $\leftarrow$ Calculate the best Q value of I in the individual

3. parentMaxQ $\leftarrow$ 0

4. while tempMaxQ $>$ parentMaxQ

5. parentMaxQ $\leftarrow$ tempMaxQ

6. $I_{\textit{new}}\leftarrow$ On the individual I merge single-cross operation

7. $I_{\textit{new}}\leftarrow$ Perform local heuristic mutation on individuals in $I_{\textit{new}}$

8. tempMaxQ $\leftarrow$ The best Q value in population $I_{\textit{new}}$

9. $I_{s}\leftarrow I_{\textit{new}}\cup I$

10. I $\leftarrow$ Select the $P$ individuals with the best Q value from $I_{s}$

11. end while

12. C $\leftarrow$ Choose the best individual in I

End

In the POGA algorithm, the label propagation strategy generates a primitive population with a certain degree of precision to give full play to the superiority of the genetic algorithm. Adopt the combined one-way crossover strategy to avoid destroying the original excellent community structure and ensure the community structure to be more Excellent direction to optimize the use of local heuristic mutation strategy to ensure the accuracy of identifying communities, in order to achieve the overall optimization function of the algorithm.

3. Experimental results

3.1 Data set

The artificially generated benchmark networks in complex networks mainly include LFR benchmark, Newman benchmark and Ball-Karrer-Newman model. The real networks identified by the community are Karate, Dolphins, Polbooks and Football. Since the LFR benchmark [16] benchmark network is very similar to the statistical characteristics of the real network, this paper uses this benchmark network as the test data set of POGA. The related parameters are set as follows: the scale of the network is $N=$ 200, the average degree of nodes is $k=$ 15, the maximum degree of nodes is maxk $=$ 50, and the ratio of mixing (the ratio of the number of connections between nodes and community outside the total number of nodes). The value is 0.1 to 0.5. Among them, as the $\mu$ value increases, the community structure of the network is also becoming increasingly blurred, and it also poses a huge challenge to the community identification algorithm. Usually, two types of methods are used to evaluate the pros and cons of the algorithm. One is to perform recognition accuracy analysis in a real-world network of artificially generated reference networks of known community structures and a small number of known community structures. The other type is based on the actual structure of the network to comprehensively analyze the community structure identified by the algorithm.Here, the NMI [17] accuracy evaluation index is used to evaluate the recognition accuracy of each algorithm. If the NMI is equal to 1, the identified community structure is completely consistent with the real community structure; if the NMI is equal to 0, the identified community structure and real structure. It is totally different. An NMI value of 0 to 1 reflects the degree to which the detected community structure matches the real community structure in the artificial network. The Q function is used to analyze the closeness of each algorithm to identify the community structure.

Figure 1.

Comparison of NMI values for each algorithm.

3.2 Experimental results

In order to validate the validity of the proposed algorithm, the POGA algorithm is tested on datasets of datasets and is compared with those based on split GN algorithm, FN algorithm based on local modularity optimization, label-based LPA algorithm, Genetic algorithm GANET algorithm, in community identification accuracy evaluation index NMI and community internal connection tightness evaluation index Q aspects of comparative analysis. Because the genetic algorithm needs to set the relevant parameters when it is running, the POGA algorithm also needs to set the general parameters of the genetic algorithm. Based on the reference [18] and the analysis, this chapter gives the parameter setting of the POGA algorithm. The population size $P$ in the POGA algorithm is 100, the crossover rate $p_{c}$ is 70% and the variation rate $p_{m}$ is 30%.

Figure 2.

Comparison of Q values of various algorithms.

Figure 1 shows the comparison between POGA algorithm and other comparison algorithms in NMI. It is found that POGA algorithm can obtain higher NMI value and better community identification ability. Figure 2 shows the comparison of each algorithm in the module function Q. It can be seen that when the community results in the network are quite vague, but the module function obtained by the POGA algorithm is still very high, the POGA algorithm can identify the community Closely connected internal community structure. Through the analysis of each algorithm in LFR benchmark datum network, it can be seen that because of the randomness of GANET algorithm and LPA algorithm, the community recognition quality is affected. Therefore, the community structure is identified by these two algorithms not ideal. Although the GN algorithm has a higher quality of community structure identified in a network with a clearer community structure, its recognition performance is relatively weaker in a network with a fuzzy community structure. Although the FN algorithm obtains higher NMI and Q values in identifying communities, it is still lower than the POGA algorithm. Therefore, the proposed POGA algorithm has better NMI and Q than other comparison algorithms.

4. Conclusions

The complex network community identification method based on local optimization genetic algorithm proposed in this paper selects the modular Q function and the average conductivity function as the objective function, adopts the coding method of gene position adjacency, and uses the label propagation strategy to generate the original population with certain precision. Take advantage of the genetic algorithm to optimize the advantages; adopt the combined one-way crossover strategy to avoid destroying the original excellent community structure in the cross process and ensure the community structure to optimize in the better direction; use the local heuristic mutation strategy to ensure the identification of the community The accuracy rate, thus achieving the overall optimization function of the algorithm. Tested in the benchmark network, the experimental results show that the POGA algorithm is effective and feasible.

Footnotes

Acknowledgments

The study was supported by the Science and Technology Innovation Project of Shanxi Higher Education Institution (No. 201804011).

References

Girvan

and Newman

M.E.J.

, Community structure in social and biological networks, Proceedings of the National Academy of Science 9(12) (2012), 7821–7826.

Palla

Derenyi

and Farkas

, Uncovering the overlapping community structure of complex networks in nature and society, Nature 435(7043) (2005), 814–818.

Ahn

Y.Y.

Bagrow

J.P.

and Lehmann

, Link communities reveal multiscale complexity in networks, Nature 466(7307) (2010), 761–764.

Raghavan

U.N.

Albert

and Kumara

, Near linear time algorithm to detect community sturctures in large-scale networks, Physical Review E 76(3) (2007), 36–106.

Lancichinetti

Fortunato

and Kertesz

, Detecting the overlapping and hierarchical community structure in complex networks, New Journal of Physic 11(3) (2009), 632–636.

Blondel

V.D.

Guillaume

J.L.

and Lambiotte

, Fast unfolding of communities in large networks, Journal of Statistical Mechanics Theory and Experiment 10(3) (2008), 10–18.

Newman

M.E.J.

, Fast algotithm for detecting community structure in networks, Physical Review E 69(6) (2004), 66–133.

Tasgin

Herdagdelen

and Bingol

, Community detection in complex networks using genetic algorithms, Eprint Arxiv 7(11) (2007), 49–101.

Pizzuti

, A genetic algorithm for community detection in social networks, in: Proceeding of the 10th International Conference on Parallel Problem Solving from Nature, 36(302), 2008, pp. 1081–1090.

10.

Gong

M.G.

and Jiao

L.C.

, Memetic algorithm for community detection in networks, Physical Review E 84(5) (2011), 56–101.

11.

Shang

R.H.

Bai

and Jiao

L.C.

, Community detection based on modularity and an improved genetic algorithm, Statistical Mechanics and its Applications 392(5) (2013), 1215–1231.

12.

Shi

Yan

and Wang

, A genetic algorithm for detecting communities in large-scale complex networks, Advances in Complex Systems 13(1) (2010), 3–17.

13.

Mezura-Montes

and Coello

C.A.C.

, A simple multimember evolution strategy to solve constrained optimization problems, IEEE Transactions on Evolutionary Computation 9(1) (2005), 1–17.

14.

Newman

M.E.J.

, Scientific collaborationnetworks, Physical Review E 64(1) (2001), 16–132.

15.

Guelzim

Bottani

and Bourgine

, Topological and causal structure of the yeast transcriptional regulatory network, Nature Genetics 31(1) (2002), 60–63.

16.

Lancichinetti

Fortunato

and Radicchi

, Benchmark graphs for testing community detection algorithms, Physical Review E 78(4) (2008), 46–110.

17.

Danon

Diaz-Guilera

and Duch

, Comparing community structure identification, Journal of Statistical Mechanics 2005(9) (2005), 9–18.

18.

Tasgin

Herdagdelen

and Bingol

, Community detection in complex networks using genetic algorithms, Eprint Arxiv 7(11) (2007), 4–91.