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

  • SCI-E
  • SSCI
作者: 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
ISSN: 1475-3995
年: 2021
卷: 28
期: 3
页码: 1242-1264
基金类别: 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 [001]
摘要: 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.

文件格式:
导出字段:
导出
关闭
Polarization reduction by minimum-cardinality edge additions: Complexity and integer programming approaches.
有问题请联系我们,邮箱:常见的失败原因