Comparison and Selection of Objective Functions in Multiobjective Community Detection


Abstract

Detecting communities of complex networks has been an effective way to identify substructures that could correspond to important functions. Conventional approaches usually consider community detection as a single-objective optimization problem, which may confine the solution to a particular community structure property. Recently, a new community detection paradigm is emerging: multiobjective optimization for community detection, which means simultaneously optimizing multiple criteria and obtaining a set of community partitions. The new paradigm has shown its advantages. However, an important issue is still open: what type of objectives should be optimized to improve the performance of multiobjective community detection? To exploit this issue, we first proposed a general multiobjective community detection solution (called NSGA-Net) and then analyzed the structural characteristics of communities identified by a variety of objective functions that have been used or can potentially be used for community detection. After that, we exploited correlation relations (i.e., positively correlated, independent, or negatively correlated) between any two objective functions. Extensive experiments on both artificial and real networks demonstrate that NSGA-Net optimizing over a pair of negatively correlated objectives usually leads to better performances compared with the single-objective algorithm optimizing over either of the original objectives, or even to other well-established community detection approaches.