論文の概要: On the Complexity of the Bipartite Polarization Problem: from Neutral to
Highly Polarized Discussions
- arxiv url: http://arxiv.org/abs/2307.11621v1
- Date: Fri, 21 Jul 2023 14:40:41 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-24 12:15:35.862856
- Title: On the Complexity of the Bipartite Polarization Problem: from Neutral to
Highly Polarized Discussions
- Title（参考訳）: 二部分極問題の複雑さについて:中性から高分極的考察
- Authors: Teresa Alsinet, Josep Argelich, Ram\'on B\'ejar and Santi Mart\'inez
- Abstract要約: 双分極問題は、重み付きラベル付きグラフ上で最も高い偏極二分法を見つけることを目標とする最適化問題である。
単一パラメータがインスタンスの分極を制御するインスタンス生成モデルを導入する。
- 参考スコア（独自算出の注目度）: 1.5675763601034223
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Bipartite Polarization Problem is an optimization problem where the goal
is to find the highest polarized bipartition on a weighted and labelled graph
that represents a debate developed through some social network, where nodes
represent user's opinions and edges agreement or disagreement between users.
This problem can be seen as a generalization of the maxcut problem, and in
previous work approximate solutions and exact solutions have been obtained for
real instances obtained from Reddit discussions, showing that such real
instances seem to be very easy to solve. In this paper, we investigate further
the complexity of this problem, by introducing an instance generation model
where a single parameter controls the polarization of the instances in such a
way that this correlates with the average complexity to solve those instances.
The average complexity results we obtain are consistent with our hypothesis:
the higher the polarization of the instance, the easier is to find the
corresponding polarized bipartition.
- Abstract（参考訳）: バイパルタイト分極問題 (Bipartite Polarization Problem) は、あるソーシャルネットワークを通じて開発された議論を表す重み付きラベル付きグラフ上で、ノードがユーザの意見や意見の一致やユーザ間の意見の相違を表す、最も高い分極分極を求める最適化問題である。
この問題はマックスカット問題の一般化と見なすことができ、過去の研究ではRedditの議論から得られた実例に対して、近似解と正確な解が得られており、そのような実例は非常に容易に解決できることが示されている。
本稿では,単一パラメータがインスタンスの分極を制御するインスタンス生成モデルを導入することにより,この問題の複雑さをさらに解明する。
私たちが得られる平均的な複雑性結果は、我々の仮説と一致している: インスタンスの偏極性が高いほど、対応する偏極二分割を見つけるのがより簡単である。
関連論文リスト
- Polynomial-Time Solutions for ReLU Network Training: A Complexity
Classification via Max-Cut and Zonotopes [70.52097560486683]
我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。
特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
論文 参考訳（メタデータ） (2023-11-18T04:41:07Z) - PARTNER: Level up the Polar Representation for LiDAR 3D Object Detection [81.16859686137435]
本稿では、極座標における新しい3次元物体検出器Partnerを紹介する。
提案手法は,ONCE検証セットにおいて3.68%,9.15%の差で従来の極性理論よりも優れていた。
論文 参考訳（メタデータ） (2023-08-08T01:59:20Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳（メタデータ） (2023-06-21T17:03:22Z) - Approximating a RUM from Distributions on k-Slates [88.32814292632675]
与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。
我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
論文 参考訳（メタデータ） (2023-05-22T17:43:34Z) - The star-shaped space of solutions of the spherical negative perceptron [4.511197686627054]
低エネルギー構成が複雑な連結構造によく見られることを示す。
我々は、他のほとんどの解と連結された非定型ハイマージンの部分集合を同定する。
論文 参考訳（メタデータ） (2023-05-18T00:21:04Z) - PolarMask++: Enhanced Polar Representation for Single-Shot Instance
Segmentation and Beyond [47.518550130850755]
PolarMaskは、極座標内のオブジェクトの輪郭を予測するものとしてインスタンス分割問題を再構成する。
2つのモジュールは慎重に設計されている。
サンプル良質の中心の例への柔らかい極の中心および極性IoUの損失)。
PolarMaskは完全に畳み込み型であり、ほとんどのオフザシェルフ検出方法に簡単に組み込むことができる。
論文 参考訳（メタデータ） (2021-05-05T16:55:53Z) - Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the
Multi-Objective Minimum Spanning Tree Problem [12.098400820502635]
我々は,Spanning Tree (MST) 問題を単目的および多目的バージョンで検討する。
我々は、低い支配数の観点から低いランクのエッジの選択に重点を置くバイアス付き突然変異を導入する。
我々は、非偏見または偏見のあるエッジ選択を決定する突然変異演算子の組み合わせが、最悪の場合、上界(unbiased mutation)を示すことを示した。
論文 参考訳（メタデータ） (2020-04-22T07:47:00Z) - Joint Wasserstein Distribution Matching [89.86721884036021]
JDM問題(Joint Distribution matching)は、2つのドメインの関節分布を一致させるために双方向マッピングを学習することを目的としており、多くの機械学習およびコンピュータビジョンアプリケーションで発生している。
2つの領域における関節分布のワッサーシュタイン距離を最小化することにより、JDM問題に対処することを提案する。
そこで我々は,難解な問題を簡単な最適化問題に還元する重要な定理を提案し,その解法を開発した。
論文 参考訳（メタデータ） (2020-03-01T03:39:00Z) - On the Sample Complexity and Optimization Landscape for Quadratic
Feasibility Problems [7.722592882475735]
複素ベクトル $mathbfxin mathbbCn$ を $mangle A-imathbfx, mathbfxr_i=1m から復元する問題を考える。
一般に、NP-ハードが解ける二次問題であるだけでなく、実際には特定できないかもしれない。
論文 参考訳（メタデータ） (2020-02-04T00:35:09Z) - Searching for polarization in signed graphs: a local spectral approach [16.384728228938574]
本稿では、符号付きグラフにおける局所偏極群を局所バイアス固有確率として求める問題を定式化する。
局所バイアスベクトルは符号付きグラフ上のチェーガー定数の局所的な類似点に関して近似保証付きコミュニティを見つけるのに利用できることを示す。
論文 参考訳（メタデータ） (2020-01-26T06:30:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。