Reducing Network Polarization by Edge Additions

Real-world networks are often extremely polarized, because the communication between groups of vertices can be weak and, most of the time, only vertices in the same groups or sharing the same beliefs communicate to each other. We formulate the Minimum-Cardinality Balanced Edge Addition Problem as a strategy for reducing polarization in real-world networks based on a principle of minimum external interventions. We give the integer programming formulation and discuss computational results on randomly generated and 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 approach developed in this work are shown to constitute an effective strategy for reducing polarization in social, interaction, and communication networks.