Signed Graph Analysis for the Interpretation of Voting Behavior
Nejat Arinik Rosa Figueiredo Vincent Labatut
Laboratoire Informatique d’Avignon Laboratoire Informatique d’Avignon Laboratoire Informatique d’Avignon
LIA EA 4128 LIA EA 4128 LIA EA 4128
Avignon, France Avignon, France Avignon, France
nejat.arinik@univ-avignon.fr rosa.figueiredo@univ-avignon.fr vincent.labatut@univ-avignon.fr
ABSTRACT of nodes more densely connected relatively to the rest of the net-
In a signed graph, each link is labeled with either a positive or a work [12]. The main difference is of course the presence of signs
negative sign. This is particularly appropriate to model polarized attached to links, which represent additional information one has
systems. Such a graph can be characterized through the notion of to take into account. Doing so is a non-trivial task, which cannot be
structural balance, which relies on the partitioning of the graph into conducted by simply performing minor adaptations of community
internally solidary but mutually hostile subgroups. In this work, detection methods [5].
we show that signed graphs can be used to model and understand In a previous article, we have studied the structural balance of
voting behavior. We take advantage of data from the European Par- weighted signed graphs representing the voting activity of Mem-
liament to confront two variants of structural balance, and illustrate bers of the European Parliament (MEPs) [17]. We have compared
how their use can help better understanding the studied system. the results obtained with partitioning methods designed for com-
munity detection on the one hand, and for structural balance on
CCS CONCEPTS the other hand. Our main result was that, in contradiction with
some conclusions presented in another study [10], taking negative
• Information systems → Clustering; • Theory of computa-
links into account leads to significantly different partitions, at least
tion → Network optimization; • Applied computing → Voting /
for these data. This is consistent with other results appearing in the
election technologies;
literature and showing that the information conveyed by negative
links generally improves the resolution of the problems at hand,
KEYWORDS e.g. graph partitioning [9] or link prediction [14].
Signed Graph, European Parliament, Graph Partitioning, (Relaxed) But our study suffers from several limitations. First, the extracted
Correlation Clustering graphs contain many links with a close to zero weight, which could
have been considered as noise: they largely increase the processing
1 INTRODUCTION time and apparently make it harder to interpret the results, without
Signed graphs were primarily introduced in Psychology, with the significantly affecting the obtained partitions. Second, we focused
objective of describing the relationships between people belonging our discussion on objective aspects (the quality of the partitions in
to distinct social groups [13]: each one of their links is labeled with terms of imbalance) and stayed quite superficial when interpreting
a sign + or −, indicating the nature of the relationship between the our results relatively to the studied system. Third, the raw data we
considered adjacent nodes. A signed graph can be used to model any used as a base to extract the signed graphs were incomplete: they
system containing two types of antithetical relationships, such as did not cover the whole 7th term.
like/dislike, for/against, etc. Such a graph is considered structurally In a more recent work also conducted in our research group [16],
balanced if it can be partitioned into two [4] or more [7] mutually Levorato & Frota applied the same methodology as in [17] and tried
hostile subgroups each having internal solidarity. Here, the words to solve certain of these limitations. They focused on a different
hostile and solidarity mean: connected by negative and positive links, dataset, representing the voting activity at the National Congress
respectively. of Brazil, and performed a thorough interpretation of the obtained
However, it is very rare for a real-world network1 to have a partitions. They also considered a variant of the structural balance,
perfectly balanced structure: the question is then to quantify how which we will describe later. However, they used the extraction
imbalanced it is. Various measures have been defined for this pur- approach from [17], leading to complete, and therefore noisy, signed
pose, the simplest consisting in counting the numbers of misplaced graphs. This may be the reason why certain of the partitions they
links, i.e. positive ones located inside the groups, and negative ones obtained are marginally informative and/or difficult to interpret.
located between them [4]. Such measures are expressed relatively Moreover, this difficulty is further increased by the current confused
to a graph partition, so processing the graph balance amounts to political situation in Brazil2 .
identifying the partition corresponding to the lowest imbalance In this paper, we present the work we conducted to overcome the
measure. In other words, calculating the graph balance can be for- limitations of both studies [16, 17], with the following contributions.
mulated as an optimization problem. This type of optimization First, we come back to the European Parliament (EP), through a
problem can be compared to that of community detection, which different, complete, data source. Second, we include a filtering step
consists in partitioning unsigned networks in order to detect groups to get rid of the noise present in the complete graphs. Third, we
focus our interpretation only on a small part of the available data,
1 We use the following words indistinctly in this article: graph and network, node and
2 http://www.bbc.com/news/world-latin-america-35810578.
vertex, link and edge.
in order to deliver a deeper analysis and better show the interest of source: the website It’s Your Parliament 4 (IYP), which is indepen-
structural balance to characterize and understand the considered dently maintained by the Danish company Buhl & Rasmussen, and
system. aims at both providing an easy access to these data and presenting
The rest of the article is organized as follows. In Section 2, we analyses of the MEPs voting patterns.
describe the methods we used to extract the signed networks from In this dataset, one vote can be represented in 3 ways: For (the
our raw data, as well as the partitioning algorithms we applied to MEP wants the text to be accepted), Against (he wants the text to
them. In Section 3, we study the effect of the additional filtering be rejected) and Abstention (he wants to express his neutrality).
step on these algorithms, and the quality of a heuristic proposed It is also possible that the MEP did not vote at all, in which case he
to measure the imbalance. In Section 4, we present our results on is considered as Absent.
a few specific cases selected from our corpus, and discuss them.
2.1.2 Extraction Procedure. As mentioned before, the behavior
We adopt the perspective of the end-user, and instead of simply
of each MEP is represented by a series of votes, corresponding to
focusing on the objective performance of the considered partition-
all the documents reviewed by the EP during one term. We want
ing algorithms, we also comment on the quality of the identified
to extract signed networks summarizing these data. But before
clusters relatively to the studied system. Finally, in Section 5 we
explaining how, we need to formalize a certain number of concepts.
summarize our findings, comment the limitations of our work and
Let G = (V , E, w) be an undirected weighted graph, where V and E
describe how they can be overcome, and how our methods can be
are the sets of vertices and edges, respectively, and w : E → [0; 1]
extended.
is a function associating a positive weight to each edge. We note
n = |V | the number of vertices, and w(e) the weight of edge e ∈ E.
2 METHODS Consider a function s : E → {+, −} that assigns a sign to each edge
In this section, we first describe how we extract the signed networks in E. An undirected weighted graph G together with a function s
from the raw data describing the votes (Subsection 2.1). We then is called a signed graph, denoted by G = (V , E, w, s). An edge e ∈ E
focus on the methods we use to partition the resulting networks is called negative if s(e) = − and positive if s(e) = +. We note E −
(Subsection 2.2). and E + the sets of negative and positive edges in a signed graph,
respectively.
2.1 Network Extraction The extraction method we use is similar to the one we previously
proposed in [17], with the addition of an optional filtering step,
We first review the raw data we use in this article (Subsection 2.1.1),
which makes it four-stepped.
before describing the method applied to extract the signed networks
The first step consists in selecting a subset of the raw data (or
(Subsection 2.1.2).
possibly all of it). This selection can be made along 4 independent
2.1.1 IYP Dataset. Like in our previous work [17], our row data dimensions: policy domain (e.g. only Foreign Affairs), political group
describe the activity of the MEPs during the 7th term of the EP, (e.g. only S&D), member country (e.g. only France), and time (e.g.
which covers the period 2009-14. They include the vote cast by only the year 2010-11). It is also possible to just consider all the
each MEP for each text considered at the EP. Each MEP is also available data over one or more dimensions, as we previously did
described through his name, country and political group, as well [16, 17]. Considering a large amount of data makes it difficult to
as other personal fields not used in this article. The country cor- perform a qualitative analysis of the results, and to give them an
responds to one of the 28 member states (at this time) in which appropriate interpretation. For this reason, in this article we focus
the MEP was elected. The political group is a transnational parlia- on a few countries and domains, and consider each parliamentary
mentary coalition. The groups of the 7th term were, by order of year separately, as explained in Section 4.
decreasing prevalence: EPP: right/center-right conservatives; S&D: The second step consists in comparing individually all MEPs in
center-left; ALDE: right/center-right neoliberals; G-EFL: left envi- terms of similarity of their voting behaviors, for the selected data.
ronmentalists, progressists and regionalists; ECR: right euroskeptics For this purpose, we use a variant of the vote similarity measures
and anti-federalists; GUE-NGL: left/far-left, socialists and commu- presented in [17]. For a pair of MEPs u and v and a given text
nists; EFD: right/far-right euroskeptics; NI: MEPs not belonging to t, this measure noted Simt (u, v) takes the value: +1 if the MEPs
any of the other groups (mainly far-right MEPs). Each text is itself agree (both votes are For or Against) ; −1 if they disagree (one
associated to one among 21 specific policy domains (see [17] for vote is For, the other is Against) ; and 0 if at least one MEP votes
the complete list). Abstention. This measure is processed for each text and averaged
In theory, these data are publicly available on the official EP web- to get the overall similarity between two MEPs, resulting in a real
site3 , however, in practice, accessing them is difficult. Fortunately, value noted Sim(u, v) and ranging from −1 (the considered MEPs
various institutions did all the work of compiling them, and provide always disagree) to +1 (they always agree). The texts for which
them under a convenient form. The dataset we used in [17] turned at least one MEP is Absent are not included in this average. We
out to be incomplete: most votes from the last year of the considered process the average vote similarity for every pair of active MEPs
term (2013-14) are missing, as well as all the amendment-related (i.e. MEPs who voted at least once in the selected data).
votes. For this reason, for the present work we switched to another The third step, which was not enforced in [16, 17], consists in fil-
tering the similarity values in order to remove the ones too close to
zero, which are deemed non-significant. Instead of using arbitrary
3 http://www.europarl.europa.eu/ 4 http://www.itsyourparliament.eu/
2
thresholds, we propose an automatic method, consisting in apply- The Imbalance I (P) of a partition P is defined as the total weight
ing k-means separately to the negative similarity values, and to the of positive edges located between clusters, and negative edges
positive ones, with k = 2. This allows distinguishing the values that located inside them, i.e.
Ω + (Ci , C j ).
Õ Õ
are close to zero from the others. Indirectly, this amounts to esti- I (P) = Ω− (Ci , Ci ) + (1)
mating the best thresholds θ − and θ + such that the similarity range 1≤i ≤k 1≤i,j ≤k
is split in 4 intervals: [−1; +1] = {[−1; θ − ]; ]θ − ; 0[; [0; θ + [; [θ + ; +1]}.
The filtering is performed by setting all values in {]θ − ; 0[; [0; θ + [} Problem 2.1 (CC problem). For a signed graph G = (V , E, w, s),
(i.e. both central intervals) to zero. the Correlation Clustering problem consists in finding a partition P
The fourth and final step allows to build the signed network of V such that the imbalance I (P) is minimized.
based on the remaining similarity values. It consists in creating a In [8], the definition of a structurally balanced signed graph
vertex to represent each active MEP, and connecting by an edge all was extended in order to include relevant processes (polarization,
pairs of MEPs whose similarity is non-zero. The sign and weight of mediation, differential popularity and subgroup internal hostility)
an edge e connecting two vertices u and v are defined as the absolute that are counted in Eq. (1) as violations of the structural balance.
value and sign of their similarity, respectively: w(e) = |Sim(u, v)| According to this new definition, a signed graph is considered
and s(e) = sдn(Sim(u, v)). The filtering conducted at the third step relaxed k-balanced if it can be l-partitioned, with l ≤ k, in such a
amounts to suppressing the weakest links, and the produced graph way that: 1) all the edges within a given cluster have the same sign
is consequently not fully connected (unlike that from [17]). If these (not necessarily +) ; and 2) all the edges between two given clusters
links indeed correspond to noise, we expect their removal to both have the same sign (not necessarily −).
lighten the computational load and ease the interpretation of the Using this new definition, the structural balance was generalized
results. to a version named Relaxed Structural Balance [8], resulting in a new
As explained in Section 2.1.1, it is possible to play with the 4 definition for the imbalance of a graph partition. For an l-partition
dimensions present in our raw data (domain, group, country, and P = {C 1 , ..., Cl }, the Relaxed Imbalance RI (P) is defined as
time) and used during the selection step, to obtain a number of
min{Ω+ (Ci , Ci ), Ω − (Ci , Ci )}
Õ
different signed networks. There are 21 policy domains, and we also RI (P) = (2)
1≤i ≤l
consider all documents independently from their domain. The term
min{Ω+ (Ci , C j ), Ω − (Ci , C j )}.
Õ
is 5-year long (2009-2014), and we consider each year separately as + (3)
well as the whole term. There are 28 countries and 8 political groups, 1≤i,j ≤l
and in both cases we consider MEPs from specific countries/groups This generalized imbalance defines a new criteria to evaluate
separately, as well as all MEPs at once. In theory, this amounts to a balancing in a signed graph, and gives rise to the following graph
total of 4884 different modalities. In practice, some of them are not clustering problem.
usable (e.g. some groups are not represented in certain countries,
Problem 2.2 (RCC problem). Let G = (V , E, w, s) be a signed graph,
resulting in an empty data selection after the first step), so our
and k an integer value satisfying 1 ≤ k ≤ n. The Relaxed Correlation
dataset contains 4150 instances of signed networks.
Clustering problem consists in finding an l-partition P of V , with
l ≤ k, such that the relaxed imbalance RI (P) is minimized.
2.2 Graph Partitioning
It is worth noticing that, for a given graph, the RCC solution is
We briefly describe the two partitioning methods, able of handling necessarily equally or more balanced than the CC one.
signed graphs, which we selected to analyze our signed networks. Both CC and RCC problems have been proved to be N P-hard [2,
Let us first formalize a few additional concepts. A graph partition 11]. Integer programming-based methods can be used to solve both
P = {C 1 , ..., Ck } (1 ≤ k ≤ n) is a k-partition of V , i.e. a division of problems to optimality [1, 11], and numerical experiments have
V into k non-overlapping and non-empty subsets Ci (1 ≤ i ≤ k) shown that the additional parameter k, in the RCC definition, turns
called clusters. For σ ∈ {+, −}, the set of positive or negative edges the graph clustering problem more difficult to solve numerically
(depending on σ ) connecting two clusters Ci , C j ∈ P (1 ≤ i, j ≤ k) [11]. Both problems can be efficiently solved by the Iterated Local
is E σ [Ci : C j ] = {(u, v) ∈ E σ | u ∈ Ci , v ∈ C j }, and its total weight Search (ILS) procedures described in [15], namely ILS-CC and ILS-
is given by Ω σ (Ci , C j ) = e ∈E σ [Ci :C j ] w(e).
Í
RCC. As a baseline, we also use the exact algorithm described in
One appropriate way of studying the structural balance of a [1] to solve CC, which we call Ex-CC in the rest of the article.
signed network G = (V , E, w, s) is by solving the Correlation Clus- We apply both ILS procedures in order to identify structural
tering problem (CC). In its original version [2], and consistently balanced partitions in each extracted signed network. The following
with the definition of structural balance given earlier in Section strategy was adopted to set the parameter k, which is an input of
1, it consists in finding a partition of the set of vertices V which the RCC problem. First, we apply ILS-CC and obtain an optimal
maximizes both the number of positive links located inside the partition containing k ′ clusters. Second, we apply ILS-RCC to the
clusters, and that of negative links located between them. A relaxed same network with parameter k ∈ {k ′, k ′ + 1, k ′ + 2}, producing 3
version called Relaxed Correlation Clustering problem (RCC) [3, 8] different network partitions. We consider and compare all obtained
consists in searching a partition of V into at most k clusters, while partitions when interpreting our results relatively to the studied
allowing special patterns of relationships originally considered as system .
violations of the structural balance [8]. Both problems are formally In the experimental part, we compare partitions using the Nor-
described next. malized Mutual Information (NMI), a measure widespread in the
3
●
●
● Unfiltered Graphs ●
● Filtered Graphs
fields of clustering [18] and community detection [12]. It ranges ●
●
●●
●
●
●●
●
●
●●
●
●
●
●
●
●●
●
●
●
● Negative links
●
●
●●
●
●
●●
●
●
●●
●
●
●
●
●
● Negative links
10000
●●
●
● ●
10000
●●
●
●
● ●
●
●●
● ● ●
●
●●
●
●
●
●
● Positive links ●
●● Positive links
from 0 (the partitions are completely different) to 1 (they are exactly ●
●●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●●
●●
● ●
●●
●●●
●
●●
●
●●●●
●
●
●
●
●
●●
●
●
●
●
●
●●
●●
●
●●
●
●
●●
●
●●
●
●● ●
●●
●●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●●
●
●
●●
●
●
●●
●
●
●●
●
●
●●
●● ●● ●●
●
●●
●
●
●
●●
●
●
●●
●●
●
●● ● ●●
●●
●●
●●●
●●
●●● ●●●●●●
●●
●
similar). This measure takes into account the possible hierarchical ●●● ● ●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●●
●
● ●●
●
●●
●
●●●
●● ●
●
●
●●
●
●
●
●
●
●
●
●
●
●●
●
●
●●
●●
●●
1000
●● ● ●● ●
●● ●
●●
●●
● ●
●●
●
● ●●● ●● ●
●
●●
●
1000
● ● ● ●
●●● ●●●●
●
●
●●
● ●● ●●
●
●●
●
●●
●● ● ● ●
●●●
●●●
●
●●
●●
●
●
● ●●● ● ●●
●●●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●●
●
●
● ● ●
●
●
●●
●●●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●●
●
●●
●
●
●
●
●
●●
●●
●
●●
● ● ●●●●●
●
●
●●
●
●●●
●
●●
●
●
●
●
●
●
●
●●
●
●●
●
●●
●
●
●●
●
●
●●
●
●
●
●
●●
●
●● ● ● ● ●● ●
● ● ● ●● ●
●●
●
●
●●
●●● ●● ● ●●
●●●
●
●●
●●● ● ● ●
●
● ●●
●●
●● ● ●●●●● ●● ● ●
●●●
● ●
●●
●● ●
●●●
●●
●●
Number of links
●
Number of links
● ●● ●● ●●●
● ● ● ● ● ●●●● ●
● ●
●
●● ●●
●
●
● ●●
● ●●● ●
●● ●
●
●
●●●
●●●
●
●●●
●●
●
●●
●
●
●
●
●●● ●●
●
●●●
●
●●
●
●
●
●●
●
●
●
●
● ● ●● ● ● ●●● ●●●●●
● ●
●●●
●●●●
●
●●
●
●●●
●●●●●
●●
●
●
●
●
●
●
●
●●
●
●●
●
●●
●●● ● ●
●● ●●
●
●●●●●●●
●
●●
●
●●●
● ●●●
● ●●
●
●
●
● ●
●●●●
●● ●● ●●
●
●
●
●
●●
●●
●
●●●
●
●●
●●●
●
●
●●
●●●●
●
●
●
●
●●
●●
●
●●●●●● ● ●●
● ●
●
●●
●●●●● ●
●
●
●●
●
● ●
●● ●
●● ● ●
●●● ●●● ●
●●●●●●
● ●
●
●
●●
●●
●
●
●●
●
●●
●●
●
●
●
●
●
●
●
●●
●
●●
● ●
●●●
● ● ●● ●●
●●●●
● ●●●
● ●● ●●●
●
●●●●
●
●
●●
●
●
●
●●
●
●
●
●●
●
●●
●
●●
●
● ●
●
●
●● ● ●●●
●●
●
● ● ●●●
●●
●
●
●
●● ●
● ●●
●●●●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●●
● ●
relations between the considered partitions. For instance, if one ●●
●●
● ●
●
●●● ●
●●
●
●●
●●●●
●● ●●
●
●
● ● ●●●
●●
●
●
●
●
● ●●●
● ●●●
●
● ● ●●●
●●●●●
●
●
● ●●
●
●
●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●●●
●
●
●
●
●
●
●
●●●
●
●
●
●●●
●
●
●●●
●
●●
●●
●
●●●
●●●
●
●
●●
●
●●
●
●● ● ●
●
●● ● ● ●●●●
●● ● ●●●●
●●
●●
●
●●
●●●
●
●
●
●●●
●
● ●
●●
●
●● ●
●
●●
● ●
●
●●
●
●
●
●
●●
●
● ●●●
●
●●●
●
●
●
●
●
● ●●
●●
●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●●
●
●
●
●●
●●
●●
●●
●
●
●●●
●
●
●
●●●
●
●
● ●
●
●●
●●
● ●
●●
●●●●●●
● ● ●●
● ● ●●● ●
●
●
● ●● ●●
●●● ●
●● ●●
● ●●
● ●●●●
●
●
●
●● ●
●●●●
●●●
●
●●●●
●
●
●
●●●
●
●
●●
●
●
●● ●●
●●
●
●●●
●● ●
●
●
●
●●●
●
●
●
●
●
●
●
●
●●
●
●
●●
●
●
●
●
●
●●
●
●
●
●
●
●●
●●●
●
●
●●
●
●●
●●
●
●●
●●
●● ●
●●● ●
●
●
●●
●
●
●
●●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●●
●
●●
●
●
●
●●
● ●● ● ● ●
● ● ●
●
●●
●
●●
●
●●
●●
●
●
●
●
●
●
●●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●●
●
●●
●
●
●
●
●
●●
●
●
●
●
●●
●
●
●
●●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●●
●
●
●●
●
●
●
●●
●
●
●
●●●
●●
●
●
●●
●
●
●●
●
●
●●
●●
●
●●
●
●●
●●
●●
●●
●● ●● ● ● ●● ● ●● ●●
● ●
●● ●●●
● ● ● ● ●●
● ●●●
●●●
●
●●●
●
●●●
●●
● ●
●
● ● ● ●
● ● ●● ●● ●
● ●●● ● ●● ●●● ● ●● ● ●
●●●
●
●●
●
●
●●
●●
●●
●●
●●
●
●●
●● ●●●●
●●●●
●
● ●
●
●●
●●
●
●●
●
●
●●
●●
●
●●
●
●●●
●●●
●●
●
●●
●●
●
●●●
●
●
●●
●
●
●●●● ● ● ● ● ● ●●
●● ●●●● ● ● ● ● ●● ●● ● ●
● ●
●●●
●
●
●●
● ●
●●●
●
●●●●
●
●
●●
●●
●●●●
●
●● ●●● ● ● ●● ●●
●
●●
●●
●●
●
●
●●
●
●●
●
●
●●
●
●●
●
●
●●
●
●●
●●●●●
●●
●●●
●●●
●
●
●●
●●●
●
● ●
●
●
●●
●●
●●●●
●
●●●●●
●
●
●●●
●
●
●●
●
●
●●
●●●●
●●
●
●●
●●
●
●
●●
●● ●●●● ●●● ●● ●●● ●●● ● ●
● ●●●
●
●●
●●
●●●
●
●●●
●●●
●●●
●
●
●
●●
●
●
●
●●
●
●●
●
●
●●
●●
●
●
●●
●●
●
●●●
● ●● ● ●● ● ●● ● ●● ●● ● ● ● ●● ● ● ● ●
●●● ●● ● ● ● ●
●●●● ●●●●● ● ●
●●●● ●
●
100
●● ●● ●●● ●●
● ● ●● ● ● ● ●
●
●● ●●
●● ● ● ●● ● ● ● ●●●●● ●● ●●●
100
●● ● ● ●
●●●
● ● ● ●● ● ● ● ●● ● ● ●●●
●● ●●●● ● ●● ● ●
●●
●●● ●
● ●●●●●● ●●●● ● ●● ●
●● ●● ●●● ●● ● ● ●●
● ●
●●
● ●
●●
●●
●●●
●●● ● ● ●
●●●●●●●
●●●● ● ● ●●
●
●
●●
●●
●
●●●
●
●●
●●●
●
●●
●●
● ●● ● ● ●● ● ●● ●●● ● ● ●● ● ●
●●●
● ●
●
●
● ●●●
●●●●
●●●
●●
●●●
●
●●
●●
●
●
●●
●
●●
●
●●●
●●
●●●
●
●●
●●●
●
cluster from the first partition corresponds to two distinct clusters ●
●
●
●●
●●
●●
●●
● ●●
●
●●
●●● ●
● ●●● ● ●
●
● ● ●●● ●
●●●
●●
●
● ●●
●
●
●
●
●
●
●●●
●
●●
● ●
● ●
●
● ● ●●
●
●●
●
●●
●
●
●●●
●●●
●
●●●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●●
●
●
●●
●
●
●
●
●●
●●●
●
●●●●●●
●●
●●●●
●●
●
●
●
● ●●
●
● ●● ●●
● ● ●●●
●
● ●
●●
●
●
●
●
● ●● ●● ●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●●
●
●
●●
●
●
●
●
●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●●
●●
●●
●
●
●●●
●
●
●●
●
●
●
●●●●
●●●●●●
●
●
●
●
●
●
●
●
●
●●
●●
●●
●
●
●
●
●
●
●●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●●●
●
●●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
● ●●
●
●
●●
●
●●●
●●
●●●
●
●●
●
●●
●
●
●
●
●
●
●
●●
●●
●●●
●
●
●
●
●
●
●
●●●
●
●
●
●
●
●● ●●
●
●
●
●
●
●●
●
●●●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●●
●●
●
●
●
●
●
●
●
●
●●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●● ●
●
●
●
●
●
●● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●●
●
●● ●
● ●
●●● ● ●
●●●
● ●●
●●
●●
● ●
●●●●
●●
●
●●●
●
●
●
●●
●●
●
●
●●
●
● ●●
●●
●
●
●
●● ●
●
● ● ●●
●
●
●●
●
●
● ●
●●●
●
●
●
● ● ●
●●●●●●
●
●
●
● ●●●
●
●
●
●
●●
●●
● ●●
●●● ●
● ●●●
●●●
●
●
●
●
●●
●
●●●●●
●●
●
●●
●●●
●●●
●
●●
●●
●
●● ●
●
●●
● ●●
● ●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●●●
●
●
●
●
●
●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●●
●
●
●●●
●
● ● ●●●● ● ● ●
● ●● ●● ●
●
●
●●●●● ● ● ●●
● ●
● ●● ●●
●●●
● ●●
●●
●
●●●●● ● ●●●
●●●
●●
●
● ●●
●
●●
●● ● ●
● ●●●●●●●●
●● ●
● ●
●
● ● ● ●● ●●● ● ● ●●● ●
● ●●●● ●
● ●●● ●●
● ●● ●● ●
● ●●
● ●●●
● ●● ●● ● ●
● ●●●●●●●
●●●
●●
●
●●
●●
●
●●●
● ●●● ●●
● ●● ●●●●●●●●●● ● ●
●●
● ●
●●
●
●
●
●●
●
● ●
●●●
●
●
● ●
●●● ●●
●●● ●●
●●●●● ●●
●●●●
●● ● ●● ● ● ●
●
●● ●● ●
● ● ● ●●● ●●●
●●● ● ●●● ●
● ●
●
●●
●
●●●
● ●●●●
● ●
●● ● ●
● ●
●●●
●
●●●●
●●
● ●
●●
●
●
●●
●●
●
●
●
●
●●
●●
●
●
●●
●
●●
●
●●
●
●
●●
●
●●
●
●
●●
● ● ● ● ●●●●● ● ●● ●
●
● ●●
●●
●● ● ●
●
● ●● ●
●
● ●
●●
● ●
●
●
●●
●
●
● ●●●●●● ●
●●●●
● ●●●
●
●
● ● ● ●
● ●●●● ●●
●● ●
●●
●
●●● ● ● ●● ●●
● ● ●●● ●●●●● ●●●●
● ●
●
● ●
● ● ●●
● ● ●● ●●
●
●● ●●
●
●
●●
●
●●●●●
●●●
●●
●●
● ●●● ●
●●●
● ●●
● ●●●●●
●
● ●●● ●●●
●●
● ●●●●
●●
●●
●●●
●
●●
●●
●
●●
●
●
●●●● ● ● ●●
●●●
● ●●●●● ●●● ●
● ●
●● ●●●●
●
●●● ●
●● ● ●
●●●●●● ●●● ●● ● ●● ● ● ●●
●●
●● ●● ●● ●● ●●
●
●
●●●● ●● ● ● ●●
●●
●
●● ● ●
●
● ●●●● ●● ●●● ●●●● ●
● ●
●●●
●●●
●●●● ●
● ● ●●●●
●●
●
●● ●●
●●
●●
●
●●
●
●
●
●●
●
●
●
●●
●
●●
●
●●
●●
●● ●●● ●
● ●● ● ●● ●●
●●● ● ●● ● ● ●
●●●● ●
●●●
● ● ●
●●●
● ● ●●● ●●
●●● ●●
●● ●● ●●● ●
● ●● ● ●●●
●
●
●
●●
●●
●●
●●●
●
●●
●
● ●● ● ● ●● ● ●
● ●● ● ● ●
●●
● ●● ●● ●●●● ●● ●
●● ●● ●● ●●●● ●●● ●●●●●
●● ● ●●●●● ●●● ●● ●
●●●●
●
●
●●
●●
●
●
●●
●●
●●
●
in the second partition, the penalty will be lower than if there is no ●●
●●
●
●
●●● ● ●●●●
●
●
●●● ●●● ● ●●
● ●●
●
●
●
●
●
●●
●
●● ● ●●
● ● ●
●● ●●
● ●
●●
● ●●
● ●● ●
●
● ●●
● ●● ●●
●●
●
●
●
●
●
●
●
●
●
●
●●●
●●●●
●
●
●
●●●
●
●
●
●● ●●●
●
●●
●
●
● ● ●●
●
●
●
●●
●
●●●●
●●●●
● ●
●
●
●●
●●
●
●
●
●●
●
●
●●●
●●●
●●●
●●
●●●
●
●
●●●
●
●
●
●
●
●
●
●
●●
●●●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●●
●● ●
●●●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●●●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●●
●
●●
●
●●
●
●●
●●
●●●
●●
●
●
●
●
●
●
●
●
●
●●●
●
●
●●
●●
●
●
●
●
●
●
●
●●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●●
●● ●
●
●
●●
● ●
●
●●
●
●●
●●
●
●
●
●●
●●
●
●
●
● ●● ●
●●
●
●
●
●
●●●●●
●● ●
● ●●
●
●
●
●
●
●
●
●
●
●
●●● ●
●
●
●
●
●●
●
●●●
●
●
●●
●●
●●
●
●
●
●●●
●
●
●
●●
●
●
●
●●
●●
●●
●●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●● ●● ●●
●● ● ●
● ●●● ●●●●
●●●● ●●●
● ● ● ● ●●
● ● ●●●●●● ●●●● ● ●
● ● ●● ● ●
●●●●●●●●●●●●
●●
●●
●●●
●
●
●● ● ●●
●●● ●
● ●
●
●●● ● ●●
●●
●
●
●
● ● ●●
●
● ●
●
●
●
● ●●
●●
●● ●
●● ●
●
●
●● ● ●
●● ●●
● ●
●
●
●
●●
●
●● ●
●●●
●●●
●
●●●
●
●
●
●●
●
●
●●●
●● ●
●
●
●●
●
●
●●●
●
●
●
●
●
●
●
●
●●
●●
●
●
●●
●●
●●
●● ●
●
●●●
●
●
●●
●●●●
●●
●
●
●
●
●
●●
●●
●●
●
●
●
●●●
● ●●
●●●
●
●
●●
●●
●
●●
●
●●
●
●●
●●
●●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●●
●●●
●
●
●
●●
●
●●●
●
●
●●●
●
●
●
●
●●●
●
●●
●
●●
●
●
●
●●
●
●
●
●●
●●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●●
●●
●
●
●
●
●●
●
●
●●
●
●
●
●
●●
●
●●
●
●
●
●
●●●
●●
●●
●
●●
●
●●●
●●
●
●
●
●●
● ●
●
●
●●●
●
●●
●●●
●
●
●
●
●
●
●
●●
●
●●
●●
●●●
●
●
●
●●
●●
●●●
●
●●
●●●
●●
●●●
●
●● ●
●
●
●
●
●●
● ●●●
●●●● ●
●●●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●●
●●●●● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●●
●
●
10
10
● ●●
●● ●●
● ●●
●● ● ● ●●●● ●●●● ●●
● ● ● ● ●●●●
● ●●
● ●●
● ●●
●●● ●
●●● ●
● ●●● ●●●●●●●●● ● ●●
●
●
●
●
●●
●
●
●
●
●
●
●
●●
●
●● ●●
●
● ●
●
●●●
●
●●
●
●●
●●
●
●
●
●
●
●
●
●
●●●
●●●
●
●
●
●
●●
●●●
●
●
●
●
●
●
● ●
●●●●●
●● ●
●●
●
●
●●
●
●
●
●●
●●
●●●
●●
●
●●
●
● ●
●
●●
●
●●
●
●●
●
● ●
●●● ●● ● ●
●●●●●● ●●
●● ●●
●●●● ●●● ●
● ●●● ●●● ●●●
●●●●●●●●●
● ●
● ●● ●●●●●
●
●●
● ●●
●
●●● ●●●● ●
●● ● ●● ●●●●
●● ●●●●
●●●● ●
●●
●
●
●●●●
●●●● ●
●
●
●●●
●●
●●
●●
●
●
●●
●
●●
●
● ●
●
●
● ●
●●●●●● ●●●
● ●
●●● ●
● ●●●
●●●
●
●●
●
●
●
●
●
●●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●●●
●
●●
●
●●● ●● ● ● ●● ● ● ●● ●
● ●●● ●● ●● ●●● ●●● ● ●●● ●●●●
●●
●●
●●●●●●●●●●●● ● ● ●
●
●
●●
●
●
● ●●
●
● ●●
●
●
●●
●●
● ● ● ●●● ●● ●
● ●● ● ●●●●● ●● ●
●● ● ●●● ●
●●●● ●●●●●●● ●●●
●●● ●●●●●●●● ● ●●● ●●●●●●
●●
●●
●
●●
●
● ● ●●● ●●●● ●
● ●●● ●● ●● ● ● ● ● ● ● ● ● ●
● ●● ●
● ●
●
● ●
●● ● ●●●
●●● ● ●●●●
● ● ●●●● ●
●● ● ●●
● ● ● ● ●●● ●● ● ● ● ● ●●●● ●● ●●
●● ● ● ● ●●● ● ● ●●●● ●● ●● ●●●●●● ●●● ●●●●●●●●●●
●●●●●● ● ●●●● ●●● ●●●●●
●●
●●●
●●●
●●
●
●
●●
●
match at all [6]. ● ●● ● ●●
● ●●
●●●
●●●● ●
●
●
●●● ●●
●●●● ●● ●●
●●
●
●
●
● ●●●
● ●● ●
●●●
●●
●
●
●●
●
●●●● ●●●
● ●●●● ●
●● ● ●
●●●● ● ● ●●
●●● ●
●●
●
●●
●
●
●●
●●
● ●
●
●
●
● ●●●●●
●●●● ● ●●●
●●● ● ●●● ●● ●●● ●
●●● ●●
●●●●● ● ●●
●●●
●● ●
● ●●
●●
● ● ●
●● ●●
●●●●●
●●
●●●
●
●
●
●● ●●
●●
● ●●
●●●●
●
● ●●
●
●● ●
●
●
●
●
●●
●
●● ●●
●●●●●
●●
●●●●●
●●
●
●●●●
●
●
●●
●●●●
●●●
●●●
●●●
●
●●
●
●
●● ●●
●●
●●●
●●
● ●●
●●●
● ●●
●●
●
●
●●●
●●●
●●●●●
●●●
●
●
● ●●
●●
●
●●
●●
●● ●
●●●●
●●●●
●
●
●
●
●●
●
●
●●
●
●●
●
●●
●
●
●
●
●●
●
●
●●●
● ●
●●●
●
●
●●●●●
● ●●
●
●●●
●●
●●
●
●●
●●●
●
● ●
●●
●●
●
●●
●
●
●● ● ●
● ●● ●
●●
●●●●
●
●●
●● ●●
●
●●●●
●●
● ●●
●● ●
● ●●● ●●
●●
● ●
● ●
● ● ●●●●●
●●
●●●●
●●
●
●●
●●● ●
●●●
●●●
●
●
●●
● ●
●●●●
●●●
●●
●
● ● ● ●●
●● ●●●
●
●
● ●● ●●●
● ●●
● ●●
●● ●●
●
●●●●●●
●●●
● ●● ●
● ●● ●●●●●●
●● ● ●●●●
● ●●● ●●● ●
●
●●
●
●●●
●●●●●
●●
●●
●●●
●●
●●
●
●●
●●
●●
● ●
● ●●
● ●●●
●●●●
●●●●
●● ●
●
●
●
●
●
●●
●
●● ●
●●
● ●●
●●
●●
●●●
●●●●
●
●●●●
●●●
●●
●●
●●
●●
●●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●●●●
●
●●
●
●●
●
●
●
●
●
● ●●●
●●
●
●●
●●
●●
●●●
●
●
●●●●
●
●●●●●●●
●●
●
●
●
●
●●
●
●
●
●●●
●
●●●
●
●●●●
●
●
●
●
●●
●●
●●●
●●●●
●●
●
●●
●
●
● ●●●●
●
●
●●●●
●●●
●●●
●
●
●●●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
● ●
●
●
●●● ● ●●●●●●● ●●● ●
●●●● ●●
●●●●
● ● ●● ●
●●●●●
●●●
● ●●●
●● ●●●
● ● ● ●● ●
● ● ●
●● ● ●● ●●
●●●●●
● ●●●
●● ● ●●
●
●●●
●
●●●● ●●
●●
● ●● ● ●
●
●●
●●
●
●●
●
●●
●
●●●●
●●●●
●
●●●●
●
●●●●●●●
●
●●
●
●●
● ●
●
●● ●
●●●●
●●●●●●●
●●
●●●
● ●
●
●●●
●●
●●●●
●
● ●●●
●● ●
●● ●
●●●
●
●●●●●
●●●●
●
●●
● ●
●●
●●●●
●●
● ●
●●●
●●●
●●●●●
●●●
●●●
●
●
● ●
●
●●●●●
●
●●●
●●●●●
● ●●
●●●
● ●●
●
●●
●●●●
●●●
●
●
●●
●●●●
●
●●●
●
●●●
●●●
●●
●
●●●
●
1
1
●
●
●●●●
● ●
●●
●●● ●
●
●●
●●
●●
● ●
●●
●●
●●●
●●● ●●
●
●●●
●
●●●●
●
● ●
●●●●
●●●
●
● ● ●● ●●
●● ● ● ●●● ●●●
●●● ●
●●●●
●●●●
●●● ●
●
●●●
●
● ●● ●
●●
●
●●●
●
●
● ●
●
●●
●
●●●
●● ●●●●●●
●
●●
●●
●
●●●
●
●●
●●
●● ●
●
●●
●
●●●
●●●
●●
●
●●
●
●●
●●●
●●
●
●●
●●●●
●
●
● ●●●●
●
●● ●●
●
●●● ●
●
● ●
●●●●
● ●
●●●
● ●●●
● ●
●●
●●●●
●
●●
●●
●
●●
●●●
●
●
●●●●●●
●●●
●●
●●●
●●●
● ●●● ●●●
●●●
● ●
●●●
●
●●●●●
●●
●●
● ●●
●●
●●●
●
●●●
●
●●
●
●●
●●
●
●●
●
●●
●
●●●
●
●●
●
●●●
●
●●
●
●●
●
●●
●
●●
●●
●
●●
●●●
●
●●
●●
●
●●
●
●●●●
●●
●●
●●
●●
●●
●
●●●
●
●●●
3 EXPERIMENTAL ASSESSMENT 0 1000
Graph instances, by decreasing order of total number of links
2000 3000 4000 0 1000
Graph instances, by decreasing order of total number of links
2000 3000 4000
In this section, we first study the effect of the filtering step of our Figure 1: Numbers of positive (green) and negative (red)
extraction process on both the obtained networks and the parti- edges in all unfiltered (left) and filtered (right) networks.
tioning algorithms (Subsection 3.1). We then assess the quality of
the heuristic previously proposed to solve the CC problem (Sub-
section 3.2). Note that the heuristic we use to solve RCC relies the dataset (3%), constituted of very small graphs, and the giant
on exactly the same operators, which is why we do not need to component is also preserved in these cases.
explicitly evaluate it for this problem. For both points (filtering 3.1.2 Effect on the Partitioning Algorithms. According to our
and heuristic), we base our analysis on the 4150 signed network experiments, the filtering step generally leads to a decrease in terms
instances constituting our whole dataset. of partitioning processing time. This effect is more pronounced for
For convenience, we will use the following notations: ExCC(G) graphs whose unfiltered partitioning requires more time, since
and ILSCC(G) are the imbalance values obtained through the corre- faster ones offer little room for improvement. For Ex-CC, filtering
sponding partitioning algorithms, expressed in total edge weight as cuts the processing time by 5–10% in those graphs, whereas for
defined by equation 1. It is sometimes more convenient to discuss ILS-CC it is close to 90%. We now turn to the quality of the detected
an imbalance described in terms of percent of the total link weight clusters. We focus on Ex-CC and ignore ILS-CC, because only the
of the graph, in which case we add a % to our notation. Finally, the analysis of optimal solutions can allow us to assess the true effect
filtered version of a graph G is noted G f . of filtering. We first consider the numbers of clusters that this
algorithm detects. For almost all instances, we observe an increase
3.1 Effect of the Filtering Step in the number of clusters in the filtered graphs. But for a few of
As explained in Section 2.1, we added a filtering step to our previ- them, there is a decrease: this is explained by the fact that removing
ously defined extraction process [17]: the goal of this subsection is an edge can decrease cluster cohesion, if this edge is positive, but
to assess its influence on both the resulting graphs (Subsection 3.1.1) also cluster separation, if it is negative. We have no ground truth
and the partitioning algorithms (Subsection 3.1.2). (group membership is not a reference, as shown in Section 4), so it is
difficult to objectively assess whether an increase in the number of
3.1.1 Effect on the Graphs. The plots from Figure 1 show the
clusters is a good thing or not. However, we can use our knowledge
numbers of positive (in green) and negative (in red) links for each
of the data: since they represent voting behaviors, we expect 1
network in the dataset, without (left-hand plot) and with filtering
cluster if there is a consensus, 2 if there is a clear For/Against
(right-hand plot). On the x axis, the networks are ordered by de-
opposition, and a very few more if some MEPs swing in-between.
creasing number of links. The y axis uses a logarithmic scale for
We observe that on the unfiltered networks Ex-CC detects a single
readability matters. There obviously is a decrease in the numbers
cluster for most networks (55% of them). It seems unlikely that a
of positive and negative links when filtering the graphs (43% of
consensus would emerge that often. After filtering, this proportion
the links are removed, in average). However it is worth noticing
drops to 38%, which seems more reasonable.
that the general distribution does not change (if anything, it is
smoothed) and the proportions of positive and negative links are Ex-CC
ILS-CC
25000
also preserved. This is even truer when considering weights instead
3000
3000
Execution time (s)
of link counts (not plotted here), since the filtering removes the
15000
2000
2000
Frequency
Frequency
weaker links (only 26% of the network weight, in average). This
1000
1000
point is important, because the considered partitioning methods
5000
take weights into account.
0
0
0
0.0 0.2 0.4 0.6 0.8 1.0 −0.15 −0.10 −0.05 0.00 0.05 0 200 400 600 800
Another important point besides link distribution is graph con- Normalized Mutual Information Imbalance Difference Graph size (nodes)
nectivity. We focus on the giant component of the unfiltered graphs Figure 2: Distribution of the NMI (left) and of imbalance dif-
(which by definition are almost completely connected) and study ference (center) between partitions detected by Ex-CC with
how they are affected by the filtering step. For the overwhelming vs. without filtering. On the right: execution time of Ex-CC
majority of the instances (66%), filtering does not make the graph and ILS-CC as a function of the network size.
disconnected. For 23% (resp. 8%) of them, it splits them in 2 (resp. 3)
components. But in this case, the larger component represent 87% But two partitions can contain the same number of clusters while
(resp. 76%) of the original component, which means we still have being very different (and oppositely: contain relatively different
one giant component. Filtering splits the rest of the graphs into up numbers of clusters, but be hierarchically related). It is thus nec-
to 10 components, but this represents a very small proportion of essary to assess how similar two solutions on an unfiltered graph
4
and its filtered counterpart are. For this purpose, we use the NMI (vertical dashed line in the figure), as the necessary computing time
(cf. Subsection 2.2), which is showed in the left plot of Figure 2. The passes the 1 hour limit (shown with a horizontal dashed line). We
NMI is close to 1 for most instances (≥ 0.8 for 61% of them), mean- could not finish processing networks larger than 600 nodes, which
ing the identified partitions are not affected much by the filtering, is why the line is interrupted. On the contrary, ILS-CC is very fast
despite the previously observed variation in the number of clusters. even for the largest graphs: the time needed is of the order of a few
We now turn to the quality of the partitions expressed in terms minutes (142.48 s at most). Note that the quality of the estimated
of imbalance. The center plot in Figure 2 displays the distribution partitions are also very good, similar to what was described in the
of ExCC%(G) − ExCC%(G f ), i.e. the difference of percent imbalance previous subsection.
between the partitions detected on an unfiltered graph vs. the
corresponding filtered graph. The values are distributed around 0, 4 INTERPRETATION OF SPECIFIC CASES
meaning the quality in terms of imbalance does not change much
The assessment conducted in the previous section was purely quan-
when filtering. Based on the previous observations, we can conclude
titative, and based on the whole dataset. In order to explore the
the filtering step only marginally affects the partitions detected by
usefulness of signed graph partitioning in a more qualitative way,
Ex-CC.
we now focus on a few specific cases of interest. We discuss the
results obtained while solving both CC and RCC on the networks
3.2 Evaluation of the Heuristic representing French and Italian MEPs, for 2 policy domains: Agri-
We now turn to the evaluation of ILS-CC, the heuristic method pro- culture & Rural Development (AGRI) and Economic & Monetary
posed to solve the CC problem. We consider two aspects: the quality Affairs (ECON). We chose those topics because of their potentially
of the identified partitions, in terms of imbalance, and the gain in polarizing nature: AGRI because the Common Agricultural Policy
computational time. We use the parameter values recommended (CAP) has historically been of utmost importance for France due
by the authors of the algorithm [15]. Based on the conclusion of to the prevalence of the agricultural sector in its economy, but a
the previous subsection, we apply the algorithm to the filtered part of the population wants to leave the industrial model of pro-
networks only. duction; and ECON because the subprime mortgage crisis started
just before the considered term. We selected France (FR) because
4000
4000
* ILS−CC
* Ex−CC of our knowledge of its politics, whereas Italy (IT) is interesting as
Number of clusters detected by the algorithm
15
*
*
3000
3000
*
*
*
a reference, since it has roughly the same number of MEPs, and a
Frequency
Frequency
10
**
2000
relatively close culture. Moreover, for each case, we focus on the
2000
**
**
****
********
year for which the results are the most illustrative.
1000
1000
*******************
5
***********************************
*******************************************************
****************************************************************
********************************************************************************************************************
In the rest of this section, we exhibit two types of graphs: indi-
0
0
0 1000
Graph instances, by decreasing number of Ex-CC clusters
2000 3000 4000 0.0 0.2 0.4 0.6 0.8
Normalized Mutual Information
1.0 0.00 0.02 0.04 0.06 0.08
Imbalance difference
0.10
vidual vs. cluster networks. In an individual network (Figures 4a,e
Figure 3: Comparison of Ex-CC and ILS-CC: number of clus- and 5a,e), vertices represent MEPs and edges represent filtered vote
ters (left), distribution of NMI (center) and of Imbalance dif- similarity values. We use a circular layout, and gather MEPs by
ference (right). political group. Each group is characterized by a color: GUE-NGL
(red), G-ELF (green), S&D (pink), ALDE (orange), EPP (light blue),
ECR (dark blue), EFD (purple) and NI (brown). In a cluster network
Figure 3 displays the obtained results. The left plot shows the
(Figures 4b-d,f-g and 5b-d,f-g), each vertex represents a cluster, and
numbers of clusters detected by Ex-CC (in blue) and ILS-CC (or-
each positive (resp. negative) edge corresponds to the set of all
ange). The networks are ordered by decreasing number of Ex-CC
individual positive (resp. negative) edges between the MEPs consti-
clusters. One can observe that the approximate approach gets very
tuting these clusters. For each cluster, we indicate the groups of the
close to Ex-CC. The center plot displays the NMI distribution, and
MEPs constituting it, and its proportions of internal positive and
we see that in 83% of the cases, ILS-CC identifies a partition very
negative links, relatively to the total network weight. The cluster
similar to the optimal one (N MI ≥ .8). The right plot is the distri-
itself is represented by a pie chart also reflecting these proportions.
bution of imbalance difference ILSCC%(G f ) − ExCC%(G f ), which
Similar proportions are provided also for each edge. Finally, in both
shows that the results output by ILS-CC are optimal or near-optimal
types of graphs, positive (resp. negative) edges are drawn in green
for almost all instances (98% of the cases). Qualitatively speaking,
(resp. red).
the heuristic leads to excellent approximations on these data.
We now turn to the computational gain of the heuristic. The
right plot in Figure 2 shows the evolution of the processing times 4.1 Agriculture & Rural Development
for both Ex-CC (orange) and ILS-CC (blue), expressed in seconds, For AGRI, we focus on the year 2012-13. The top plots in Figure4
as a function of the number of nodes in the processed network. We represent the network of the French MEPs, and 3 different partitions
used a 24-core AMD Opteron 2.6 GHz CPU with 512 GB RAM. The estimated for this network. The first partition (b) is the optimal
benchmark was generated randomly by sampling an increasing solution to CC, which contains 3 clusters and has an imbalance of
number of nodes from the largest unfiltered network. The obtained 14.18 (1.35% of the total weight). There are two large clusters of
sizes range from 10 to 850 nodes, by 10-node steps. Since consecu- similar size: the left one is largely dominated by the environmen-
tive graphs are independently drawn, we expect some fluctuations talists (G-EFL) and also contains the radical left (GUE-NGL) and
in the obtained durations. Our first observation is that it becomes NI ; and the right cluster contains the center-left (S&D), right and
very hard for Ex-CC to solve instances larger than 450 vertices center-right (EPP and ALDE) groups. Both clusters have a majority
5
ALDE (1) 88.15 (8.44%)
G-EFL (16) 0.00 (0.00%) G-EFL (14)
GUE-NGL (5) ALDE (1)
150.20 (14.38%) NI (3) 108.12 (10.35%) G-EFL (15)
0.00 (0.00%) 0.00 (0.00%) GUE-NGL (1)
14.1
)
8%
8 (1
.7
.36
(4
%) ALDE (3)
.9
ALDE (5) EFD (1)
–4
49
ALDE (3) EPP (30)
2.
EPP (30) EPP (29) G-EFL (2) GUE-NGL (4)
3
–42 –42
7
S&D (13) .90 GUE-NGL (1) GUE-NGL (1) NI (2)
(4
.37
.0
(4 (4.1 NI (1) S&D (13)
6%
.06 1%
–0.71 (0.07%)
%)
47.39 (4.54%)
)
)
64.70 (6.19%)
837.06 (80.14%) 2%) 392.86 (37.61%)
0.00 (0.00%) 0.0 0.00 (0.00%)
9( 5.81 (0.56%) 792.88 (75.91%)
–0
.1
–0 0.00 (0.00%) 0.00 (0.00%)
.7
1
)
(0
%
.39
.0
30
7%
8(
)
7.3
31
b) c)
0.00 (0.00%) EFD (1) 135.68 (12.99%) ALDE (5) GUE-NGL (3)
0.00 (0.00%) 0.00 (0.00%) EPP (1) NI (3)
G-EFL (1)S&D (13)
0.00 (0.00%)
0.00 (0.00%)
EFD (1) d)
ALDE (2)
EFD (1)
0.86 (0.07%) S&D (1)
0.00 (0.00%)
11.9
ALDE (3) ALDE (2) 8 (0
ECR (1) ECR (1) .99
%)
EFD (8) ALDE (2) EFD (7)
EPP (35) EFD (1) EPP (34) ALDE (1)
NI (1) EPP (1) NI (1) –0.4
EPP (3)
ALDE (1) S&D (24) S&D (1) S&D (23) 9 (0 S&D (22)
6.75 (0.56%) 106.37 (8.81%) .04
–8.14 (0.67%)
%)
–6.79 (0.56%) –7.00 (0.58%)
0.00 (0.00%) 1191.32 (98.73%) 0.00 (0.00%) 1091.70 (90.47%) 176.05 (14.59%)
0.00 (0.00%) –1.83 (0.15%) –0.63 (0.05%) –0.99 (0.08%) 0.00 (0.00%)
)
.60%
23
5(
4.7
28
f) g) h)
724.43 (60.03%) ALDE (1) EPP (32)
0.00 (0.00%) ECR (1) NI (1)
EFD (7) S&D (1)
Figure 4: French (top) and Italian (bottom) MEPs for the AGRI domain during the year 2012-13: individual networks (a,e) ; and
cluster networks for the CC problem (b,f), the RCC problem with k = 2 (g), k = 3 (c,h), and k = 4 (d).
of positive internal and negative external links. The third cluster because it manages to identify a cluster of moderate MEPs, which
(at the bottom) is a single node corresponding to Philippe de Villiers, sometimes vote like the environmentalists, and sometimes like
the only French member of the right-wing euroskeptic EFD group. the right. The cluster graph consequently takes the form of an
Unlike the three members of the other euroskeptic group (NI), he is imbalanced (in terms of CC) triangle in which the environmentalists
connected to the rest of the graph only by negative links. This parti- and the right are in opposition, whereas the moderate are positively
tion displays a clear left/right divide, with the exception of the three connected to both. This type of structure could be identified only
NI members, who are put together with the left/environmentalists. thanks to the relaxed nature of RCC, which allows here to have
This divide can be explained when considering the texts voted positive links between clusters.
this year, among which many concern animal rights and related The k = 4 partition is quite similar to the CC partition, in the
matters (questions of great importance for these groups). The fact sense S&D and EPP are in the same cluster, and de Villiers is apart
one ALDE member was put with the Greens supports this, since it again. But NI and GUE-NGL are now part of the EPP-dominated
corresponds to Corrine Lepage, former Minister of the Environment cluster, and there is a fourth cluster formed by MEPs from almost
in a right-wing French government. One could expect the S&D to all political groups except EPP. Due to this heterogeneity, this last
vote similarly to the rest of the left on these topics. However, even cluster is very difficult to interpret. Yet, the partition reaches a
more texts voted during this year concern the CAP, on which the perfect zero imbalance, which means absolutely no link is misplaced.
center-left is more likely to side with the right. This also explains This highlights the fact increasing k will decrease the imbalance,
the position of NI, which is more likely to opportunistically support but not necessarily make the partition more informative, from the
resolutions in favor of small family-owned farms (and therefore application point of view. This means that the problem, as it is
vote like the radical left). formulated, does not allow to completely automate the process of
The other partitions are solutions of the RCC problem, with identifying the best partition for the end-user.
various k values. For k = 3 (we start from the optimal number of We now turn to the Italian MEPs, which are represented by
clusters for CC, as explained in Section 2.2), represented in plot the bottom plots of Figure 4. first point to notice in the individual
(c), we get a lower imbalance than with CC (0.19), which is to be network (e) is the complete absence of any G-EFL or GUE-NGL
expected. The partition differs from the first one in that it identifies MEPs, which seems to result in much fewer negative links, and
3 clusters of comparable sizes (no more singleton cluster). Both large therefore less polarization. The CC solution, represented in plot (f),
clusters from the previous partition loose a number of members, contains 2 clusters, with an imbalance of 8.58. They are connected
which are gathered to form a new, intermediary group. It contains as much positively as negatively, and the smaller is a singleton
some of the radical left (GUE-NGL), the center-left (S&D), center- corresponding to Gianni Vattimo. All of his links are negative, and
right (ALDE) as well as the NI group. The two other clusters are represent most of the negative links in the network. According to
the environmentalists (G-EFL with Lepage) and the rest of the right his biography5 , he has a very specific background and ideological
(EPP with de Villiers), respectively. This partition is interesting,
5 https://en.wikipedia.org/wiki/Gianni_Vattimo
6
ALDE (1)
G-EFL (14) 346.51 (29.39%) ALDE (5)
GUE-NGL (5) EFD (1) 0.00 (0.00%) EPP (26)
NI (3) G-EFL (14)
524.74 (44.51%) S&D (14) 466.68 (39.59%)
0.00 (0.00%) –29.18 (2.48%) GUE-NGL (5)
NI (3)
S&D (13)
)
46.7
7%
3 (3
.7
.96
(8
%)
44
3.
G-EFL (14)
–9
10
6.
ALDE (5) ALDE (5) ALDE (1) GUE-NGL (5)
7
–99 –12
9
EPP (30) 7.6 EPP (26) EPP (4) NI (3)
(8
.25 2 (1 SD (1) S&D (13)
.2
(8
1%
.42 0.8
–31.18 (2.64%)
–7.46 (0.63%)
%) 3%
91.40 (7.75%)
)
) 91.40 (7.75%)
–2.46 (0.21%)
)
7% 443.14 (37.59%) 346.51 (29.39%)
(2.8
–30.83 (2.62%)
3 0.00 (0.00%) 0.00 (0.00%) 6.57 (0.56%) 466.68 (39.59%)
)
8%
3.8
–5
0.00 (0.00%) 0.00 (0.00%)
–3
.0
.4
0
(2
)
(0
18
7%
.4
9.
8.7
2%
4(
–2
)
3.4
10
b) c) d)
0.00 (0.00%) EFD (1) 6.57 (0.56%) ALDE (1)
0.00 (0.00%) 0.00 (0.00%) EPP (4) 0.00 (0.00%) EFD (1)
S&D (1) 0.00 (0.00%)
EFD (4) 24.13 (2.22%)
EFD (7)
EPP (1)) 0.00 (0.00%)
EPP (1)
NI (1) NI (1)
189.76 (17.48%) SD (20)
0.00 (0.00%)
92.7
2 (8
ALDE (5) .54
%)
ALDE (2)
ECR (1) ECR (1)
)
1%
EFD (1) EFD (7) EFD (3) ALDE (3) ALDE (2)
–1
.3
EPP (33) EPP (1) EPP (4) ECR (1) EFD (1)
.9
(0
3
S&D (23) NI (1) –1.9 S&D (2) EPP (4) EPP (29)
2
(0
.3
3 (0
.1
S&D (2) S&D (1)
–3
8%
.18
–52.28 (4.82%)
%)
)
228.89 (21.09%)
–5.25 (0.48%)
1006.20 (92.71%) 24.13 (2.22%) %) 27.51 (2.53%) –0.80 (0.07%)
–49.77 (4.59%) 0.00 (0.00%) (0.07 0.00 (0.00%) 31.44 (2.90%) 485.65 (44.75%)
)
.80
%
0.00 (0.00%) 0.00 (0.00%)
1
–0
.5
(4
)
9%
97
.0
80
8.
20
–4
3(
.8
3
8.0
(7
21
.4
%5
f) g) h)
)
502.31 (46.28%) ALDE (3)
0.00 (0.00%) EFD (1) 179.39 (16.56%) S&D (20)
EPP (29) 0.00 (0.00%)
S&D (1)
Figure 5: French (top) and Italian (bottom) MEPs for the ECON domain during the year 2009-10: individual networks (a) ; and
cluster networks for the CC problem (b,f), the RCC problem with k = 3 (c,g) and k = 4 (d,h).
position (nihilist philosopher, communist, speaks his mind) we have sensibly the same size. The CC solution (b) contains 3 clusters
can confidently state he is an outlier. If we ignore him, we can for a relatively high imbalance (46.72). There are 2 large clusters:
conclude that no polarization was detected by CC, probably due to one dominated by left-wing groups (GUE-NGL, G-EFL, S&D) and
the absence of environmentalists. the other by right-wing ones (ALDE and EPP). Like for AGRI, we
Cluster graph (g) represents the partition obtained for RCC and have some exceptions: NI (far right) and Lepage (ALDE) are placed
k = 2. The imbalance is slightly improved, and the partition is quite in the left-wing cluster. For NI, we observe only a few positive
similar to that of CC, except Vattimo is joined by a few members of links with the left, but many negative ones with the right, which is
other groups. Interestingly, the resulting cluster has only negative why they were put in the left-wing cluster. The third cluster is a
internal links, whereas it is mostly positively connected to the other singleton: de Villiers, like for AGRI, because he is only negatively
cluster. This is called internal hostility by Doreian [8]. In this case, connected to the other groups. The clusters constitute a purely neg-
we suppose that this cluster gathers the most opposed MEPs from ative triangle: all clusters are in strong opposition while internally
the main groups, and that they are likely to be agents of polarization, positive. However, de Villiers is likely to be an outlier again, so this
pulling their groups in opposite directions. rather reflects a strong bipartition. This partition is consistent with
The partition obtained for k = 3 (d) has an almost-zero imbal- the groups’ ideologies regarding economics, with a clear left/right
ance (0.49), and differs in two points with the previous one: 1) the divide. It highlights the main difference with AGRI: this time, S&D
large cluster is split in two: S&D vs. right-wing groups ; and 2) Vat- is on the side of G-EFL/S&D (positive links) against EPP/ALDE
timo’s cluster changes slightly, and as a result becomes internally (negative links), and does not constitute an intermediary cluster.
positively connected. The cluster graph is quite similar in structure The result obtained for RCC k = 3 (c) has a slightly improved
to the one obtained for France with RCC k = 3, except this time imbalance (36.64). The partition also exhibits a strong left/right
S&D has positive connections with a right-wing cluster and a small divide, but not as strong as with CC. The third cluster does not
heterogeneous cluster, themselves in opposition (instead of right vs. contain de Villiers, and is instead a heterogeneous gathering of
left/environmentalists). Overall, the RCC k = 3 partition seems to MEPs from 3 distinct groups (EPP, S&D and ALDE), which seem to
be more informative than the RCC k = 2, but the very distinct vot- be outliers in their own groups. For instance, it contains Lepage,
ing behavior of Vattimo might hide the simple fact that the Italian which tends to vote like G-EFL when other ALDE MEPs votes like
MEPs are not polarized on agricultural questions. EPP. The cluster graph shows an imbalanced triangle, in which the
outliers group is positively connected to both wings, whereas the
4.2 Economic & Monetary Affairs other two clusters are very strongly negatively connected. There-
fore, we consider this group has an intermediate position on the
The top plot in Figure 5 display the ECON results for the French political spectrum, as previously observed for AGRI (with a different
MEP during the year 2009-10. The individual network (a) contains distribution, though).
much more negative links for AGRI. As we will see, this is meanly
due to the fact that, this time, the two main antagonistic groups
7
When considering k = 4 (d), the partition is the same except that the political groups, whereas other highlights specific behaviors or
de Villiers is placed in his own cluster. This small change causes positions in the EP.
the imbalance to drop to 2.5. However, it is worth noticing that However, we also identified some limitations, which we plan
de Villiers was absent to many votes during this period (27 out to solve in our future work. First, some artifacts appear when cer-
of 35), which explains the number and strength of his negative tain MEPs combine two specific behaviors: frequent absences and
links. Due to these absences, these links are not very meaningful. systematic Against vote. The partitioning tools are able to detect
So, in terms of interpretation, this partition is the same as the these cases, but they still obfuscate the results, so this issue has
previous one, as shown by the cluster graph. Again, as observed for to be solved before partitioning. Second, our interpretation was
AGRI, a lower imbalance does not necessarily means the partition limited to our short knowledge in the domain of European politics:
is more informative: it is necessary to go back to the original data we need to collaborate with a specialist, in order to further assess
to correctly interpret the results. the quality of the partitioning methods.
We now turn to Italian MEPs, represented in the bottom plots of
Figure 5. The individual network (e) contains much fewer negative ACKNOWLEDGMENTS
links compared to the French network, and they are mostly attached This research benefited from the support of the Agorantic FR 3621,
to a few MEPs (especially Magdi Cristiano Allam and Pino Arlacchi). as well as the FMJH Program Gaspard Monge in optimization and
Like before, this is due to the fact these MEPs were absent to a operation research (Project 2015-2842H), and from the support from
lot of voting sessions, and always vote Against: by comparison, EDF to this program.
frequent voters tend to have their similarity scores smoothed when
averaging over time. The CC solution (f) splits the network in 2 REFERENCES
clusters: one contains almost all far-right MEPs (EFD and NI), and [1] Z. Ales and A. Knippel. 2016. An extended edge-representative formulation for
the other the rest of the network. We clearly have 2 antagonistic the K-partitioning problem. Electr. Notes in Disc. Math. 52 (2016), 333–342.
[2] N. Bansal, A. Blum, and S. Chawla. 2002. Correlation Clustering. In 43rd Annual
clusters, however this is due, in part, to the possibly overestimated IEEE Symposium on Foundations of Computer Science. 238–247.
negative links mentioned earlier. Overall, the network does not [3] M. Brusco and D. Steinley. 2010. K-balance partitioning: An exact method with
seem to display as much polarization as the French one. applications to generalized structural balance and other psychological contexts.
Psychological Methods 15, 2 (2010), 145–157.
The result obtained with RCC for k = 2 is exactly similar to [4] D. Cartwright and F. Harary. 1956. Structural balance: A generalization of Heider’s
that of CC, and for this reason it is not shown. For k = 3 (g), the theory. Psychological Review 63 (1956), 277–293.
[5] K.-Y. Chiang, C.-J. Hsieh, N. Natarajan, I. S. Dhillon, and A. Tewari. 2014. Predic-
imbalance is almost zero (0.49), and the partition is very different: tion and clustering in signed networks: a local to global perspective. Journal of
the large cluster is roughly split into a left-wing (S&D) and a right- Machine Learning Research 15, 1 (2014), 1177–1213.
wing (EPP and ALDE) clusters, whereas the third group is very [6] L. Danon, A. DÃŋaz-Guilera, J. Duch, and A. Arenas. 2005. Comparing Commu-
nity Structure Identification. J. Stat. Mech. 2005, 9 (2005), P09008.
heterogeneous, and contains MEPs from all groups except NI. The [7] J. A. Davis. 1967. Clustering and structural balance in graphs. Human Relations
cluster graph takes the form of the triangle already observed before: 20, 2 (1967), 181–187.
two opposed clusters (here: left vs. right) both positively connected [8] P. Doreian and A. Mrvar. 2009. Partitioning signed social networks. Social
Networks 31, 1 (2009), 1–11.
to the third one (here: the heterogeneous cluster), which holds [9] P. Doreian and A. Mrvar. 2015. Structural Balance and Signed International
an intermediary position. With k = 4 (h), we get a very similar Relations. Journal of Social Structure 16 (2015), 1–49.
[10] P. Esmailian, S. E. Abtahi, and M. Jalili. 2014. Mesoscopic analysis of online social
partition, with an extra cluster gathering the same frequently absent networks: The role of negative ties. Physical Review E 90, 4 (2014), 042817.
far-right MEPs. As mentioned before, this group is likely to be an [11] R. Figueiredo and G. Moura. 2013. Mixed integer programming formulations for
artifact due to the way absence is handled during the extraction clustering problems related to structural balance. Soc. Net. 35, 4 (2013), 639–651.
[12] S. Fortunato. 2010. Community detection in graphs. 486, 3-5 (2010), 75–174.
process. However, RCC must be credited for being able to identify [13] F. Heider. 1946. Attitudes and cognitive organization. Journal of Psychology 21, 1
this cluster of interest while still distinguishing the three other (1946), 107–112.
political trends present among the Italian MEPs. [14] J. Kunegis, J. Preusse, and F. Schwagereit. 2013. What is the added value of
negative links in online social networks?. In 22nd International Conference on
World Wide Web. 727–736.
[15] M. Levorato, R. Figueiredo, Y. Frota, and L. Drummond. 2017. Evaluating balanc-
5 CONCLUSION ing on social networks through the efficient solution of correlation clustering
problems. EURO Journal on Computational Optimization in press (2017).
In this article, we extract and analyze signed networks representing [16] M. Levorato and Y. Frota. 2017. Brazilian Congress structural balance analysis.
the voting behavior of MEPs, using two graph partitioning methods Journal of Interdisciplinary Methodologies and Issues in Science 2 (2017).
for the CC and RCC problems. We first propose a filtering step to [17] I. Mendonça, R. Figueiredo, V. Labatut, and P. Michelon. 2015. Relevance of Neg-
ative Links in Graph Partitioning: A Case Study Using Votes From the European
make the original networks sparser, which eases both their pro- Parliament. In 2nd European Network Intelligence Conference. 122–129.
cessing and the interpretation of the results. We show empirically [18] A. Strehl and J. Ghosh. 2002. Cluster ensembles: A knowledge reuse framework
that the effect of this step on the obtained partitions is negligible. for combining multiple partitions. Journal of Machine Learning Research 3 (2002),
583–617.
We also assess the quality of a heuristic allowing to speed up the
partitioning process, and show it is significantly faster than an exact
method, while identifying solutions of the same quality. Finally, we
focus on 4 networks of interest from our dataset, and validate the
relevance of the partitioning algorithms by performing a qualita-
tive evaluation of their results. We show that the two partitioning
approaches are complementary, and allow to identify various types
of clusters: some match the traditional ideological divides between
8