# A New Multiobjective Evolutionary Algorithm for Community Detection in Dynamic Complex Networks

Authors: Guoqiang Chen; Yuping Wang; Jingxuan Wei
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Community detection in dynamic networks is an important research topic and has received an enormous amount of attention in recent years. Modularity is selected as a measure to quantify the quality of the community partition in previous detection methods. But, the modularity has been exposed to resolution limits. In this paper, we propose a novel multiobjective evolutionary algorithm for dynamic networks community detection based on the framework of nondominated sorting genetic algorithm. Modularity density which can address the limitations of modularity function is adopted to measure the snapshot cost, and normalized mutual information is selected to measure temporal cost, respectively. The characteristics knowledge of the problem is used in designing the genetic operators. Furthermore, a local search operator was designed, which can improve the effectiveness and efficiency of community detection. Experimental studies based on synthetic datasets show that the proposed algorithm can obtain better performance than the compared algorithms.


---

## Body

## 1. Introduction

Many real-world complex systems take the form of networks. Acquaintance networks, Internet, power grids, and neural networks are some examples. Networks could be modeled as graphs, where the individual objects are represented by nodes and the interactions among these objects are represented by edges. Community structure, that is, the vertices in networks are often found to cluster into tightly knit groups with a high density of within-group edges and a lower density of between-group edges [1], is one important property of these networks. The detection of such a community structure has great practical meaning.Traditional analysis of community detection treats the network as a static graph, where the static graph is either derived from aggregation of data over all time or taken as a snapshot of data at a particular time. Researchers have successively proposed many effective detection methods of static network. In fact, dynamic networks capture the modifications of interconnections over time, which allow tracing the changes of network structure at different time steps. Community detection in dynamic networks is attracting increasing interest.Recently, a framework called temporal smoothness is applied to solve community detection in dynamic networks. In this framework, it is not desirable that the significant changes of clusters structure in a short time period [2]. In order to smooth each community over time, it needs to trade off two competing objectives of snapshot quality, which is that the clustering should reflect as accurately as possible the data coming during the current time step, and temporal cost, which is that each clustering should not shift dramatically from one time step to the successive one. Using this idea, Folino and Pizzuti proposed a multiobjective approach named DYN-MOGA to discover communities in dynamic networks by employing genetic algorithms [3]. In DYN-MOGA, Community Score (CS) and Normalized Mutual Information (NMI) were selected as two objectives to be optimized simultaneously. At the end of each timestamp, DYN-MOGAreturns a set of solutions contained in the Pareto front. They adopted modularity as a criterion to automatically select one solution with respect to another. Following this work, Gong et al. introduced a novel multiobjective immune algorithm with local search to solve the community detection problem in dynamic networks [4]. They adopted Modularity and NMI as two objectives to optimize.But, the modularity has been exposed to resolution limits [5–7]. Fortunato and Barthélemy [5] have recently found that modularity optimization may fail to identify modules smaller than a scale which depends on the total size of the network and on the degree of interconnectedness of the modules, even in cases where modules are unambiguously defined. To overcome the limitations of modularity function, a new measure, named by modularity density, was presented in [8].In this paper, we present a novel multiobjective algorithm, named DNCD-MOEA, to detect community in dynamic networks. The algorithm adopts modularity density as one objective to measure how well the clustering found represents the data at the current time, and it adopts NMI as another objective to measure the distance between two clusterings at consecutive time steps. Based on the problem-specific knowledge, the new genetic operators are designed to solve the proposed model. In order to improve the quality of the solutions, a local search operator is designed.The outline of the paper is as follows. Section2 introduces related background. In Section 3 we present our algorithm and explain its steps. Experimental studies are presented in Section 4. Section 5 concludes this paper.


## 2. Background

### 2.1. Notation

