| 引用本文: | 杨波,程维政,朱超.小世界效应加速生物地理学优化的社团识别算法[J].哈尔滨工业大学学报,2020,52(3):179.DOI:10.11918/201811143 |
| YANG Bo,CHENG Weizheng,ZHU Chao.Detecting communities via biogeography-based optimization accelerated by small-world effects[J].Journal of Harbin Institute of Technology,2020,52(3):179.DOI:10.11918/201811143 |
|
| 摘要: |
| 为提高基于优化方法的网络社团结构识别算法的有效性,设计一种利用小世界效应加速生物地理学优化过程的网络社团结构识别算法. 首先基于矩阵随机编码建立网络社团识别生物地理学优化框架,在栖息地中全局进化地搜索对应于最大化模块度的网络社团划分. 然后,给出基于小世界效应的生物地理学迁移策略,可以加速进化算法的信息交换过程. 最后,运用该算法在现实网络和人工合成网络上进行实验. 结果表明:引入小世界效应能够降低网络社团结构识别算法的收敛时间；在典型现实网络与人工合成网络上运行该算法能够获得较高的模块度值与标准化互信息值；信息交换的拓扑结构能够优化进化算法效率. 应用小世界效应加速生物地理学优化的网络社团识别算法具有较好的可行性与有效性. |
| 关键词: 网络 社团结构识别 进化算法 生物地理学优化 小世界效应 |
| DOI：10.11918/201811143 |
| 分类号:TP393.0 |
| 文献标识码:A |
| 基金项目:国家自然科学基金(61203032)；湖北省自然科学基金(2012FFB05007)；国家留学基金委基金(201406955049) |
|
| Detecting communities via biogeography-based optimization accelerated by small-world effects |
|
YANG Bo,CHENG Weizheng,ZHU Chao
|
|
(School of Automation, Wuhan University of Technology, Wuhan 430070, China)
|
| Abstract: |
| To enhance the efficiency of optimization-based algorithms for detecting community structures in networks, a novel algorithm was designed by utilizing the small-world effects to accelerate biogeography-based optimization process for community detection. First, based on matrix random coding, the problems of detecting community structures in networks were embedded into the framework of biogeography-based optimization. Community structures were searched evolutionarily and globally corresponding to the maximal modularity in habitat. Then, a migration evolutionary strategy was introduced based on the small-world effects, which can accelerate the information exchange process of the proposed evolutionary algorithm. Finally, tests on real-world and computer-generated networks were conducted using the proposed algorithm. Results show that the small-world effects reduced the convergence time of the algorithm for community detection, and the values of the modularity and the normalized mutual information were both high when applying the proposed algorithm to the real-world and the computer-generated networks. The topology structures of information exchanges could optimize the efficiency of the evolutionary algorithm. Therefore, the algorithm adopting small-world effects to accelerate biogeography-based optimization for network community detection was proved feasible and effective. |
| Key words: network community detection evolutionary algorithm biogeography-based optimization small-world effects |
