Laboratory of Digital and Computational Demography, Max Planck Institute for Demographic Research, 18057, Rostock, Germany.
School of Computer Science, University of Auckland, 1142, Auckland, New Zealand.
Sci Rep. 2020 Jan 30;10(1):1506. doi: 10.1038/s41598-020-58471-z.
We propose new mathematical programming models for optimal partitioning of a signed graph into cohesive groups. To demonstrate the approach's utility, we apply it to identify coalitions in US Congress since 1979 and examine the impact of polarized coalitions on the effectiveness of passing bills. Our models produce a globally optimal solution to the NP-hard problem of minimizing the total number of intra-group negative and inter-group positive edges. We tackle the intensive computations of dense signed networks by providing upper and lower bounds, then solving an optimization model which closes the gap between the two bounds and returns the optimal partitioning of vertices. Our substantive findings suggest that the dominance of an ideologically homogeneous coalition (i.e. partisan polarization) can be a protective factor that enhances legislative effectiveness.
我们提出了新的数学规划模型，用于将有符号图最佳划分为凝聚群组。为了展示该方法的实用性，我们将其应用于识别自 1979 年以来美国国会中的联盟，并研究极化联盟对法案通过效率的影响。我们的模型针对最小化组内负边和组间正边总数的 NP 难问题提供了全局最优解。我们通过提供上下界来解决密集有符号网络的密集计算问题，然后求解一个优化模型，该模型缩小了两个界之间的差距，并返回顶点的最优划分。我们的实质性发现表明，意识形态同质联盟（即党派极化）的主导地位可能是增强立法效力的保护因素。