We define a static networkNt at time t as Nt=(Vt,Et), where Vt is a set of objects, each vi∈Vt denotes a node, and Et is a set of links, each vij∈Et represents an edge that connects two nodes vi and vj at time t. The dynamic network N can be defined as a sequence of static networks Nt=(Vt,Et); that is, N={N1,N2,…,NT}, where each Nt represents the snapshot of nodes and edges at time t. Let Ct={Ct1,Ct2,…,Ctk} be the set of all communities in network Nt at time t where Cti denotes the ith community at time t.


### 2.2. Evolutionary Clustering

Chakrabarti et al. first introduced evolutionary clustering in [2] as the problem of clustering data coming at different time steps to produce a sequence of clustering. We adopt this framework to analyze communities and their evolutions by use of the community structure at time t-1 to regularize the community structure at time t. At each time step, two conflicting criteria must be simultaneously optimized to produce a new clustering. The first criterion is that the clustering at any point in time should remain faithful to the current data as much as possible. The second is that the clustering should not shift dramatically from one time step to the next. A framework called temporal smoothness is defined in order to satisfy the second property to smooth out each community over time. This framework assumes that the dramatic change of clustering in a short time is not desirable; thus the cost function consisting of two parts is defined as follows:
(1)cost=α×SC+(1-α)×TC,
where SC denotes snapshot cost which measures how well a community structure Ct represents the data at time t and TC denotes temporal cost which measures how similar the community structure Ct is with the previous community structure Ct-1. The input parameter α is used by the user to control the level of emphasis on each part of the two objectives. When α=1, it returns the clustering without temporal smoothing. When α=0, however, the framework produces the same clustering structure with the previous time step, that is, Ct=Ct-1. Thus it can control the preference degree of each subcost by changing the value of parameter α between 0 and 1.


## 2.1. Notation

We define a static networkNt at time t as Nt=(Vt,Et), where Vt is a set of objects, each vi∈Vt denotes a node, and Et is a set of links, each vij∈Et represents an edge that connects two nodes vi and vj at time t. The dynamic network N can be defined as a sequence of static networks Nt=(Vt,Et); that is, N={N1,N2,…,NT}, where each Nt represents the snapshot of nodes and edges at time t. Let Ct={Ct1,Ct2,…,Ctk} be the set of all communities in network Nt at time t where Cti denotes the ith community at time t.


## 2.2. Evolutionary Clustering

Chakrabarti et al. first introduced evolutionary clustering in [2] as the problem of clustering data coming at different time steps to produce a sequence of clustering. We adopt this framework to analyze communities and their evolutions by use of the community structure at time t-1 to regularize the community structure at time t. At each time step, two conflicting criteria must be simultaneously optimized to produce a new clustering. The first criterion is that the clustering at any point in time should remain faithful to the current data as much as possible. The second is that the clustering should not shift dramatically from one time step to the next. A framework called temporal smoothness is defined in order to satisfy the second property to smooth out each community over time. This framework assumes that the dramatic change of clustering in a short time is not desirable; thus the cost function consisting of two parts is defined as follows:
(1)cost=α×SC+(1-α)×TC,
where SC denotes snapshot cost which measures how well a community structure Ct represents the data at time t and TC denotes temporal cost which measures how similar the community structure Ct is with the previous community structure Ct-1. The input parameter α is used by the user to control the level of emphasis on each part of the two objectives. When α=1, it returns the clustering without temporal smoothing. When α=0, however, the framework produces the same clustering structure with the previous time step, that is, Ct=Ct-1. Thus it can control the preference degree of each subcost by changing the value of parameter α between 0 and 1.


## 3. Proposed Algorithm

As [3], we adopt the same multiobjective representative frameworks for dynamic community detection which treat snapshot cost SC and temporal cost TC as two competing objectives. Modularity density and NMI are employed to denote snapshot cost SC and temporal cost TC, respectively. The main advantage of this method is that it does not need to fix the control parameter α.The proposed algorithm DNCD-MOEA is realized under the framework of NSGA-II [9]. The details of objective functions and representation method are given as follows.


