"Polarization reduction by minimum edge additions"
Celso Ribeiro

Polarization is the division into sharply contrasting groups or sets of opinions or beliefs. The issue of polarization has been widely discussed by politicians, media, and researchers. Polarized networks are divided into two or more strongly connected groups, with few edges between vertices belonging to different groups. We illustrate this discussion considering a short real-life polarized network extracted from Research Gate, involving the optimization community and, in particular, the area of metaheuristics.

New tools for evaluating the polarization of a network are described. We characterize the homophily of each node individually. In order to address the polarization of the network as a whole, a probabilistic approach is developed, based on the computation of empirical cumulative distribution functions of sampled data from the network. These empirical distributions provide a more insightful understanding of the status of the network. They may be used not only to compare the polarization of groups of nodes or entire networks, but also to estimate the impacts of external interventions in terms of node polarization. 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 campaign, a regulatory action or some direct manipulation that adds or removes vertices or edges of the network.

External interventions can be used to treat networks in order to reduce polarization. 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 be interpreted as the permanent exclusion of elements such as users, sites, or posts from a social network. Exclusions are often interpreted as aggressions against freedom of expression in the digital environment.

We introduce the Minimum-Cardinality Balanced Edge Addition Problem as a strategy for reducing polarization in real-world networks. We present the problem formulation and discuss its complexity, showing that its decision version is NP-complete. Computational results on artificially generated and real-life instances are discussed. Randomly generated instances with up to 1000 vertices are solved to optimality. Heuristic approaches are needed to solve larger problems. 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 that guided this approach is shown to constitute an effective strategy for tackling polarization problems in real networks, making it possible to build concrete tools and strategies to address polarization issues in practice.