Community structure detection in complex networks using DNA genetic algorithm

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

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遗传算法的复杂网络社区结构发现

戴飞飞,唐普英

电子科技大学光电信息学院，成都 610054

通讯作者: 戴飞飞

Abstract

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遗传算法

DAI Fei-fei,TANG Pu-ying. Community structure detection in complex networks using DNA genetic algorithm[J]. Computer Engineering and Applications, 2008, 44(3): 53-56.

戴飞飞,唐普英. 基于DNA遗传算法的复杂网络社区结构发现[J]. 计算机工程与应用, 2008, 44(3): 53-56.

[1]	SHI Yuqiang, TIAN Yongzheng, ZHANG Yuqi, SHI Xiaoqiu. Solving FJSP by Multi-population Genetic Algorithms with Complex Network Structure [J]. Computer Engineering and Applications, 2021, 57(2): 257-266.
[2]	CAI Fei, ZHANG Xin, MU Xiaohui, CHEN Jie, CAI Xun. Research on Link Prediction Method Based on Deep Non-negative Matrix Factorization [J]. Computer Engineering and Applications, 2020, 56(15): 153-161.
[3]	ZHANG Xin, GUO Yang. Betweenness-Degree Entropy Invulnerability Measurement Method in Complex Networks [J]. Computer Engineering and Applications, 2020, 56(12): 105-111.
[4]	SHENG Jinfang, LIU Jiaguang, WANG Bin. Katz Auto Encoder for Urban Road Network Link Prediction Model [J]. Computer Engineering and Applications, 2019, 55(8): 116-123.
[5]	ZHU Xiaoxia, HU Xiaoxue. Identification of Node Influence Based on Improved k-shell Algorithm [J]. Computer Engineering and Applications, 2019, 55(1): 35-41.
[6]	LIN Ding1, 2, XU Ying1, 2, HUANG Guoxin1, 2, CHEN Chongcheng1, 2. Visualizing graph data in 3D tree-style based on Louvain algorithm [J]. Computer Engineering and Applications, 2018, 54(7): 96-101.
[7]	DU Wenju1, ZHANG Jiangang2, YU Jianning1. Research on stability?of complex bus community network model [J]. Computer Engineering and Applications, 2017, 53(23): 39-46.
[8]	LI Yuchi, LI Haifang, JIE Dan, YIN Guimei, HU Keyou. Phase synchronization analysis of emotional EEG based on complex network theory [J]. Computer Engineering and Applications, 2017, 53(18): 230-235.
[9]	ZHAO Weiji1，2, ZHANG Fengbin2, LIU Jinglian1, JIN Hao1. Community mining algorithm based on central maximal-clique expansion [J]. Computer Engineering and Applications, 2017, 53(15): 164-169.
[10]	YANG Qiang, LU Gang. Establishment and study of properties of Weibo social network model [J]. Computer Engineering and Applications, 2016, 52(12): 42-48.
[11]	TIAN Wenxiu, TAN Manchun, ZHOU Xuan. Finite-time generalized outer synchronization of time-varying couple complex networks [J]. Computer Engineering and Applications, 2015, 51(9): 41-45.
[12]	MIN Liang1, SHAO Liangshan2, ZHAO Yonggang1. Community detection based on node similarity [J]. Computer Engineering and Applications, 2015, 51(9): 77-81.
[13]	WEN Hong1，2, FAN Xiaoping1，3, ZHANG Huifu2, CHEN Anhua2. Dynamic local routing strategy design on scale-free networks [J]. Computer Engineering and Applications, 2014, 50(20): 10-14.
[14]	ZHANG Zhen, ZHANG Zhenyu, SONG Manman. Important node searching algorithm based on shortest-path betweeness [J]. Computer Engineering and Applications, 2013, 49(21): 98-100.
[15]	LI Faxu. Dynamic local world evolution model of complex supply chain network [J]. Computer Engineering and Applications, 2012, 48(8): 125-127.

Community structure detection in complex networks using DNA genetic algorithm

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics