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

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

基于遗传算法的复杂网络社区探测是当前的研究热点.针对该问题,本文在分析网络模块性函数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.