Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (3): 53-56.

• 学术探讨 • Previous Articles     Next Articles

Community structure detection in complex networks using DNA genetic algorithm

DAI Fei-fei,TANG Pu-ying   

  1. School of Opto-Electronic Information,University of Electronic Science and Technology of China,Chengdu 610054,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2008-01-21 Published:2008-01-21
  • Contact: DAI Fei-fei

基于DNA遗传算法的复杂网络社区结构发现

戴飞飞,唐普英   

  1. 电子科技大学 光电信息学院,成都 610054
  • 通讯作者: 戴飞飞

Abstract: Community structure identification have been one of the most popular research areas in recent years and there have been many algorithms proposed so far to detect community structures in complex networks in varied topics,where most of the algorithms have some drawbacks,and some of them are not suitable for very large networks because of their time-complexity.In this paper,we present an algorithm for detecting community structures in complex network,which is based on the DNA genetic algorithm.It doesn’t need any priori knowledge about the numbers of communities and any threshold values.The algorithm is tested on the two network data named Zachary Karate Club and College Football.

Key words: complex networks, community structure, DNA genetic algorithm

摘要: 复杂网络社区结构划分日益成为近年来复杂网络的研究热点,到目前为止,已经提出了很多分析复杂网络社区结构的算法。但是大部分算法还存在一定的缺陷,而且有些算法由于其时间复杂度的过高导致其不合适应用于对大型网络的分析。提出了一种基于DNA遗传算法的复杂网络社区结构分析的方法。该方法无须预先知道社区内结点的数量以及任何门限值。该算法的可行性用Zachary Karate Club和College Football Network模型进行验证。

关键词: 复杂网络, 社区结构, DNA遗传算法