### 3.1. Objective Functions

To denote snapshot costSC, we adopt modularity density as an objective function to measure the quality of the community. The modularity density is defined as follows:
(2)D=∑i=1md(Gi)=∑i=1mL(Vi,Vi)-L(Vi,Vi¯)|Vi|.In detail, given an undirected networkG=(V,E) consisting of the vertex set V={v1,v2,…,vn} (n is the cardinality of V) and the edge set E. Where {Vc}c=1m is a partition of the vertex set V into m groups, Vc¯ is the complement of Vc with respect to V, L(Vc,Vc¯)=∑i∈Vc,j∈Vc¯Aij (A=(Aij) is the adjacent matrix of G), and |Vc| is the cardinality of Vc.Normalized Mutual Information (NMI) was employed to denote the second objective function, that is, temporal cost. Danon et al. have proved NMI to be a reliable similarity measure [10].LetA={A1,A2,…,Am} and B={B1,B2,…,Bn} denote two partitions of a network in communities, and C denotes the confusion matrix whose element Cij is the number of nodes of the community Ai∈A that are also in the community Bj∈B. The NMI(A,B) is defined as follows:
(3)NMI(A,B)=-2∑i=1m∑j=1nCijlog(CijN/Ci.C.j)∑i=1mCi.log(Ci./N)+∑j=1nC.jlog(C.j/N),
where Ci.(C.j) is the sum of the elements of C in row i (column j) and N is the number of nodes. If A=B, set NMI(A,B)=1. If A and B are completely different, set NMI(A,B)=0. In this paper, the two objectives of D(Ct) and NMI(Ct-1,Ct) will be maximized simultaneously.


### 3.2. Solution Selection

In fact, the proposed algorithm DNCD-MOEA returns Pareto front at the end of each timestamp, which contains a set of solutions. Each of these solutions corresponds to a different tradeoff between the two objectives and thus to a diverse partitioning of the network consisting of various number of clusters. It needs to establish a criterion to automatically select which solution denotes the optimal partitioning of the current network at each time step. Community score introduced in [11] has been proved to be very effective in detecting communities. In this paper, we adopt community score as a criterion to select, among the solutions found, the solution having the highest value of community score. It is defined as follows.LetCt={Ct1,Ct2,…,Ctk} be the set of all communities in network Nt at time t where Cti denotes the ith community at time t. The community score of Ct is defined as
(4)CS(Ct)=∑i=1kscore(Cti),
where
(5)score(Cti)=∑i∈Ctiμi|Cti|×∑i,j∈CtiAij.
The parameter μi=(1/|Cti|)∑j∈CtiAij denotes the fraction of edges which connect each node i of Cti to the nodes in the same community Cti. The community score takes into account both the fraction of interconnections among the nodes and the number of interconnections contained in the module Cti. It gives a global measure of the network division in communities by summing up the local score of each module found. Thus the larger community score indicates that the community structure is stronger. So, we select the maximum community score value in the set of solutions as the best solution.


### 3.3. Genetic Representation

The locus-based adjacency representation proposed by Park and Song [12] is used in our community detection algorithm, similar to [11].As a graphG=(V,E) has N vertices, an arbitrary individual of the population consists of N genes, which can be represented by a number of strings as follows:
(6)(g1,g2,…,gN),gi∈{1,2,…,N}(i=1,2,…,N),
where gi=j denotes that there exists a link between the nodes i and j. This means that thenodes i and j will be in the same community. It is necessary to identify all of the components of the corresponding graph in the decoding step. The nodes participating to the same component are assigned to the same community. Adopting this representation, the main advantage is that the decoding step can be done in linear time and it has been verified as an effective encoding schema for community detection as shown in [3]. Additionally, the number k of clusters is automatically determined by the number of components contained in an individual and is also determined by the decoding step [11].An example of the encoded genotype and corresponding network is shown in Figure1. As shown in Figure 1(a), the supposed network consists of seven nodes numbered from 1 to 7. It is obvious that the network can be partitioned into two groups visualized by different shape. A possible genotype as shown in Figure 1(b), which corresponds to the optimal solution, is translated in the graph structure given in Figure 1(c). Each connected component provides a grouping of nodes that corresponds to the partitioning of the network in Figure 1(a).(a) A graph modeled as a network, (b) the representation of a possible genotype, and (c) the graph structure of the genotype to be decoded.
(a)
(b)
(c)


