用遗传算法优化模块密度探测社团结构

Genetic algorithm optimizing modularity density for community detection

为更精确地探测社团结构,通过选择优化函数,分析社团结构特性,设计适合社团检测的选择、交叉、变异等遗传算子,提出了基于遗传算法和模块密度的社团结构探测算法。该算法未采用传统的分裂或聚合方法用减边或加边的策略,没有引入其他中间变量,直接通过优化模块密度函数发现网络社团结构。分析和仿真结果表明,该算法探测的社团结构与模块度探测算法相比,能检测到更小规模的社团结构,参照强弱社团结构定义,比较各节点的内部度,其不满足强社团定义的节点明显小于其他划分结果,在性能上有了显著提高,能更准确地测度社团结构。

Identification and detection of the community structure is fundamental and important problem for the analysis of complex network. To detect community structure precisely,a new community detection algorithm was designed based on genetic algorithm and modularity density D. The algorithm does not need any prior knowledge about the number of communities, requires no arbitrary convergence or abruption criteria, and can generally find the global optimal solution. Genetic algorithm for detecting communities in complex networks, based on optimizing network modularity density was presented here. The algorithm was illustrated and compared with GN algorithm by using classic real world networks. Optimizing modularity density D not only can resolve detail modules but also can correctly identify the number of communities. Experimental results show the method can reveal community structure more precisely than traditional approaches. According to the definition of community in a strong sense, the nodes in experimental result which have more connections within the community than with the rest of the graph are more than the other partitions.