Multi-objective community detection in complex networks

Community detection in social network analysis is usually considered as a single objective optimization problem, in which different heuristics or approximate algorithms are employed to optimize a objective function that capture the notion of community. Due to the inadequacy of those single-objective solutions, this paper first formulates a multi-objective framework for community detection and proposes a multi-objective evolutionary algorithm for finding efficient solutions under the framework. After analyzing and comparing a variety of objective functions that have been used or can potentially be used for community detection, this paper exploits the concept of correlation between objective which charcterizes the relationship between any two objective functions. Through extensive experiments on both artifical and real networks, this paper demonstrates that a combination of two negatively correlated objectives under the multi-objective framework usually leads to remarkably better performance compared with either of the orignal single objectives, including even many popular algorithms..

This paper formulates the community detection as a multi-objective optimization problem and proposes a novel solution which simultaneously optimizes two components (i.e., intra and inter) of modularity Q. The multi-objective community detection can find a set of optimal solutions, which is helpful to reveal complex community structures (e.g., hierarchical and overlapping structures). Moreover, based on the Max-Min distance model selection method, our algorithm can recommend a more accurate community partition.Figure optionsDownload as PowerPoint slide