Polarization reduction by minimum-cardinality edge additions: Complexity and integer programming approaches.
Ruben Interian;Jorge R. Moreno;Celso C. Ribeiro
Institute of Computing Universidade Federal Fluminense Niterói RJ 24210‐346 Brazil
polarization;minimum-cardinality edge addition problem;polarized networks;complexity;integer programming
INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH
CNPqNational Council for Scientific and Technological Development (CNPq) [303958/2015-4, 425778/2016-9]; FAPERJCarlos Chagas Filho Foundation for Research Support of the State of Rio de Janeiro (FAPERJ) [E-26/202.854/2017]; Coordenacao de Aperfeicoamento de Pessoal de Nivel Superior (CAPES)CAPES 
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 beliefs 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 decision 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.