首页 | 本学科首页   官方微博 | 高级检索  
     

复杂网络社区挖掘——-基于聚类融合的遗传算法
引用本文:何东晓,周栩,王佐,周春光,王喆,金弟.复杂网络社区挖掘——-基于聚类融合的遗传算法[J].自动化学报,2010,36(8):1160-1170.
作者姓名:何东晓  周栩  王佐  周春光  王喆  金弟
作者单位:1.吉林大学计算机科学与技术学院 长春 130012
摘    要:针对当前研究复杂网络社区挖掘的热点问题, 提出了一种基于聚类融合的遗传算法用于复杂网络社区挖掘. 该算法将聚类融合引入到交叉算子中, 利用父个体的聚类信息辅以网络拓扑结构的局部信息产生新个体, 避免了传统交叉算子单纯交换字符块而忽略了聚类内容所带来的问题. 为使聚类融合的作用得以充分发挥, 本文提出了基于马尔科夫随机游走的初始群体生成算法, 使初始群体中的个体具有一定聚类精度并有较强的多样性. 初始群体生成算法与基于聚类融合的交叉算子互相配合, 有效地增强了算法的寻优能力. 此外, 算法将局部搜索机制用于变异算子, 通过迫使变异节点与其多数邻居在同一社区内, 有针对性地缩小了搜索空间, 从而加快了算法收敛速度. 在计算机生成网络和真实世界网络上进行了测试, 并与当前具有代表性的社区挖掘算法进行比较, 实验结果表明了该算法的可行性和有效性.

关 键 词:复杂网络    社区结构    遗传算法    聚类融合    局部搜索
收稿时间:2009-07-16

Community Mining in Complex Networks --- Clustering Combination Based Genetic Algorithm
HE Dong-Xiao,ZHOU Xu,WANG Zuo,ZHOU Chun-Guang,WANG Zhe,JIN Di.Community Mining in Complex Networks --- Clustering Combination Based Genetic Algorithm[J].Acta Automatica Sinica,2010,36(8):1160-1170.
Authors:HE Dong-Xiao  ZHOU Xu  WANG Zuo  ZHOU Chun-Guang  WANG Zhe  JIN Di
Affiliation:1.College of Computer Science and Technology, Jilin University, Changchun 130012 ;2.Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012
Abstract:Community mining has been the focus of many recent efforts on complex networks. In this paper, we propose a clustering combination based genetic algorithm (CCGA) for community mining in complex networks. The CCGA introduces clustering combination into the crossover operator and utilizes the clustering information of parent individuals to generate offspring, assisted by the local information of network topology. Thus, CCGA can be immune from the problems caused by traditional crossover operators that only exchange string blocks of different individuals but do not recombine their clustering contents. In order to make full use of clustering combination, a Markov random walk based population initializing method is proposed, which can provide us an initial population with individuals of certain clustering precision and high diversity. The population initializing method cooperates with the clustering combination based crossover operator, thus the search capability of CCGA is effectively strengthened. In addition, a local search strategy is used in the mutation operator, which makes the mutated node placed into the community to which most of its neighbors belong. Therefore, the specialized mutation operator allows the reduction of the searching space and thus speeds up the convergence of CCGA. The proposed CCGA is tested on both computer-generated and real-world networks, and is compared with current representative algorithms in community mining. Experimental results show the feasibility and validity of CCGA.
Keywords:Complex network  community structure  genetic algorithm  clustering combination  local search
点击此处可从《自动化学报》浏览原始摘要信息
点击此处可从《自动化学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号