Polarization reduction by minimum‐cardinality edge additions: Complexity and integer programming approaches

• Date: 01 May 2021
• Author: Ruben Interian,Celso C. Ribeiro,Jorge R. Moreno
• DOI: http://doi.org/10.1111/itor.12854
• Published date: 01 May 2021

Intl. Trans. in Op. Res. 28 (2021) 1242–1264

DOI: 10.1111/itor.12854

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Polarization reduction by minimum-cardinality edge additions:

Complexity and integer programming approaches

Ruben Interian∗, Jorge R. Moreno and Celso C. Ribeiro

Institute of Computing, Universidade FederalFluminense, Niterói, RJ 24210-346, Brazil

E-mail: rinterian@id.uff.br [Interian]; jmoreno@ic.uff.br[Moreno]; celso@ic.uff.br [Ribeiro]

Received 5 March 2020; receivedin revised form 30 June 2020; accepted 19 July 2020

Abstract

Real-world networks are often extremely polarized because the communication between different groups of

vertices can be weak and, most of the time, only vertices within the same group or sharing the same be-

liefs communicate to each other. In this work, we introduce the minimum-cardinality edge addition problem

(MinCEAP) as a strategy for reducing polarization in real-world networks based on a principle of minimum

external interventions. We present the problem formulation and discuss its complexity, showing that its deci-

sion version is NP-complete. We also propose three integer programming formulations for the problem and

discuss computational results on artificially generated and real-life instances. Randomly generated instances

with up to 1000 vertices are solved to optimality. On the real-life instances, we show that polarization can be

reduced to the desired threshold with the addition of a few edges. The minimum intervention principle and

the methods developed in this work are shown to constitute an effective strategy for tackling polarization

issues in practice in social, interaction, and communication networks, which is a relevant problem in a world

characterized by extreme political and ideological polarization.

Keywords: polarization; minimum-cardinality edge addition problem; polarized networks; complexity; integer program-

ming

1. Motivation

The issue of polarization has been discussed by politicians, media, and researchers (The Economist,

2015; New York Times, 2017). This subject has also attracted the attention of thinkers throughout

history. John Stuart Mill claimed that dialogue across lines of political difference is a key prereq-

uisite for sustaining a democratic citizenry (Mill, 1859). Hannah Arendt also asseverated that de-

bate is irreplaceable for forming enlightened opinions that reach beyond the limits of one’s own

∗Corresponding author.

© 2020 The Authors.

International Transactionsin Operational Research © 2020 International Federation of OperationalResearch Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

R. Interian et al. / Intl. Trans. in Op. Res. 28 (2021) 1242–1264 1243

subjectivity to incorporate the standpoints of others (Arendt, 1968). From sociologists to

economists, many are interested in studying the behavior and interactions in social networks that

rule the opinion formation process.

According to the Oxford Dictionaries, polarization is the division into sharply contrasting groups

or sets of opinions or beliefs (Oxford Dictionaries, 2017). Academic articles, newspapers, and the

media in general constantly report the growth of fake news, misinformation spreading, and the

polarization of increasingly isolated groups of individuals (Ribeiro and Interian, 2020). These phe-

nomena are closely interrelated with each other. Fake news spread faster in polarized networks or

groups (Ribeiro et al., 2017). At the same time, fake and tendentious news can accentuate polariza-

tion within already existing echo chambers in social networks.

Recently, the causes of the proliferation of flat-earth believers, that is, people who believe that

the Earth is actually flat, were investigated by Landrum (2019), revealing the role of the video-

sharing platform YouTube on this proliferation. This work showed that the algorithms the plat-

form uses to guide people to topics that might interest them make it easier for a user to end

up in a misinformation echo chamber. The study concludes that the most effective instrument

to combat disinformation—that is, false information spread deliberately to deceive—is to provide

(or even “to flood”) users of the platform with high-quality information, to ensure that the pub-

lic also receives accurate, scientific or simply plural information when watching videos on some

subject.

Interian and Ribeiro (2018) have shown that many case-study real-world networks are extremely

polarized. A polarized network is one divided into two or more strongly connected groups,with few

edges between vertices belonging to different groups. Communication between different groups is

weak: there are many vertices for which all or most of its neighbors belong to the same group.

In practice, this corresponds to a situation where, most of the time, only same-group vertices

communicate to each other and most of the information that a vertex can receive comes from

inside the same group to which it belongs. These groups may correspond to large cliques or quasi-

cliques (Abello et al., 1999; Pinto et al., 2018; Ribeiro and Riveaux, 2018; Vogiatzis and Walteros,

2018; Walteros et al., 2019). In such graphs, there may be an important number of vertices that are

loosely connected to other groups, that is, there may be only intragroup edges adjacent to these

vertices. Consider, for example, a network of books about U.S. politics sold by Amazon.com (New-

man, 2017). Edges between books represent frequent co-purchasing of those books by the same

buyers. Most of the books are classified as conservative or liberal, and a small number of them as

neutral. There are 105 vertices in this instance and 56 of them are adjacent only to neighbors of

the same group, as shown in Fig. 1. Another example is that of a network of political blogs that

emerged during the 2004 U.S. presidential election (Adamic and Glance, 2005). Blogs are divided

into two groups: republican and democratic. Among the 1065 nonisolated vertices in this instance,

there are 572 blogs with links exclusively to blogs of the same political orientation, as shown in

Fig. 2.

Interian (2019) also showed that, in order to reduce polarization, networks can be treated

by external interventions. An intervention can be seen as any externally induced process that

modifies the structure of the network, such as a fact-checking campaign, a marketing cam-

paign, a regulatory action, or some direct manipulation that adds or removes vertices or edges

of the network. The process of adding new vertices is often difficult to be performed in real

networks. On the other hand, removing vertices or edges may be controversial because it can

© 2020 The Authors.

International Transactionsin Operational Research © 2020 International Federation of OperationalResearch Societies