A Variant of EAM to Uncover Community Structure in Complex Networks

Abstract—Environmental Adaptation Method (EAM) was developed to solve single objective  optimization  problems. After the first proposal, many variants have been developed to speed up the convergence rate and to maintain the diversity of the solutions. Among those variants, IEAM-RP works with real numbers. In this paper, a variant of IEAM-RP has been suggested by major changes in adaptation operator to improve the overall performance of the algorithm. In the proposed method, asig-nificant attention has been given to balance the exploration and exploitation of individuals in the population.The performance of the proposed algorithm is compared against 14 state-of-the-art algorithms using standard benchmark functions of COCO (COmparing Continuous Optimisers) framework. It has been observed that the proposed approach is very competitive with other algorithms and it either outperforms or performs similarly with other state-of-the-art algorithms. Further, to check the effectiveness of the  proposed approach, it has been applied to a real-world problem of community detection in complex networks. In this problem, modularity optimization is  taken into consideration as a fitness function. Again, the experimental results are very promising and competitive compared to other algorithms.

Keywords—Single Objective Optimization, Evolutionary Algo-rithms, Environmental Adaptation Method, Community Detection Problem.

1. INTRODUCTION

K. K. Mishra et al. [33] proposed Environmental Adaptation Method as an alternative of GA [25],  PSO  [27],  and  DE [53] for solving optimization problems. This algorithm uses the theory of adaptive learning given by Mark Baldwin [6]. EAM uses three operators: adaptation, alteration, and selection to find optimal solutions. These operators are based on the theory of adaptive learning. Adaptation operator was used to update the phenotypic structure of the solution in the search space on the basis of current environmental fitness and current solution’s fitness. Alteration operator used updated positions of solutions as an input and incorporate some extra diversity mechanism by inverting each bit of every solution with some probability. After alteration operator, offspring population is obtained. Finally, a selection operator is used to select the best solution from parent and offspring population for the next generation. Although, the convergence rate and diversity of solution was good enough and very efficient for multi-modal functions, but this algorithm was not efficient for uni-mode functions. Moreover, the best solution of the population of this algorithm did not have any contribution in search process of optimal points in the  search  space.  Therefore,  to  make the algorithm efficient for both multi-model and uni-mode functions, and to utilize the contribution of best solution in the search process, K. K. Mishra et al. [34], [35] proposed a variant of EAM named “Improved Environmental Adaptation Method (IEAM)”.

IEAM uses the same operators with some changes in adap- tation and divided the population into two parts. One part con- tains only one (best) solution and other parts contain remaining (N-1) solutions. Adaptation operator has a different mechanism to change the position of the solution of the both parts in the search space. The working of remaining two operators are same as they were in EAM. The use of the best solution in the search process in IEAM was found very useful and it performed well as compared to EAM. Both EAM and IEAM are binary coded due to which there were some computational overhead and limitations. These algorithms can not be used for real numbered problems. In order to reduce computational overhead and to work with real numbered problems, a new version of IEAM named “Improved Environmental Adaption Method with Real Parameter (IEAM-RP)” [52] was suggested in 2016. In IEAM-RP, the adaption operator has been modified to deal with real numbered problems. The performance of the algorithm was checked on 24 benchmark functions of COCO [19] framework. IEAM-RP has Improved the convergence rate and was able to find the optimal solutions in less number of function evaluations. Although the performance of IEAM-RP was very good in lower dimensions (2-D, 3-D, 5-D, and 10- D), it was not so efficient in higher dimensions optimization problems.

In this paper, a variant of IEAM-RP named “IEAM-RP1” is developed to improve the performance of the algorithm in the higher dimensions. In the proposed method two operators, adaptation, and selection have been used to find optimal solu- tions. For this purpose, the main concentration has been given to provide extra exploration capability to the solutions. Based on the current environmental fitness, the population is divided into two parts. The first part contains those solutions that have lower fitness values compared to the current environmental fitness and second part contains those solutions that have higher fitness values compared to the current environmental fitness. Here, current environmental fitness is the average fitness of the population. Different mechanisms have been applied to change the phenotypic structure of  solutions  of both parts. Special attention has been given to balance the exploration and exploitation capabilities of the operators.

