Convex inference for community discovery in signed networks

Abstract

In contrast to traditional social networks, signed ones encode both relations of affinity and disagreement. Community discovery in this kind of networks has been successfully addressed using the Potts model, originated in statistical mechanics to explain the magnetic dipole moments of atomic spins. However, due to the computational complexity of finding an exact solution, it has not been applied to many real-world networks yet. We propose a novel approach to compute an approximated solution to the Potts model applied to the context of community discovering, which is based on a continuous convex relaxation of the original problem using hinge-loss functions. We show empirically the benefits of the proposed method in comparison with loopy belief propagation in terms of the communities discovered. We illustrate the scalability and effectiveness of our approach by applying it to the network of voters of the European Parliament that we have crawled for this study. This large-scale and dense network comprises about 300 votings periods on the actual term involving a total of more than 730 voters. Remarkably, the two major communities are those created by the european-antieuropean antagonism, rather than the classical right-left antagonism.