Polarized Communities Meet Densest Subgraph: Efficient and Effective Polarization Detection in Signed Networks

Signed networks represent interactions among users (nodes), with edges labeled as positive for friendly relations and negative for antagonistic ones. The 2-Polarized-Communities (2pc) combinatorial optimization problem seeks two disjoint polarized communities in a signed network, so as to satisfy three conditions: most edges within each community are positive, most edges between communities are negative, and the number of edges satisfying these conditions is high compared to the number of nodes in the communities. The Densest Subgraph (ds) problem in unsigned networks consists in finding a subgraph that exhibits maximum ratio between number of edges and number of nodes. Although the 2pc problem intuitively suggests finding a dense subgraph, no prior work has explored the implicitly optimized density measure or algorithmic methods from the rich, yet distinct, literature on the ds problem (in unsigned networks) and applied them to 2pc. This work bridges this gap by formally establishing a link between the two problems and introducing a highly efficient and effective greedy algorithm inspired by ds methods to solve 2pc. Experimental results on synthetic and real datasets demonstrate the superior performance of our method compared to competing approaches in terms of both accuracy and efficiency.