In order to evaluate the performance of the proposed ap- proach, it is tested with the 24 benchmark functions of COCO [19] framework on 2-D, 3-D, 5-D, 10-D, and 20-D dimensions. The proposed algorithm is compared with 14 state-of-the-art algorithms. The comparative analysis of experimental results has shown that IEAM-RP1 is very competitive in 2-D, 3-D, and 5-D dimensions and is comparable to other algorithms in rest of the dimensions. Further, in order to check the effectiveness of the algorithm, IEAM-RP1 has been applied to the community detection problem of complex networks. In this problem, a complex network is divided into communities in such a way that the sum of the degrees  of  the  nodes within a community is maximum and between the communities is minimum. The proposed algorithm has been tested using standard networks and performance is compared against five state-of-the-art algorithms.

The remaining part of the paper is organized as follows: Section II has presented the background details and related work. The description  of  the  proposed  algorithm  is  given in Section III. The description of experimental setup and benchmark functions are given in Section IV and experimental results are described in Section V. The proposed algorithm is applied to a real-world problem of community detection in a complex network in section VI. In Section VII, experimental results of community detection problem are discussed and conclusion of the paper is given in Section VIII.

2. BACKGROUND DETAILS AND RELATED WORK

1. Environmental Adaptation Method (EAM)

K. K. Mishra et al. [33] proposed a  new  algorithm  to solve single objective optimization problems. This algorithm used the theory of adaptive learning in three steps. For each step, one operator has been designed to achieve the desired goal. These operators are adaptation, alteration, and selection. These operators use a binary representation of the solutions that represent the phenotypic structure of an individual. Adaptation operator uses randomly initialized population as an input and changes their phenotypic structure in the search space. Mathematically, adaptation operator is used to explore other regions in the given range as follows:

Pi+1 = (α(Pi)F(Pi)/Favg+ β)%(2L−1) (1)

WherePiand Pi+1 is the position vector and updated position vector of ithmember in the population. αand βare constant values that needs to be chosen according to optimization problems  taken  into  consideration.  F(Pi)  and  Favg   is  the

fitness value of Piand environmental fitness value of current population respectively. L is the total number of bits in an individual. After adaptation, the alteration operator is used to invert each bit of every individual with a certain probability in order to provide extra diversity. After the alteration operator, an offspring population of the same size is obtained. Selection operator is used to select the best individual from parent and offspring population. This process is  repeated until we get the optimal solution or a maximum number of iterations has been reached. EAM has following shortcomings:

• EAM works with binary encoding, we can not apply this algorithm in real numbered problems.
• In  higher  dimensions,  it  needs  a  greater  number  of bits  and  convergence  rate  decreases  which prone to stagnation.

• There is no contribution of best individual of the popula- tion in the search process in the subsequent generations.

2. Improved Environmental Adaptation Method (IEAM)

K. K. Mishra et. al. [34] proposed a new  version  of EAM to incorporate  the  contribution  of  the  best  member of the population in the search process, named “Improved Environmental Adaptation Method (IEAM)”. The adaptation operator of EAM was designed to explore the problem search space and alteration operator exploited new solutions around the solutions generated by adaptation operator. Since EAM uses little exploitation, it did not perform well with uni-model benchmark functions. In IEAM there are few changes in operators as well as the fine-tuning of parameters. In IEAM, some changes were made in the adaptation operator. The adaptation operator made the best member explore other good regions, while the remaining members exploit the problem search space. The best member uses its own fitness and environmental fitness to explore the other good regions in the problem search space as follows:

Pi+1 = [α∗(Pi)F(Xi)/Favg  + β]%2l (2)

