Complex Network Community Detection Algorithm Based on Genetic Algorithm
For the problem of complex network community detection, propose a new algorithm based on genetic algorithm to solve it. This algorithm sets network modularity function as target function and fitness function, uses matrix encoding to describe individuals,
- PDF / 282,089 Bytes
- 11 Pages / 439.36 x 666.15 pts Page_size
- 9 Downloads / 219 Views
Complex Network Community Detection Algorithm Based on Genetic Algorithm Yun Li, Gang Liu, and Song-yang Lao
Abstract For the problem of complex network community detection, propose a new algorithm based on genetic algorithm to solve it. This algorithm sets network modularity function as target function and fitness function, uses matrix encoding to describe individuals, and generates initial population using nodes similarity. The crossover operation is based on the quality of individuals’ genes, in this process, all nodes that weren’t partitioned into any communities make up a new one together, and the nodes that were partitioned into more than one community are placed into the community to which most of their neighbors belong. The mutation operation is non-uniform, which splits the mutation gene into two new genes or fuses it into the others randomly. The experiment proved that this algorithm could effectively detect communities in complex networks. Keywords Complex network • Community detection • Genetic algorithm
25.1 Introduction In 2002, Newman and Girvan opened up a new field of complex network research – complex network community detection (Girvan and Newman 2002). It uses the information contained in network topology to get the community structure of complex network, which has some connotations. The research of this problem, which is of great significance, helps to study the whole network’s module, function and its evolution in a divide and conquer way so that to understand complex network’s organization principle, topology and dynamics characteristic more correctly (Luo et al. 2011). Y. Li () • G. Liu • S. Lao Information System and Management College, National University of Defense Technology, Changsha, China e-mail: [email protected] E. Qi et al. (eds.), The 19th International Conference on Industrial Engineering and Engineering Management, DOI 10.1007/978-3-642-37270-4 25, © Springer-Verlag Berlin Heidelberg 2013
257
258
Y. Li et al.
In 2004, they proposed network modularity (Newman and Girvan 2004) to quantitatively evaluate the result’s quality of complex network community detection, and its function is as follows: ki kj 1 X QD (25.1) ı ci ; cj aij 2m ij 2m Where aij represents an element of network adjacency matrix A D aij nn , if nodes i and j are connected by an edge, then aij D 1, or aij D 0; ci and cj respectively stand for that nodes i and j belongs to; if ci D cj , the communities ı ci ; cj D 1, or ı ci ; cj D 0; ki and kj respectively represent the degrees of n n P P aij , kj D aij , i; j D 1; 2; : : : ; n; m and n are respectively nodes i and j, ki D j D1
i D1
the amount of network’s edges and that of nodes. jQj 1, the greater it is, the better the result of complex network community detection is.
25.2 Methodology To assume each node in complex network G(V, E) belongs to only one community, that’s to say, communities are not intersected or overlapped, and: V D fvi ji D 1; 2; : : : ; ng ; E D fei ji D 1; 2; : : : ; mg Where V and E respectively represent th
Data Loading...