### 3.4. Initialization

If an individual is created randomly, it may not be a feasible solution. In fact, a randomly generated individual could contain an allele valuej in the ith position, but no connection exists between the two nodes i and j; that is, the edge (i,j) is not present. In order to overcome this limitation, we should check whether the individual is safe after an individual is created. When the individual is not safe, that is, a gene i contains a value j, but link (i,j) does not exist, it needs to repair to ensure whether the individual is safe or not. Safe individuals improve the convergence of the method because the space of the possible solutions is restricted.


### 3.5. Crossover and Mutation

As in [3], we use uniform crossover which can guarantee the maintenance of the effective connections of the nodes in the network in the child individual. Given two arbitrary safe parent individuals and that a random binary vector is created, the genes are selected from the first parent if the vector element is 1, and the genes are selected from the second parent if the vector element is 0. Then the genes are combined to form a child. Because of the biased initialization, the child created from the two safe parents is safe also. In the child, if a position i contains a value j, then the edge (i,j) exists. The uniform crossover is shown in Figure 2.Figure 2
Illustration of the uniform crossover.Crossover operator is regarded as a macroscopic operation on individuals, while the mutation operator is regarded as a microcosmic operation on individuals. The mutation operator that randomly changes the valuej of the ith gene causes a useless exploration of the search space. In order to guarantee the mutated child is safe as the crossover operation, the possible value of an allele after mutating is restricted to be one of the replaced gene’s neighbors.


### 3.6. The Pseudocode of the Proposed Algorithm

The pseudocode of our DNCD-MOEA algorithm is described in Algorithm1.Algorithm 1
Program  DNCD-MOEA
Input:  The number T of time steps, the sequence of
dynamic networkN={N1,N2,…,NT}
Output:  The sequence of community structure detected in
the dynamic networkC={C1,C2,…,CT}
Begin
Step1: Set t=1. Generate the initial community structure
C1={C11,C12,…,C1k} of the network N1using
GA-Net algorithm. Sett=t+1.
Step2: If t>T, return the sequence of community
structureC={C1,C2,…,CT} as the output,
algorithm stops; Else, go to Step3.
Step3: Set s=1. Randomly generate individuals whose
length equals the nodes numbernt=|Vt| of
networkNt as an initial population Ps;
Step4: While termination condition is not satisfied do
Step4.1: Create a new population Qs of offspring by
applying the variation operators on
populationPs;
Step4.2: Combine the parents Ps and offspring Qs into a
new poolRs and;
Step4.3: Decode each individual I of the population Rs
to generate the partitioning
Ct={Ct1,Ct2,…,CtktI} of the network Nt in
kt connected components;
Step4.4: Evaluate the two fitness values of the translated
individuals;
Step4.5: Partition Rs into fronts, assign a rank to each
individual and sort them according to
nondomination rank;
Step4.6: Select individuals based on rank and crowding
length to comprise new populationPs+1;
Step4.7: Select the dominant individuals Ls in Ps+1,
Step4.8: Perform the local search algorithm on the
selected individuals inLs to generate the new
dominant populationLs′. Update the dominant
populationLs with Ls′ in Ps+1.
Step4.9: s=s+1
End while
Step5: Select the individual which has the maximum
Community Score on the Pareto front. Decode the
selected individual to get the community structure
Ct={Ct1,Ct2,…,Ctkt} of the network Nt.
Step6: Set t=t+1, go to Step 2.
End


