Understanding the Role of Positive and Negative Relations for Community Detection Problem in Signed Networks: A New Perspective

Abstract

In real world, almost all networks come out with positive and negative types of relations. The sign could reflect like-dislike, agreement-disagreement, friendship-enmity, and attraction-discouragement. The contribution of this paper is to introduce prototype definitions for both nodes and communities of signed networks according to the distribution of positive and negative signs over the network's links. Two types of nodes (strong and weak) are introduced. Accordingly, three types of communities are declared, these are strong, weak, and irregular (or noisy). The formulated definitions provide us with a new understanding for the difficulty raised in community detection problem in signed networks. One of the recent state-of-the-art multi-objective detection models (modeled after Liu et al.) is adopted in this study as the optimization function for one of the well-known decomposition based multi-objective evolutionary algorithm (MOEA/D). In the experiments, different levels of complex synthetic networks are generated, characterized, and used as test-bed to explore and evaluate the performance of MOEA/D for solving community detection problem. The results reveal that the accuracy of the network partitioning solutions is increased while increasing the percentage of strong nodes and strong communities and vice versa while increasing percentage of weak nodes and weak and irregular communities.