Detecting coalitions by optimally partitioning signed networks of political collaboration
Detecting coalitions by optimally partitioning signed networks of political collaboration
复制标题
DOI：
10.1038/s41598-020-58471-z
复制
发表时间：
2020-01-30
影响因子：
4.6
通讯作者：
Neal, Zachary
中科院分区：
文献类型：
--
作者：
Aref, Samin;Neal, Zachary
我们提出了一种新的数学规划模型，用于将带符号图最优划分为内聚群。为了证明这种方法的实用性，我们应用它来识别自1979年以来美国国会中的联盟，并检查两极分化的联盟对通过法案的有效性的影响。对于最小化组内负边和组间正边总数的NP-Hard问题，我们的模型产生了一个全局最优解。我们通过提供上下界来解决密集符号网络的密集计算问题，然后求解一个优化模型，该模型弥合了这两个界之间的差距，并返回最优的顶点划分。我们的实质性调查结果表明，意识形态上同质联盟的主导地位(即党派分化)可以成为提高立法效力的保护性因素。
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.