WherePiis the position vector of the member that wants to update its structure, l is the number of bits, and α, βare the random numbers between 0 to 1. F(Xi) is the fitness value of ithmember and Favgis the current environmental fitness. Remaining members of the population are guided to update their position vector in the direction of the best member in the hope that optimal solution  exists  somewhere  close  to the structure of the best solution. Adaptation operator uses adaptation window of variable bandwidth and changes their structure as follows:

Pi+1 = [α∗(Pi)F(Xi)/Favg+ β∗[(Gb−Pi) + (Pb−Pi)]]%2l

(3)

where Gbis the  position  vector  of  the  best  member,  and Pbis the personal best position vector of the member that wants to update its position in the problem search space. The remaining two operators of IEAM, alteration, and selection, were used in the same way as they were used in EAM.

Although, IEAM performed well with uni-model, and multi-model  benchmark  functions  and  convergence  rate was improved as compared to EAM, still it had following shortcomings:

• The value of (Gb − Pi) + (Pb − Pi) is different for each member of the population which is known as bandwidth. Due to this, some members are not able to move properly in the search space and decreases the performance of the algorithm.

• Both EAM and IEAM are binary encoded, which results in high computational time.

3. Improved Environmental Adaptation Method With Real Parameter (IEAM-RP)

To overcome the above problems, a new version of IEAM was proposed  in 2016: Improved  Environmental Adaption Method with Real Parameter Encoding (IEAM-RP). IEAM-RP uses basic framework of IEAM. Unlike IEAM, IEAM-RP uses two operators: Adaption and Selection. Like other optimization algorithms, IEAM-RP also starts with a randomly initialized population in the search space. Here, adaption operator is used to create offspring population from parent population on the basis of adaption factor and mobility factor. The adaption factor is the ratio of individual fitness to current environmental fitness, whereas the mobility factor is the difference between the best and worst position vectors. The best and worst positions are the positions that correspond to the members having the best fitness and worst fitness respectively. The best member of the population uses adaption factor to change its structure, whereas, remaining members use mobility factor to attain the phenotypic structure of the best member. The offspring population produced by the adaption operator was diverse enough, so the alteration operator was excluded. Mathematically, the best member of the population changes its phenotypic structure as follows:

Pi+1 = Pi∗F(Xi)/Favg+ β (4)

Where βis a random number between 0 to 1. Piis the position vector of best member in the population that wants to update its phenotypic structure, F(Xi) is the fitness value of the best member and Favgis the current environmental fitness. Remaining members of the population try to attain the phenotypic structure of the best member by using mobility factor as follows:

Pi+1 = Pi+ β∗(best_position−worst_position)   (5)

Here Piis the position vector of ithmember, and best_position-worst_position is the fixed bandwidth that is used by non-best members to move in the problem search space. The value of best_position-worst_position is called as mobility factor, it is fixed for all non-best members in a particular generation that makes the members move properly in the problem search space.

The performance of IEAM-RP was compared with other nature-inspired optimization algorithms on a total of 24 bench- mark functions of COCO [19] framework on 2-D, 3-D, 5-D, and 10-D dimensions. It was found that IEAM-RP performs better than others state-of-the-art algorithms in many ways. IEAM-RP has removed all the limitations of IEAM and performed well in terms of convergence rate and diversity. The main problem of IEAM-RP was it did not perform well in higher dimensions, like, 20-D, and 40-D. This is due to the fact that IEAM-RP was unable to maintain the balance between exploration and exploitation in an efficient way.

4. Evolutionary Strategy (ES)

