論文の概要: An Efficient Local Search Approach for Polarized Community Discovery in Signed Networks
- arxiv url: http://arxiv.org/abs/2502.02197v2
- Date: Sat, 05 Jul 2025 12:39:26 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-08 15:46:34.210595
- Title: An Efficient Local Search Approach for Polarized Community Discovery in Signed Networks
- Title（参考訳）: 符号付きネットワークにおける分極型コミュニティ発見のための効率的な局所探索手法
- Authors: Linus Aronsson, Morteza Haghir Chehreghani,
- Abstract要約: そこで本研究では,$k$の偏光コミュニティを同定する手法を提案する。
サイズ不均衡な解を避けるための新しい最適化手法を提案する。
実世界のデータセットと合成データセットの実験は、我々の手法がソリューション品質の最先端のベースラインを一貫して上回っていることを示している。
- 参考スコア（独自算出の注目度）: 3.2688425993442696
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Signed networks, where edges are labeled as positive or negative to represent friendly or antagonistic interactions, offer a natural framework for analyzing polarization, trust, and conflict in social systems. Detecting meaningful group structures in such networks is crucial for understanding online discourse, political divisions, and trust dynamics. A key challenge is to identify communities that are internally cohesive and externally antagonistic, while allowing for neutral or unaligned vertices. In this paper, we propose a method for identifying $k$ polarized communities that addresses a major limitation of prior methods: their tendency to produce highly size-imbalanced solutions. We introduce a novel optimization objective that avoids such imbalance. In addition, it is well known that approximation algorithms based on local search are highly effective for clustering signed networks when neutral vertices are not allowed. We build on this idea and design the first local search algorithm that extends to the setting with neutral vertices while scaling to large networks. By connecting our approach to block-coordinate Frank-Wolfe optimization, we prove a linear convergence rate, enabled by the structure of our objective. Experiments on real-world and synthetic datasets demonstrate that our method consistently outperforms state-of-the-art baselines in solution quality, while remaining competitive in computational efficiency.
- Abstract（参考訳）: エッジが友好的あるいは敵対的な相互作用を表すために肯定的あるいは否定的にラベル付けされたサイン付きネットワークは、社会システムにおける分極、信頼、紛争を分析するための自然な枠組みを提供する。
このようなネットワークにおける有意義なグループ構造の検出は、オンラインの談話、政治的分裂、信頼のダイナミクスを理解する上で不可欠である。
重要な課題は、中立的あるいは非整合的な頂点を許容しながら、内部の結束性と外部の対立性を持つコミュニティを特定することである。
本稿では,従来の手法の大きな制限に対処する,$k$の偏光コミュニティを同定する手法を提案する。
このような不均衡を回避するために,新たな最適化手法を提案する。
さらに, 局所探索に基づく近似アルゴリズムは, 中立頂点が許されていない場合, 符号付きネットワークのクラスタリングに極めて有効であることが知られている。
我々は、このアイデアに基づいて、大規模なネットワークにスケールしながら中立な頂点を持つ設定にまで拡張する、最初のローカル検索アルゴリズムを設計する。
ブロックコーディネートフランク=ウルフ最適化へのアプローチを結合することにより、目的の構造によって可能となる線形収束率を証明できる。
実世界のデータセットと合成データセットの実験は、我々の手法が計算効率の競争力を維持しながら、ソリューション品質の最先端のベースラインを一貫して上回っていることを示している。
関連論文リスト
- Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networks [103.78912399195005]
組合せ最適化(英: Combinatorial Optimization、CO)は、計算機科学、応用数学などにおける基本的な問題である。
本稿では, 正線形制約下でのCO問題の解法として, 非自己回帰ニューラルネットワーク群を設計する。
本研究では,施設位置,最大被覆率,旅行セールスマン問題を含む代表的CO問題の解決において,この枠組みの有効性を検証する。
論文 参考訳（メタデータ） (2024-09-06T14:58:31Z) - The Impact of Adversarial Node Placement in Decentralized Federated Learning Networks [6.661122374160369]
連邦学習(FL)の人気が高まるにつれ、新しい分散フレームワークが広まりつつある。
本稿では,ネットワーク内の配置を協調的に調整できる各種対向配置戦略において,分散FLの性能を解析する。
本稿では,敵同士の平均ネットワーク距離を最大化することにより,敵の中央性よりも敵の拡散を優先する新たな攻撃アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-11-14T06:48:50Z) - Rebalancing Social Feed to Minimize Polarization and Disagreement [24.939887831898453]
本稿では,ユーザのソーシャルフィードをわずかにヌードすることを目的とした新しい問題定式化を提案し,その妥当性と多様性を両立させる。
提案手法は,ユーザがフォローするアカウントの相対的重要性を再重み付けすることで,ユーザに対して様々なアカウントが生成するコンテンツの頻度を校正する。
論文 参考訳（メタデータ） (2023-08-28T10:59:05Z) - Networked Communication for Decentralised Agents in Mean-Field Games [59.01527054553122]
平均フィールドゲームフレームワークにネットワーク通信を導入する。
当社のアーキテクチャは、中央集権型と独立した学習ケースの双方で保証されていることを証明しています。
論文 参考訳（メタデータ） (2023-06-05T10:45:39Z) - Network polarization, filter bubbles, and echo chambers: An annotated
review of measures and reduction methods [0.0]
偏極は、下層のネットワークが、グループ間の接続が弱い高度に連結されたグループによって特徴づけられるときに生じる。
本研究は、ネットワーク偏光対策と偏光処理に使用されるモデルについて注釈付きレビューを行う。
論文 参考訳（メタデータ） (2022-07-27T21:23:27Z) - One More Step Towards Reality: Cooperative Bandits with Imperfect
Communication [15.440053226788562]
我々は,3つの典型的な実世界のコミュニケーションシナリオの下で協調的バンディット学習を研究する。
競争性能を実現する分散型アルゴリズムを提案する。
様々なネットワークトポロジにおいて既存の最先端技術よりも優れた遅延更新アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-11-24T13:19:11Z) - Finite-Time Consensus Learning for Decentralized Optimization with
Nonlinear Gossiping [77.53019031244908]
本稿では,非線形ゴシップ(NGO)に基づく分散学習フレームワークを提案する。
コミュニケーション遅延とランダム化チャットが学習にどう影響するかを解析することで,実践的なバリエーションの導出が可能となる。
論文 参考訳（メタデータ） (2021-11-04T15:36:25Z) - Unsupervised Domain-adaptive Hash for Networks [81.49184987430333]
ドメイン適応型ハッシュ学習はコンピュータビジョンコミュニティでかなりの成功を収めた。
UDAHと呼ばれるネットワークのための教師なしドメイン適応型ハッシュ学習手法を開発した。
論文 参考訳（メタデータ） (2021-08-20T12:09:38Z) - Contingency-Aware Influence Maximization: A Reinforcement Learning
Approach [52.109536198330126]
インフルエンス(IM)問題は、インフルエンスの普及を最大化する、ソーシャルネットワーク内のシードノードのサブセットを見つけることを目的としている。
本研究では、招待されたノードがシードであるかどうかが不確実なIM問題(contingency-aware IM)に焦点をあてる。
最初の成功にもかかわらず、より多くのコミュニティへのソリューションの推進における大きな実践上の障害は、欲張りのアルゴリズムの巨大な実行時である。
論文 参考訳（メタデータ） (2021-06-13T16:42:22Z) - Competing Adaptive Networks [56.56653763124104]
適応エージェントのチーム間での分散競争のためのアルゴリズムを開発する。
本稿では,生成的対向ニューラルネットワークの分散学習への応用について述べる。
論文 参考訳（メタデータ） (2021-03-29T14:42:15Z) - Hide and Seek: Outwitting Community Detection Algorithms [17.144388833011536]
ネットワーク内のノードのコンテキスト位置を決定する上で,コミュニティ提携は重要な役割を果たす。
本研究は,そのようなセンシティブなコミュニティを隠して,対象ノードのコミュニティ関連を隠蔽することに焦点を当てている。
我々は,ノード中心の目的関数を厳格に最適化し,スイッチング戦略を決定する新手法であるNEURALを紹介する。
論文 参考訳（メタデータ） (2021-02-22T03:50:44Z) - On the use of local structural properties for improving the efficiency
of hierarchical community detection methods [77.34726150561087]
本研究では,階層型コミュニティ検出の効率向上のために,局所構造ネットワーク特性をプロキシとして利用する方法について検討する。
また,ネットワークプルーニングの性能への影響を,階層的コミュニティ検出をより効率的にするための補助的手法として検証する。
論文 参考訳（メタデータ） (2020-09-15T00:16:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。