Characterizing and locating polarized communities in signed networks

Abstract Extreme polarization stands as a crucial concern for fostering a healthier web ecosystem. Locating the polarized groups is pivotal in this context. These groups involve nodes forming robust agreements with each other and engaging in collective conflicts with other groups. Previous studies tackle this problem by focusing on the balanced subgraphs in which all (or small) cycles have an even number of negative edges. However, balanced subgraphs in real-world signed networks are often not inherently polarized, such as those with solely positive edges, and any method that targets balanced subgraphs results in sizable communities with dominantly positive interactions. Building on this concern, we propose to utilize cohesion to find polarized subgraphs in this work. Specifically, we identify pairs of cohesively polarized communities where each node within a community has many positive connections with the nodes in the same community and numerous negative connections with the nodes in the opposing community. We introduce a novel measure, called dichotomy, to capture both cohesion and polarization in a given pair of polarized communities. We show that optimizing dichotomy is NP-hard. As a heuristic approach, we employ balanced triangles to develop a hierarchical dense subgraph discovery algorithm, called atom decomposition, that establishes effective seedbeds for polarized communities in signed networks. To address the challenges posed by real-world signed networks, we introduce two additional algorithms to find polarized communities: photon and electron decompositions. Photon decomposition filters out the nodes that engage in unbalanced triangles and yields numerous cohesively balanced communities. Electron decomposition favors polarized triangles over positive triangles to find polarized communities with high dichotomy. Through comprehensive experiments, we demonstrate that our approaches excel in identifying cohesively polarized communities, surpassing the state-of-the-art methods across various metrics. We give interesting anecdotal findings by using our algorithms on a political network among governments in the Cold War era and a business network of company relationships/competitions. Overall, our algorithms exhibit greater effectiveness and efficiency than existing methods, rendering them practical for large-scale networks.