论文标题
复杂社交网络中社区检测的进化多目标优化算法
Evolutionary Multi Objective Optimization Algorithm for Community Detection in Complex Social Networks
论文作者
论文摘要
大多数基于优化的社区检测方法在单个或双目标框架中提出了问题。在本文中，我们使用自定义的非主导分类遗传算法III（NSGA-III）提出了两种三个目标公式的变体，以在网络中找到社区结构。在名为NSGA-III-KRM的第一个变体中，我们将内核K均值，比率削减和模块化视为三个目标，而第二个变体（称为NSGA-IIII-CCM），将社区得分，社区健身和模态性视为三个目标功能。实验是在四个基准网络数据集上进行的。与最先进的方法以及基于分解的多目标进化算法变体（MOEA/D-KRM和MOEA/D-CCM）的比较表明，所提出的变体产生了可比或更好的结果。这尤其重要，因为增加第三个目标不会使其他两个目标的结果恶化。我们还提出了一种简单的方法来对帕累托溶液进行排名，从而通过提出一种新的度量，即超体积和倒世代距离（IGD）的比率。比率越高，帕累托集越好。在多目标框架中，该策略在没有经验掌握功能的情况下特别有用，该框架的数量超过两个。
Most optimization-based community detection approaches formulate the problem in a single or bi-objective framework. In this paper, we propose two variants of a three-objective formulation using a customized non-dominated sorting genetic algorithm III (NSGA-III) to find community structures in a network. In the first variant, named NSGA-III-KRM, we considered Kernel k means, Ratio cut, and Modularity, as the three objectives, whereas the second variant, named NSGA-III-CCM, considers Community score, Community fitness and Modularity, as three objective functions. Experiments are conducted on four benchmark network datasets. Comparison with state-of-the-art approaches along with decomposition-based multi-objective evolutionary algorithm variants (MOEA/D-KRM and MOEA/D-CCM) indicates that the proposed variants yield comparable or better results. This is particularly significant because the addition of the third objective does not worsen the results of the other two objectives. We also propose a simple method to rank the Pareto solutions so obtained by proposing a new measure, namely the ratio of the hyper-volume and inverted generational distance (IGD). The higher the ratio, the better is the Pareto set. This strategy is particularly useful in the absence of empirical attainment function in the multi-objective framework, where the number of objectives is more than two.