Ingo Rechenberg [47] proposed ES algorithm for optimiza- tion in 1989 by using the idea of adaptation and evolution. In this algorithm, one parent is selected to generate an offspring in one generation. The offspring population is produced by using a mutation operator that remains the same in all gener- ations. The first version of this algorithm was known as two- membered ES. After the first proposal, a number of updated versions of this algorithm have been developed. Later version of the algorithm is known as (µ+ λ) ES. In this version, µparents are used to create λmutated offspring. The approach of this version of the ES algorithm is similar to real parameter genetic algorithm [24], [60], [18]. The evolutionary process in ES was enhanced by using the distribution model of the population resulting in a new algorithm called Covariance Matrix Adaptation Evolution Strategy (CMAES) [21]. The distribution model helps CMAES to learn linkage of involved variables. CMAES starts with the initialization of mean vector

(m∈Rn) and covariance matrix (cov) where n represents the dimension of the problem.

mj  = rand(Lj,Uj), such that Lj  <mj <Uj  j= 1,2,,n, cov= σ2C,

where C∈Rn×nand σis the step size. The initial value of C is set to an identity matrix. In each iteration, λnew solutions

are generated using multivariate normal distribution N(m, cov). The weighted sum of the best µ solutions is used to update m, σ, and C. The general accepted values of µand λare [λ/4] and 4 + [3ln(n)] respectively [22]. This process is repeated until the terminating criterion.

5. Differential Evolution (DE)

Storn and Price [54] proposed one of the most powerful stochastic real-parameter optimization algorithms in current use. DE is population-based optimization algorithm and oper- ates the similar computational steps as employed by a standard evolutionary algorithm (EA) to find optimal solution. Since DE was developed in 1995, it has drawn the attention of many researchers all over the world resulting in a lot of variants of the basic algorithm with improved performance. It uses three operators (mutation, crossover and selection). The working of each operator is described as follows:

Mutation: For each target vector xi,G, i = 1, 2, 3, … , NP, a mutant vector is generated according to

vi,G+1 = xr1 ,G+ F∗(xr2 ,G−xr3 ,G)

with random  indexes  r1,  r2, r3 ∈{1,2,…,NP}, mutually different and F ∈[0,2]. Further, i, r1, r2, and r3 are different so that NP ≥4. Larger values for F result in higher diversity in  the  generated  population  and  lower  values  cause  faster

convergence [46].

Crossover: In order to improve the diversity, crossover is introduced. It defines the following trial vector:

Ui,G+1     =    (U1i,G+1,U2i,G+1,U3i,G+1,…,UDi,G+1)   is

formed, where

Uji,G+1 if randj(0,1) ≤Cr

randomly initialized potential solutions (particles) in the search space. Each point in the search space associates some objective function value. In order to find the optimal solution, particles fly in the search space with some velocity and change their location using current velocity. Each particle moves in the search space using the following velocity:

V(t+1) = w×V(t)+c1×r1(pbest−X(t))+c2×r2(gbest−X(t))

(6)

On the basis of velocity, particles change their location in the search space as follows:

U_ji, G+1 =

xji,Gotherwise

X(t+ 1) = X(t) + V(t+ 1) (7)

j = 1, 2, … , D (D = problem dimension)

Selection: To decide whether or not it should become a member of generation G + 1, the trial vector Ui,G+1 is compared to the target vector xi,G. If vector Ui,G+1 yields a smaller cost function value than xi,G, then xi,G+1 is set to Ui,G+1, otherwise, the old value xi,G  is retained.

The task of any optimization is to  search  for  the parameter  vector  X∗ that  minimizes  an  objective  function

Where

• pbest and gbest are the personal best and global best positions, respectively.
• X(t) is the current position of the particle.
• V(t) is the current velocity of the particle.
• w is inertia weight.

c1 and c2 are cognitive and social behavioural constants.

f(X)(f: RD→R), i.e. f(X∗) <f(X) for all X, where

RD  is a non-empty large finite set serving as the domain of the search.

