TY - GEN
T1 - Community detection in social and biological networks using differential evolution
AU - Jia, Guanbo
AU - Cai, Zixing
AU - Musolesi, Mirco
AU - Wang, Yong
AU - Tennant, Dan A.
AU - Weber, Ralf J.M.
AU - Heath, John K.
AU - He, Shan
PY - 2012/10/30
Y1 - 2012/10/30
N2 - 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.
AB - 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.
KW - Community structure
KW - Differential Evolution
KW - evolutionary computation
KW - graph partitioning
UR - http://www.scopus.com/inward/record.url?scp=84867853435&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-34413-8_6
DO - 10.1007/978-3-642-34413-8_6
M3 - Conference contribution
AN - SCOPUS:84867853435
SN - 9783642344121
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 71
EP - 85
BT - Learning and Intelligent Optimization - 6th International Conference, LION 6, Revised Selected Papers
T2 - 6th International Conference on Learning and Intelligent Optimization, LION 6
Y2 - 16 January 2012 through 20 January 2012
ER -