Improving the performance of evolutionary multi-objective co-clustering models for community detection in complex social networks

摘要

Due to globalization, the characteristic of many systems in biology, engineering and sociology paradigms can nowadays be captured and investigated as networks of connected communities. Detecting natural divisions in such complex networks is proved to be extremely NP-hard problem that recently enjoyed a considerable interest. Among the proposed methods, the field of multi-objective evolutionary algorithms (MOEAs) reveals outperformed results. Despite the existing efforts on designing effective multi-objective optimization (MOO) models and investigating the performance of several MOEAs for detecting natural community structures, their techniques lack the introduction of some problem-specific heuristic operators that realize their principles from the natural structure of communities. Moreover, most of these MOEAs evaluate and compare their performance under different algorithmic settings that may hold unmerited conclusions. The main contribution of this paper is two-fold. Firstly, to reformulate the community detection problem as a MOO model that can simultaneously capture the intra-and inter community structures. Secondly, to propose a heuristic perturbation operator that can emphasize the search for such intra-and inter-community connections in an attempt to offer a positive collaboration with the MOO model. One of the prominent multi-objective evolutionary algorithms (the so-called MOEA/D) is adopted with the proposed community detection model and the perturbation operator to identify the overlapped community sets in complex networks. Under the same MOEA/D characteristic settings, the performance of the proposed model and test results are evaluated against three state-of-the-art MOO models. The experiments on real-world and synthetic social networks of different complexities demonstrate the effectiveness of the proposed model to define community detection problem. Moreover, the results prove the positive impact of the proposed heuristic operator to harness the strength of all MOO models in both terms of convergence velocity and convergence reliability. (C) 2015 Elsevier B.V. All rights reserved.