# Discovering Polarized Communities in Signed Networks

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Oct 2019.

## Built on by (most cited first, 20 of 20)

- [SSSNET: Semi-Supervised Signed Network Clustering](https://mlsanity.com/paper/2110.06623/) (2021)
- [Signed Bipartite Graph Neural Networks](https://mlsanity.com/paper/2108.09638/) (2021)
- [POLE: Polarized Embedding for Signed Networks](https://mlsanity.com/paper/2110.09899/) (2021)
- [Self-Explainable Graph Transformer for Link Sign Prediction](https://mlsanity.com/paper/2408.08754/) (2024)
- [Representation Learning in Continuous-Time Dynamic Signed Networks](https://mlsanity.com/paper/2207.03408/) (2022)
- [Signed Graph Autoencoder for Explainable and Polarization-Aware Network Embeddings](https://mlsanity.com/paper/2409.10452/) (2024)
- [Exact Community Recovery over Signed Graphs](https://mlsanity.com/paper/2202.12255/) (2022)
- [DropEdge not Foolproof: Effective Augmentation Method for Signed Graph Neural Networks](https://mlsanity.com/paper/2409.19620/) (2024)
- [In-Group Love, Out-Group Hate: A Framework to Measure Affective Polarization via Contentious Online Discussions](https://mlsanity.com/paper/2412.14414/) (2024)
- [Sublinear-Time Clustering Oracle for Signed Graphs](https://mlsanity.com/paper/2206.13813/) (2022)
- [Trustworthiness-Driven Graph Convolutional Networks for Signed Network Embedding](https://mlsanity.com/paper/2309.00816/) (2023)
- [Link Polarity Prediction from Sparse and Noisy Labels via Multiscale Social Balance](https://mlsanity.com/paper/2407.15643/) (2024)
- [An Efficient Local Search Approach for Polarized Community Discovery in Signed Networks](https://mlsanity.com/paper/2502.02197/) (2025)
- [Improved analysis of randomized SVD for top-eigenvector approximation](https://mlsanity.com/paper/2202.07992/) (2022)
- [Quantitative Analysis of Forecasting Models:In the Aspect of Online Political Bias](https://mlsanity.com/paper/2309.05589/) (2023)
- [SGA: A Graph Augmentation Method for Signed Graph Neural Networks](https://mlsanity.com/paper/2310.09705/) (2023)
- [Enhancing Signed Graph Neural Networks through Curriculum-Based Training](https://mlsanity.com/paper/2310.11083/) (2023)
- [Bridging or Breaking: Impact of Intergroup Interactions on Religious Polarization](https://mlsanity.com/paper/2402.11895/) (2024)
- [Signed graphs in data sciences via communicability geometry](https://mlsanity.com/paper/2403.07493/) (2024)
- [Linking Scalar-Intensity Language to Structural Polarization with Validated Signed-Network Measures](https://mlsanity.com/paper/2605.12814/) (2026)

## Abstract (arXiv)

Signed networks contain edge annotations to indicate whether each interaction is friendly (positive edge) or antagonistic (negative edge). The model is simple but powerful and it can capture novel and interesting structural properties of real-world phenomena. The analysis of signed networks has many applications from modeling discussions in social media, to mining user reviews, and to recommending products in e-commerce sites. In this paper we consider the problem of discovering polarized communities in signed networks. In particular, we search for two communities (subsets of the network vertices) where within communities there are mostly positive edges while across communities there are mostly negative edges. We formulate this novel problem as a "discrete eigenvector" problem, which we show to be NP-hard. We then develop two intuitive spectral algorithms: one deterministic, and one randomized with quality guarantee √n (where n is the number of vertices in the graph), tight up to constant factors. We validate our algorithms against non-trivial baselines on real-world signed networks. Our experiments confirm that our algorithms produce higher quality solutions, are much faster and can scale to much larger networks than the baselines, and are able to detect ground-truth polarized communities.