Scholarlink

<p>Polarization is common in social systems, where individuals tend to form cohesive groups that oppose each other. Signed networks, with positive edges representing agreement and negative edges representing disagreement, provide a natural model for studying such dynamics. The <span>2-Polarized-Communities</span> problem (<span>2pc</span>) was recently introduced to detect a single pair of polarized communities by maximizing a Rayleigh quotient that balances intra-community agreement and inter-community disagreement. However, real signed networks usually host multiple, coexisting axes of conflict, often with communities that overlap. Existing extension of <span>2pc</span> to multiple communities or find-and-remove heuristics, either rely on the restrictive assumption that every polarized community is in conflict with all the others, or enforce disjoint solutions–thus failing to capture the nuanced structures observed in real networks. In this paper, we introduce the <span>Diverse top-k-pc</span> problem, which is the first principled formulation of top-<i>k</i> polarized communities with controlled overlap. Our formulation extends the <span>2pc</span> polarity objective by incorporating diversity terms directly into the denominator of the Rayleigh quotient, yielding a generalized objective that jointly promotes polarity and diversity. We design a greedy sequential algorithm that solves a generalized eigenvector problem at each step, efficiently discovering diverse polarized pairs. Experiments on both real-world and synthetic signed networks demonstrate that our approach identifies multiple meaningful and overlapping pairs of polarized communities, outperforming natural baselines while scaling to large graphs.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Top-k Diverse Polarized Communities in Signed Networks

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年7月2日

查看全文
  • Francesco Gullo,
  • Domenico Mandaglio,
  • Andrea Tagarelli

摘要

Polarization is common in social systems, where individuals tend to form cohesive groups that oppose each other. Signed networks, with positive edges representing agreement and negative edges representing disagreement, provide a natural model for studying such dynamics. The 2-Polarized-Communities problem (2pc) was recently introduced to detect a single pair of polarized communities by maximizing a Rayleigh quotient that balances intra-community agreement and inter-community disagreement. However, real signed networks usually host multiple, coexisting axes of conflict, often with communities that overlap. Existing extension of 2pc to multiple communities or find-and-remove heuristics, either rely on the restrictive assumption that every polarized community is in conflict with all the others, or enforce disjoint solutions–thus failing to capture the nuanced structures observed in real networks. In this paper, we introduce the Diverse top-k-pc problem, which is the first principled formulation of top-k polarized communities with controlled overlap. Our formulation extends the 2pc polarity objective by incorporating diversity terms directly into the denominator of the Rayleigh quotient, yielding a generalized objective that jointly promotes polarity and diversity. We design a greedy sequential algorithm that solves a generalized eigenvector problem at each step, efficiently discovering diverse polarized pairs. Experiments on both real-world and synthetic signed networks demonstrate that our approach identifies multiple meaningful and overlapping pairs of polarized communities, outperforming natural baselines while scaling to large graphs.