A new evolutionary multi-objective community mining algorithm for signed networks

摘要

Community detection in presence of both positive and negative interactions in signed community structures has recently enjoyed a large increase in interest. The general definition of community structure which considers both strong and weak connections of the individual nodes in a network is adopted in the literature for signed community detection. Despite the widespread use of this definition, it lacks complete reflection of specific topological properties such as type of ties, in terms of positive and negative connections. To remedy this difficulty, a new community detection model for signed networks is suggested in this paper. The main contribution of this paper is three-fold. First, the quantitative definition of community structure is revisited to properly reflect positive and negative characteristics of the ties in signed networks. Three definitions are introduced to explicitly identify the possible means of signed communities in three different forms. These are strong signed community, weak signed community, and irregular signed community. Then, a new multi-objective signed community detection model and a new anti-frustration heuristic operator are introduced. The proposed model and operator hypothesize a possible clustering of the signed complex network into signed communities under the framework of multi-objective evolutionary algorithm. The essential principle of both of them is to establish "more positive and less negative intra relations between the nodes of a signed community'' and "more negative and less positive inter relations among different signed communities''. The performance of the proposed model is tested against other state-of-the-art signed community detection models. In the experiments, we demonstrate that, in general, our model outperforms the counterpart models, and moreover, the proposed anti-frustration heuristic operator harnesses the strength of all detection models, keeping our model with the highest level of detection reliability. (C) 2019 Elsevier B.V. All rights reserved.