This algorithm uses a combination  of  mutation,  crossover, and selection operators to target optimal solutions. Several mutation schemes to refine classical DE were compared by Mezura-Montes et al. [32] by using eight different DE variants on a set of 13 benchmark problems. Liu et al. [30] proposed Fuzzy Adaptive Differential Algorithm driven by the fuzzy logic controller that is adaptive during each generation of DE. Qin et al. [44] proposed Self-Adaptive Differential Evolution (SADE) in which both trial vector generation scheme and control parameters Cr and F are gradually self-adapted through learning from their previous understanding. In order to tune the random parameters, other variants [39], [1], [9] were also proposed .

Zhang et al. [61] proposed JADE as an adaptive differential evolution to improve the optimization performance by implementing a new mutation strategy with the optional external archive. JADE uses a neighborhood-based mutation strategy to  enhance the  performance of  DE.  In JADE,  the maximum size of external archive A is bound to population size. Multiple best solutions are used to balance the exploration and exploitation. The performance of JADE was evaluated on a set of 20 benchmark functions. It was found that for higher dimensional problems, JADE with an external archive shows promising results.

6. Particle Swarm Optimization

Particle swarm optimization (PSO) is a population-based stochastic optimization technique developed by Dr. Eberhart and Dr. Kennedy [27] in 1995, inspired by social behavior of bird flocking or fish schooling. PSO processes a set of

• r1 and r2 are random numbers generated between [0,1].

Unlike, GA, and DE, PSO do not have any mutation, crossover or selection operators. After the first proposal of PSO, many variants have been developed to  improve  its  performance and to solve real-world problems. At the present time, PSO has been used for training [12] in neural network, controller parameter setting [58], multiobjective optimization [11], and so on.

3.      DESCRIPTION OF THE PROPOSED ALGORITHM

In this paper, a variant of IEAM-RP is suggested to improve its performance on the higher dimension of a given problem. In the proposed algorithm, enough attention has been given to improve the operators so that the algorithm can perform better in higher dimensional problems. Any optimization algorithm tries  to  find  optimal  solutions using  three  steps, which are:  an exploration of  search space to identify new good solutions, exploitation around the good solutions, and selection of  good  solutions.  Selection  of  good  solutions  is essential to identify those locations in the search space where the probability of getting optimal solutions is very high. After that, these locations are exploited to check whether a global optimum solution lies in these locations or not. If an optimal solution is not found then the search space is explored so that other good locations can be found. These steps are repeated until the global optimum solution is identified or maximum iteration has been achieved. In the proposed approach, above three steps are achieved using two operators (adaptation and selection). The detailed description of both operators  have been given below.

1. Adaptation Operator

The main purpose of this operator is to create offspring population from the parent or intermediate population. This operator divides the population into two parts. One part contains those solutions that have smaller fitness value compared  to  current  environmental  fitness  and   another part contains those solutions that have higher fitness value compared to current environmental fitness. The division of the population into  two  parts  is  to  measure  the  deviation of the  solutions from  the current  environmental fitness.  In the case  of  minimization,  the  solutions  having  the  smaller fitness compared to current environmental fitness are better as compared to the solutions that have higher fitness to the current environmental fitness. In the proposed algorithm, different strategies have been adopted in the two parts of solutions to generate offspring population. The environmental fitness Favgis the average fitness of the population and represented as follows:

N

Favg= ) Fi/N (8)

i=1

Where N is the initial population size, Fiis the fitness value of ithmember of the population. Each member having the higher fitness value compared to the current environmental fitness changes its location as follows:

PH+1 = permute(PH) (9)

where PHis the position vectors of the members that want to change its genome structure. Permute (PH) is one of the possible combination of respective solutions. To understand this, let us consider a position vector of  PH  =  {1.2,  3.7, 2.4}. For this position vector, a total 6 possibilities are there, which are: {1.2, 3.7, 2.4}{1.2, 2.4, 3.7}{3.7, 1.2, 2.4}{3.7,

2.4, 1.2}{2.4, 1.2, 3.7}{2.4, 3.7, 1.2}. Permute(PH) will return

2. Selection Operator

