离散Jaya算法的复杂网络社区发现

社区结构是复杂网络的重要特性之一, 基于模块度的复杂网络社区发现问题是一个NP难度的组合优化问题, 常用启发式算法求解. 最近出现的Jaya算法是求解连续优化问题的一种简单有效的元启发式方法. 本文在遵循Jaya算法按靠近最好解、远离最差解的方式更新种群个体的基础上, 针对复杂网络社区发现问题给出了Jaya算法离散化的策略, 提出一种复杂网络社区发现的离散Jaya算法. 实验表明, 在几个典型真实网络实例和一类人造网络实例上, 与几个经典算法和元启发式算法相比, 本文算法具有求解精度高、能自动确定社区数目等优点.

Discrete Jaya Algorithm for Complex Network Community Detection

Community structure is one of most important characteristics of complex networks. The community detection problem based on modularity is NP-hard as a combinatorial optimization problem, which is often solved by heuristic algorithms. Jaya algorithm is a simple and effective meta-heuristic method for solving continuous optimization problems. In this study, the strategy of discreting Jaya algorithm for complex network community discovery is given on the basis of updating the population individuals according to the way Jaya algorithm works, that is, an individual is updated close to the best solution and far away from the worst solution, and thus a discrete Jaya algorithm for complex network community discovery is proposed. Experiments show that the proposed algorithm has the advantages of high resolution and automatic determination of the number of communities compared with the classical algorithms in several real network instances and a class of artificial network instances.