局部搜索与遗传算法结合的大规模复杂网络社区探测  

Genetic Algorithm with Local Search for Community Detection in Large-scale Complex Networks

作　　者：金弟[1,2] 刘杰[1,2] 杨博[1,2] 何东晓[1,2] 刘大有[1,2] 

机构地区：[1]吉林大学计算机科学与技术学院,长春130012 [2]吉林大学符号计算与知识工程教育部重点实验室,长春130012

出　　处：《自动化学报》2011年第7期873-882,共10页Acta Automatica Sinica

基　　金：国家高技术研究发展计划(863计划)(2006AA10Z245);国家自然科学基金(60773099;60703022;60873149;60973088);模式识别国家重点实验室开放课题(09-1-1);中央高校基本科研业务费专项资金(200903177);复旦大学智能信息处理上海市重点实验室开放课题(IIPL-09-007)资助~~

摘　　要：基于遗传算法的复杂网络社区探测是当前的研究热点.针对该问题,本文在分析网络模块性函数Q的局部单调性的基础上,给出一种快速、有效的局部搜索变异策略,同时为兼顾初始种群的精度和多样性以达到进一步提高搜索效率的目的,采用了标签传播作为初始种群的产生方法;综上,提出了一个结合局部搜索的遗传算法(Genetic algorithm with local search,LGA).在基准网络及大规模复杂网络上对LGA进行测试,并与当前具有代表性的社区探测算法进行比较,实验结果表明了文中算法的有效性与高效性.Detecting communities from complex networks by genetic algorithm has triggered a great common interest. For this problem, a genetic algorithm with local search （LGA） which employs network modularity Q as objective function is given in this work. An effective as well as effcient mutation method combined with a local search strategy is proposed based on our profound analysis on local monotonicity of function Q, meanwhile, a label propagation based method is adopted to produce the accurate and diverse initial population, which can further improve the search effciency of LGA. The proposed LGA has been tested on both benchmark networks and some large-scale complex networks, and compared with some competitive community detection algorithms. Experimental result has shown that LGA is highly effective and effcient for discovering community structure.

关 键 词：复杂网络 社区探测 网络聚类 遗传算法 局部搜索 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]