### 3.7. Local Search Strategy

Local search is proved to be an effective algorithm. The mutation operator is regarded as a microcosmic operation on individuals and can achieve its local search function by moving single nodes between communities. Inspired by this idea, we adopt mutation operator in our local search algorithm.In local search algorithm, it needs to convert multiple objectives into a single objective function. In our study, we select a weighted objective as follows [3]:
(7)G(x)=∑i=12rigi(x),
where gi(x) is the objective function which is described in (2) and (3), respectively, and ri is the nonnegative weights for the two objectives. The weights are calculated in a special way as follows:
(8)ri=(gi(x)-gimin)/(gimax-gimin)∑j=12(gj(x)-gjmin)/(gjmax-gjmin),
where gimax or gimin is the maximum or minimum value of each objective function gi(x) in the obtained dominant population and ∑i=12ri=1. In Algorithm 2, the detailed pseudocode of the local search algorithm is given.Algorithm 2
Program: Local Search Algorithm:
Input: Given a dominant population Ls before local search
at thesth generation, the size M of dominant population Ls,
the numberN of local search.
Output: the improved population Ls′ in the sth generation.
Begin
(
1
)   for i=1 to M
(
2
)      j=1; find=false
(
3
)      while j<N and not find
(
4
)     Create a new individual applying the mutation
operator on theith individual of dominant
populationLs;
(
5
)     Calculate the objective function value of the new
individual according to formula (7). If its value is
greater than that before local search, add the new
individual toLs′, find=true;
(
6
)     j=j+1;
(
7
)      end while
(
8
)      if not find, adds the current individual to Ls′
(
9
)   end for
END


### 3.8. Computational Complexity

The computational complexity of DNCD-MOEA algorithm is investigated in this subsection. The DNCD-MOEA algorithm contains two major components: the main program based on the NSGA-II framework and the subprogram of local search operation. The time consuming of the main program mainly consists of three parts: generating nondominated sorting, calculating crowding distance assignment, and constructing partially ordered set. LetS denote the size of population and r denote the number of objects. The computational complexity of the three parts is O(r(2S)2), O(r(2S)log(2S)), and O(2Slog(2S)), respectively. So the total time complexity of the main programming is O(rS2). The local search operation mainly contains two loops and its computational complexity is O(MN). So, the total computational complexity of DNCD-MOEA algorithm is O(rS2)+O(MN). Because M<S, r=2, and in practice N<S, the time complexity can be simplified to O(S2).


## 3.1. Objective Functions

To denote snapshot costSC, we adopt modularity density as an objective function to measure the quality of the community. The modularity density is defined as follows:
(2)D=∑i=1md(Gi)=∑i=1mL(Vi,Vi)-L(Vi,Vi¯)|Vi|.In detail, given an undirected networkG=(V,E) consisting of the vertex set V={v1,v2,…,vn} (n is the cardinality of V) and the edge set E. Where {Vc}c=1m is a partition of the vertex set V into m groups, Vc¯ is the complement of Vc with respect to V, L(Vc,Vc¯)=∑i∈Vc,j∈Vc¯Aij (A=(Aij) is the adjacent matrix of G), and |Vc| is the cardinality of Vc.Normalized Mutual Information (NMI) was employed to denote the second objective function, that is, temporal cost. Danon et al. have proved NMI to be a reliable similarity measure [10].LetA={A1,A2,…,Am} and B={B1,B2,…,Bn} denote two partitions of a network in communities, and C denotes the confusion matrix whose element Cij is the number of nodes of the community Ai∈A that are also in the community Bj∈B. The NMI(A,B) is defined as follows:
(3)NMI(A,B)=-2∑i=1m∑j=1nCijlog(CijN/Ci.C.j)∑i=1mCi.log(Ci./N)+∑j=1nC.jlog(C.j/N),
where Ci.(C.j) is the sum of the elements of C in row i (column j) and N is the number of nodes. If A=B, set NMI(A,B)=1. If A and B are completely different, set NMI(A,B)=0. In this paper, the two objectives of D(Ct) and NMI(Ct-1,Ct) will be maximized simultaneously.


