# On the Complexity of the Bipartite Polarization Problem: from Neutral to Highly Polarized Discussions

arXiv: https://arxiv.org/abs/2307.11621 · HTML: https://mlsanity.com/paper/2307.11621/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 33 references that are in the map.
- First posted on arXiv 21 Jul 2023.

## Builds on (most cited first, 5 of 5)

- [Echo Chambers: Emotional Contagion and Group Polarization on Facebook](https://mlsanity.com/paper/1607.01032/) (2016)
- [Users Polarization on Facebook and Youtube](https://mlsanity.com/paper/1604.02705/) (2016)
- [No Echo in the Chambers of Political Interactions on Reddit](https://mlsanity.com/paper/2102.05477/) (2021)
- [Polarization and Fake News: Early Warning of Potential Misinformation Targets](https://mlsanity.com/paper/1802.01400/) (2018)
- [On the Impact of Social Media Recommendations on Opinion Consensus](https://mlsanity.com/paper/2204.03299/) (2022)

## Abstract (arXiv)

The Bipartite Polarization Problem is an optimization problem where the goal is to find the highest polarized bipartition on a weighted and labelled graph that represents a debate developed through some social network, where nodes represent user's opinions and edges agreement or disagreement between users. This problem can be seen as a generalization of the maxcut problem, and in previous work approximate solutions and exact solutions have been obtained for real instances obtained from Reddit discussions, showing that such real instances seem to be very easy to solve. In this paper, we investigate further the complexity of this problem, by introducing an instance generation model where a single parameter controls the polarization of the instances in such a way that this correlates with the average complexity to solve those instances. The average complexity results we obtain are consistent with our hypothesis: the higher the polarization of the instance, the easier is to find the corresponding polarized bipartition.