An Efficient Local Search Approach for Polarized Community Discovery in Signed Networks

Researchers Linus Aronsson and Morteza Haghir Chehreghani have published a new paper, "An Efficient Local Search Approach for Polarized Community Discovery in Signed Networks," accepted at NeurIPS 2025. The work tackles a core problem in network science: identifying groups that are internally friendly (positive edges) but externally hostile (negative edges) within complex social systems like online discourse or political forums. Their key innovation is a novel optimization objective that directly addresses a major flaw in previous methods—their tendency to produce solutions with wildly uneven community sizes, which are less meaningful for real-world analysis.

Building on the known effectiveness of local search algorithms for clustering, the team designed the first such algorithm that efficiently handles the practical scenario where many vertices (users or nodes) are neutral or unaligned. By framing their approach within a block-coordinate Frank-Wolfe optimization framework, they provide strong theoretical guarantees, including a proven linear convergence rate. In practical tests on real-world and synthetic datasets, their method consistently delivered higher-quality community structures than existing state-of-the-art techniques, while maintaining competitive computational speed. This makes it a scalable tool for analyzing large-scale, contentious social networks.