## 3.2. Solution Selection

In fact, the proposed algorithm DNCD-MOEA returns Pareto front at the end of each timestamp, which contains a set of solutions. Each of these solutions corresponds to a different tradeoff between the two objectives and thus to a diverse partitioning of the network consisting of various number of clusters. It needs to establish a criterion to automatically select which solution denotes the optimal partitioning of the current network at each time step. Community score introduced in [11] has been proved to be very effective in detecting communities. In this paper, we adopt community score as a criterion to select, among the solutions found, the solution having the highest value of community score. It is defined as follows.LetCt={Ct1,Ct2,…,Ctk} be the set of all communities in network Nt at time t where Cti denotes the ith community at time t. The community score of Ct is defined as
(4)CS(Ct)=∑i=1kscore(Cti),
where
(5)score(Cti)=∑i∈Ctiμi|Cti|×∑i,j∈CtiAij.
The parameter μi=(1/|Cti|)∑j∈CtiAij denotes the fraction of edges which connect each node i of Cti to the nodes in the same community Cti. The community score takes into account both the fraction of interconnections among the nodes and the number of interconnections contained in the module Cti. It gives a global measure of the network division in communities by summing up the local score of each module found. Thus the larger community score indicates that the community structure is stronger. So, we select the maximum community score value in the set of solutions as the best solution.


## 3.3. Genetic Representation

The locus-based adjacency representation proposed by Park and Song [12] is used in our community detection algorithm, similar to [11].As a graphG=(V,E) has N vertices, an arbitrary individual of the population consists of N genes, which can be represented by a number of strings as follows:
(6)(g1,g2,…,gN),gi∈{1,2,…,N}(i=1,2,…,N),
where gi=j denotes that there exists a link between the nodes i and j. This means that thenodes i and j will be in the same community. It is necessary to identify all of the components of the corresponding graph in the decoding step. The nodes participating to the same component are assigned to the same community. Adopting this representation, the main advantage is that the decoding step can be done in linear time and it has been verified as an effective encoding schema for community detection as shown in [3]. Additionally, the number k of clusters is automatically determined by the number of components contained in an individual and is also determined by the decoding step [11].An example of the encoded genotype and corresponding network is shown in Figure1. As shown in Figure 1(a), the supposed network consists of seven nodes numbered from 1 to 7. It is obvious that the network can be partitioned into two groups visualized by different shape. A possible genotype as shown in Figure 1(b), which corresponds to the optimal solution, is translated in the graph structure given in Figure 1(c). Each connected component provides a grouping of nodes that corresponds to the partitioning of the network in Figure 1(a).(a) A graph modeled as a network, (b) the representation of a possible genotype, and (c) the graph structure of the genotype to be decoded.
(a)
(b)
(c)


## 3.4. Initialization

If an individual is created randomly, it may not be a feasible solution. In fact, a randomly generated individual could contain an allele valuej in the ith position, but no connection exists between the two nodes i and j; that is, the edge (i,j) is not present. In order to overcome this limitation, we should check whether the individual is safe after an individual is created. When the individual is not safe, that is, a gene i contains a value j, but link (i,j) does not exist, it needs to repair to ensure whether the individual is safe or not. Safe individuals improve the convergence of the method because the space of the possible solutions is restricted.


## 3.5. Crossover and Mutation

