Detecting coalitions by optimally partitioning signed networks of political collaboration

Abstract

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.

arXiv comment21 pages, 10 figures, 4 tables (including supplementary information) Old title: Legislative effectiveness hangs in the balance: Studying balance and polarization through partitioning signed networks

References in corpus (12)

• Community structure in social and biological networks
• Finding community structure in very large networks
• Near linear time algorithm to detect community structures in large-scale networks
• Extracting the multiscale backbone of complex weighted networks
• A network analysis of committees in the United States House of Representatives
• Community Structure in Congressional Cosponsorship Networks
• The dynamical structure of political corruption networks
• Unwinding the hairball graph: pruning algorithms for weighted complex networks
• Balance and Frustration in Signed Networks
• Measuring Partial Balance in Signed Networks
• Party Polarization in Congress: A Network Science Approach
• Multiple Partitioning of Multiplex Signed Networks: Application to European Parliament Votes

Cited by in corpus (12)

• backbone: An R package to extract network backbones
• backbone: An R Package for extracting the backbone of bipartite projections
• Comparing Alternatives to the Fixed Degree Sequence Model for Extracting the Backbone of Bipartite Projections
• An Evaluation Tool for Backbone Extraction Techniques in Weighted Complex Networks
• Polarization and multiscale structural balance in signed networks
• Identifying hidden coalitions in the US House of Representatives by optimally partitioning signed networks based on generalized balance
• Mean-Field Solution for Critical Behavior of Signed Networks in Competitive Balance Theory
• Co-sponsorship analysis of party politics in the 20th National Assembly of Republic of Korea
• Modified Heider Balance on Sparse Random Networks
• Analyzing and visualizing polarization and balance with signed networks: the U.S. Congress case study
• Negative Ties Highlight Hidden Extremes in Social Media Polarization
• Evaluating Presidential Support in the Brazilian House of Representatives Through a Network-Based Approach