Multiresolution community detection in complex networks by using a decomposition based multiobjective memetic algorithm

doi:10.1007/s12293-022-00370-z

2022-07-11

PRE

DOI：10.1007/s12293-022-00370-z

原文链接

原文求助

摘要

En 中文

Community structures are sets of nodes that are densely linked with each other, reflecting the functional modules of real-world systems. Most classical works for community detection (CD) are based on the optimization of an objective function, namely modularity. However, it has been recently demonstrated that there exists a resolution limit in the modularity optimization based CD methods, i.e., the communities cannot be detected if their scales are smaller than a certain threshold. To overcome this resolution limit, in this paper, we propose a decomposition based multiobjective memetic algorithm (called MDMCD) for multiresolution CD (MCD) in complex networks, aiming to detect communities at multiple resolution levels. MDMCD first models the MCD problem as a multiobjective optimization problem (MOP) with two contradictory objectives, namely the intra-link ratio and inter-link ratio. Then, it devises a multiobjective memetic optimization framework that combines a decomposition based multiobjective evolutionary algorithm with a two-level local search to solve the modeled MOP. In this framework, the modeled MOP is first decomposed into a set of single-objective optimization subproblems, each of which corresponds to a CD problem in a certain resolution level. Subsequently, these subproblems are simultaneously optimized by the evolutionary operators and the local search, taking the network-specific knowledge into consideration. Finally, MDMCD returns a population of solutions in a single simulation run, reflecting the community divisions at multiple resolution levels. Experiments on both the simulated and real-world networks show the effectiveness of MDMCD in detecting multiresolution community structures.

Keyword:

Multiobjective optimization

Memetic algorithm

Community detection

Multiresolution

Complex networks