As in [3], we use uniform crossover which can guarantee the maintenance of the effective connections of the nodes in the network in the child individual. Given two arbitrary safe parent individuals and that a random binary vector is created, the genes are selected from the first parent if the vector element is 1, and the genes are selected from the second parent if the vector element is 0. Then the genes are combined to form a child. Because of the biased initialization, the child created from the two safe parents is safe also. In the child, if a position i contains a value j, then the edge (i,j) exists. The uniform crossover is shown in Figure 2.Figure 2
Illustration of the uniform crossover.Crossover operator is regarded as a macroscopic operation on individuals, while the mutation operator is regarded as a microcosmic operation on individuals. The mutation operator that randomly changes the valuej of the ith gene causes a useless exploration of the search space. In order to guarantee the mutated child is safe as the crossover operation, the possible value of an allele after mutating is restricted to be one of the replaced gene’s neighbors.


## 3.6. The Pseudocode of the Proposed Algorithm

The pseudocode of our DNCD-MOEA algorithm is described in Algorithm1.Algorithm 1
Program  DNCD-MOEA
Input:  The number T of time steps, the sequence of
dynamic networkN={N1,N2,…,NT}
Output:  The sequence of community structure detected in
the dynamic networkC={C1,C2,…,CT}
Begin
Step1: Set t=1. Generate the initial community structure
C1={C11,C12,…,C1k} of the network N1using
GA-Net algorithm. Sett=t+1.
Step2: If t>T, return the sequence of community
structureC={C1,C2,…,CT} as the output,
algorithm stops; Else, go to Step3.
Step3: Set s=1. Randomly generate individuals whose
length equals the nodes numbernt=|Vt| of
networkNt as an initial population Ps;
Step4: While termination condition is not satisfied do
Step4.1: Create a new population Qs of offspring by
applying the variation operators on
populationPs;
Step4.2: Combine the parents Ps and offspring Qs into a
new poolRs and;
Step4.3: Decode each individual I of the population Rs
to generate the partitioning
Ct={Ct1,Ct2,…,CtktI} of the network Nt in
kt connected components;
Step4.4: Evaluate the two fitness values of the translated
individuals;
Step4.5: Partition Rs into fronts, assign a rank to each
individual and sort them according to
nondomination rank;
Step4.6: Select individuals based on rank and crowding
length to comprise new populationPs+1;
Step4.7: Select the dominant individuals Ls in Ps+1,
Step4.8: Perform the local search algorithm on the
selected individuals inLs to generate the new
dominant populationLs′. Update the dominant
populationLs with Ls′ in Ps+1.
Step4.9: s=s+1
End while
Step5: Select the individual which has the maximum
Community Score on the Pareto front. Decode the
selected individual to get the community structure
Ct={Ct1,Ct2,…,Ctkt} of the network Nt.
Step6: Set t=t+1, go to Step 2.
End


## 3.7. Local Search Strategy

Local search is proved to be an effective algorithm. The mutation operator is regarded as a microcosmic operation on individuals and can achieve its local search function by moving single nodes between communities. Inspired by this idea, we adopt mutation operator in our local search algorithm.In local search algorithm, it needs to convert multiple objectives into a single objective function. In our study, we select a weighted objective as follows [3]:
(7)G(x)=∑i=12rigi(x),
where gi(x) is the objective function which is described in (2) and (3), respectively, and ri is the nonnegative weights for the two objectives. The weights are calculated in a special way as follows:
(8)ri=(gi(x)-gimin)/(gimax-gimin)∑j=12(gj(x)-gjmin)/(gjmax-gjmin),
where gimax or gimin is the maximum or minimum value of each objective function gi(x) in the obtained dominant population and ∑i=12ri=1. In Algorithm 2, the detailed pseudocode of the local search algorithm is given.Algorithm 2
Program: Local Search Algorithm:
Input: Given a dominant population Ls before local search
at thesth generation, the size M of dominant population Ls,
the numberN of local search.
Output: the improved population Ls′ in the sth generation.
Begin
(
1
)   for i=1 to M
(
2
)      j=1; find=false
(
3
)      while j<N and not find
(
4
)     Create a new individual applying the mutation
operator on theith individual of dominant
populationLs;
(
5
)     Calculate the objective function value of the new
individual according to formula (7). If its value is
greater than that before local search, add the new
individual toLs′, find=true;
(
6
)     j=j+1;
(
7
)      end while
(
8
)      if not find, adds the current individual to Ls′
(
9
)   end for
END


