Exploiting Antagonistic Relations in Signed Graphs under the Structural Balance Hypothesis

Abstract

Abstract, Communication orale ; International audience ; A signed graph is considered structurally balanced [1] if it can be partitioned into a number of clusters, such that positive (negative) links are located inside (in-between) the clusters. Due to the imbalanced nature of real-world networks, various measures have been dened to quantify the amount of imbalance, the simplest consisting in counting the numbers of misplaced links [1]. Such measures are expressed relatively to a graph partition, so processing the graph balance amounts to identifying the partition corresponding to the lowest imbalance measure. Our goal is to use this paradigm to study the roll-call voting activity of the Members of the European Parliament (MEPs). We want not only to detect groups of MEPs which would be cohesive in terms of votes (i.e groups of antagonistic voters), but also to identify the characteristic ways in which the MEP set is partitioned by these votes. The standard approach to study this type of system is to extract a mean vote similarity network (e.g. [2]). However, this approach suers from several limitations. The two main ones are that 1) they rely on some temporal integration of the raw data, which causes some information loss; and/or 2) they identify groups of antagonistic voters, but not the context associated to their occurrence. In this work, we propose a novel method taking advantage of multiplex signed graphs to solve both these issues. It consists in rst partitioning separately each layer which models a single roll-call as a signed unweighted graph, before grouping these partitions by similarity. We show the interest of our approach by applying it to a European Parliament dataset and by comparing the results with those obtained through a standard approach in our previous work [3].