Community detection in social and biological networks using differential evolution

Research output: Chapter in Book/Report/Conference proceedingConference contribution

External organisations

  • Central South University China

Abstract

The community detection in complex networks is an important problem in many scientific fields, from biology to sociology. This paper proposes a new algorithm, Differential Evolution based Community Detection (DECD), which employs a novel optimization algorithm, differential evolution (DE) for detecting communities in complex networks. DE uses network modularity as the fitness function to search for an optimal partition of a network. Based on the standard DE crossover operator, we design a modified binomial crossover to effectively transmit some important information about the community structure in evolution. Moreover, a biased initialization process and a clean-up operation are employed in DECD to improve the quality of individuals in the population. One of the distinct merits of DECD is that, unlike many other community detection algorithms, DECD does not require any prior knowledge about the community structure, which is particularly useful for its application to real-world complex networks where prior knowledge is usually not available. We evaluate DECD on several artificial and real-world social and biological networks. Experimental results show that DECD has very competitive performance compared with other state-of-the-art community detection algorithms.

Details

Original languageEnglish
Title of host publicationLearning and Intelligent Optimization - 6th International Conference, LION 6, Revised Selected Papers
Publication statusPublished - 30 Oct 2012
Event6th International Conference on Learning and Intelligent Optimization, LION 6 - Paris, France
Duration: 16 Jan 201220 Jan 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7219 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference6th International Conference on Learning and Intelligent Optimization, LION 6
CountryFrance
CityParis
Period16/01/1220/01/12

Keywords

  • Community structure, Differential Evolution, evolutionary computation, graph partitioning