## 3.8. Computational Complexity

The computational complexity of DNCD-MOEA algorithm is investigated in this subsection. The DNCD-MOEA algorithm contains two major components: the main program based on the NSGA-II framework and the subprogram of local search operation. The time consuming of the main program mainly consists of three parts: generating nondominated sorting, calculating crowding distance assignment, and constructing partially ordered set. LetS denote the size of population and r denote the number of objects. The computational complexity of the three parts is O(r(2S)2), O(r(2S)log(2S)), and O(2Slog(2S)), respectively. So the total time complexity of the main programming is O(rS2). The local search operation mainly contains two loops and its computational complexity is O(MN). So, the total computational complexity of DNCD-MOEA algorithm is O(rS2)+O(MN). Because M<S, r=2, and in practice N<S, the time complexity can be simplified to O(S2).


## 4. Experiments

In order to check the ability of our approach on a dynamic network, we adopt the method proposed as [3] to generate data simulating dynamic network. Firstly, we generate synthetic datasets by following the procedure suggested by Girvan and Newman [1]. The datasets are generated using the software package designed by Lancichinetti et al. [13]. The data have 128 nodes, which are divided into 4 communities of 32 vertices each. Every node has an average degree of 16 and shares a number Zout, which represents the average number of edges from a node to nodes in other communities. If we increase Zout, then the noise level of network is augmented. On the other hand, if we decrease Zout, then the noise level in the network decreases.A parameterμ, which represents the average ratio of external degree/total degree for each node, is used to control the noise level in the dynamic networks. If the value of μ is increased, then the network will become more noisy in the sense that the community structure becomes less obvious and hard to detect. In this study, by setting μ=0.1 and μ=0.3, the datasets under two different noise levels are generated. In order to introduce dynamics into the network, we let the community structure of the network evolve in the following way. After time step 1, 5% of the nodes is randomly choused to leave their original community and randomly assigned to the other three communities at each time step. After the community memberships are decided, links are generated by following the parameter μ. We generate the network with community evolution in this way for 10 time steps.Figure3 shows the statistical average value of normalized mutual information with the ground truth over the 10 networks for the 10 timestamps when the value of μ=0.1 (Figure 3(a)) and μ=0.3 (Figure 3(b)). Both figures show that the proposed algorithm DNCD-MOEA can achieve better accuracy than the compared method. Especially, the average values of NMI at each time step obtained by DNCD-MOEA are closed to 1 when μ=0.1.Normalized mutual information (NMI) of clustering results when (a)μ=0.1 and (b) μ=0.3.
(a)
(b)Figure4 reports the community score obtained by the two algorithms at each time step when μ=0.1 (Figure 4(a)) and μ=0.3 (Figure 4(b)). It indicates that the corresponding network is densely connected within each subnetwork when the obtained value of community score is larger. From Figure 4, it can be found that the algorithm DNCD-MOEA outperforms the algorithm DYN-MOGA. That is to say, the community structure obtained by our algorithm is more closed to the true community structure.Community score when (a)μ=0.1 and (b) μ=0.3.
(a)
(b)


## 5. Conclusions

In this paper, a novel multiobjective algorithm for detecting communities in dynamic networks is proposed. Based on optimizing modularity density and NMI, the algorithm automatically provides a solution representing the best tradeoff between the accuracy of the community structure obtained with respect to the data of the current time step and the deviation from one time step to the successive. To solve the proposed model, the new genetic operators are designed based on the problem-specific knowledge. A local search operator is designed in order to improve the quality of the solutions. Experimental results on synthetic datasets show that the proposed algorithm can obtain better performance than the compared algorithm. Future research will aim at improving efficiency and applying proposed algorithm to process real-life network.



---

*Source: 161670-2013-05-30.xml*