This operator is used to select best N (initial population size) individuals from parent and  offspring  population  for the next generation. For doing this, it combines parent and offspring population and selects top N individuals on the basis of fitness values. This process continues until we get the optimal solutions or a maximum number of iterations has been reached.

Algorithm1IEAM-RP1

1:  Set initial values of parameters

2:  N = 100×DIM 1>DIM is the problem dimension

3:  Initialize each solution of population randomly

4:  repeat

5: for g=1 to MaxGen do

6: Evaluate fitness value of each solution

7: Generate offspring population using Adaptation

8: Update population using Selection

9: endfor

10:  untilstopping criteria is not met or optimal solution is not

   found                                   

Algorithm2Adaptation

1:  Compute average fitness of current population 1>use eq. 8

2:  On the basis of Favg, divide population into two parts

3:  if IF≥Favg 1>IF= individual fitness

4:  Apply  random  exploration  using  eqn  9  to  find  other

promising solutions

5:  else

6:  Apply exploitation using eqn 10 around the good solutions

7:  end if

  8:  END                                   

one possible combination from all 6 combinations. This is a simple and efficient way to find an offspring from a solution. Hence, in order to get permute(PH), we need to shuffle the position vector of PH. Shuffling of position vector and then choosing one possible combination provides extra exploratory capability to the solutions, which in turn improves the overall performance of the algorithm.

The solutions that have smaller fitness value compared to the current environmental fitness value, change their location in the problem search space as follows:

PL+1 = PL+ β×(best_position−worst_position) (10)

Here, in equation 10, best_position and  worst_position are the position vectors of solutions that have least fitness and highest fitness values respectively. βis a random number from 0 to 1. PLis position vectors of solutions that have smaller fitness values compared to current environmental fitness. PL+1 is updated position vectors of PL. The best_position – worst_position provides a fixed bandwidth to the members of the population so that they can properly evolve in the problem search space. Now PH+1 and PL+1 are combined which is the offspring population created by adaptation operator.

Algorithm3 Selection

1:  Combine parents and offspring population

2:  Select  N  distinct  best  individuals  from  the  combined population

4.     DESCRIPTION OF EXPERIMENTAL SETUP AND BENCHMARK FUNCTIONS

We evaluated the performance of IEAM-RP1 over 24 Black- Box Optimization Benchmarking (BBOB)functions [20] using COmparing Continuous Optimizers (COCO) framework [19], [14]. The results generated by IEAM-RP1 are compared with the other existing state-of-the-art algorithms. To analyze the performance of different algorithms, both uni-modal and multi- modal functions have been taken.

1. Experimental Setup

The search domain for all functions is used as [−5,5]D. In the experiments, all functions are tested for D = 2, 3, 5, 10,  and  20  search  space  dimensionalities.  If  foptimal  is  an optimal fitness value defined for each benchmark function individually and ∆fis the required precision then ftarget= foptimal+ ∆fis the target value of function. The value of

∆fis taken as 10−8 in COCO framework in computations. The number of trial runs for each function per dimension is

15. Maximum allowed function evaluations (FEs) for each trial are calculated using eqn 11.

Maximum_FEs= 1000×Population_Size×Dimension

2 (11)

where

Population_Size= 100 ×Dimension (12)

All experiments are performed using MATLAB 2017a in Windows7 on a desktop with Core-i5 @2.80GHz processor and 4GB RAM.

2. Benchmark Functions

The Black-Box Optimization Benchmarking (BBOB) provides 24 noiseless real-parameter single-objective benchmark functions. These functions are further classified

into five groups, including separable functions (f1 −f5), functions with low or moderate conditioning (f6 −f9), uni-modal functions with high conditioning (f10 −f15), multi-modal              functions  with   adequate   global   structure (f16 −f19), and multi-modal functions with weak global structure (f20 −f24) as listed in Table I. All benchmark functions are scalable with the dimension (D). Most functions

have no specific value of their optimal solution. All functions have an artificially chosen optimal function value [20].

Table I: BBOB Benchmark Functions