Polarized Community Detection in Signed Networks via Quasi-Arithmetic Means

The 2-POLARIZED-COMMUNITIES (2PC) problem seeks two disjoint polarized communities such that most edges within each community are positive, and most edges between communities are negative. The 2PC objective encodes these requirements as the arithmetic mean of the per-node net degree balance. While effective, this captures only an average-driven notion of polarized structure, and may overlook other notions such as tight cores, where all selected nodes are strongly polarized, and hub-driven formations, dominated by a few high-balance nodes. We introduce a novel one-parameter family of polarized-community objectives, where the parameter $p$ controls a quasi-arithmetic exponential mean of net degree balances. Our objective captures the standard 2PC problem as a special case ($p\to 0$), and interpolates between core-like ($p\to -\infty$) and hub-driven ($p\to +\infty$) notions of polarized structure. We study the complexity of the resulting problems, showing NP-hardness in general and at the core-like extreme, a polynomial-time exact algorithm for the hub-driven extreme, and identifying tractable cases on balanced signed graphs. Algorithmically, we show that the standard 2PC peeling rule does not extend to $p\ne 0$, and design a generalized peeling algorithm that removes nodes according to the exact marginal change in the finite-$p$ objective. Experiments on real-world datasets show that $p$ interpolates between small, dense, highly polarized cores and larger hub-driven structures; on synthetic graphs, our methods robustly identify the ground-truth communities.