論文の概要: Minimizing Polarization in Noisy Leader-Follower Opinion Dynamics
- arxiv url: http://arxiv.org/abs/2308.07008v1
- Date: Mon, 14 Aug 2023 08:52:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-15 13:57:41.942803
- Title: Minimizing Polarization in Noisy Leader-Follower Opinion Dynamics
- Title（参考訳）: 雑音型リーダ・フォロワオピニオンダイナミクスにおける分極最小化
- Authors: Wanyue Xu and Zhongzhi Zhang
- Abstract要約: 本稿では,ノイズの多いソーシャルネットワークにおけるリーダ・フォロワーの意見ダイナミクスに対する偏極最適化の問題について考察する。
私たちは、すべてのリーダの意見が同一であり、変化のない、一般的なリーダフォローのDeGrootモデルを採用しています。
目的関数が単調で超モジュラーであることを示し、その後、近似係数が1-1/e$の単純なグレディアルゴリズムを提案し、O((n-q)3)$時間で問題を解く。
- 参考スコア（独自算出の注目度）: 17.413930396663833
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The operation of creating edges has been widely applied to optimize relevant
quantities of opinion dynamics. In this paper, we consider a problem of
polarization optimization for the leader-follower opinion dynamics in a noisy
social network with $n$ nodes and $m$ edges, where a group $Q$ of $q$ nodes are
leaders, and the remaining $n-q$ nodes are followers. We adopt the popular
leader-follower DeGroot model, where the opinion of every leader is identical
and remains unchanged, while the opinion of every follower is subject to white
noise. The polarization is defined as the steady-state variance of the
deviation of each node's opinion from leaders' opinion, which equals one half
of the effective resistance $\mathcal{R}_Q$ between the node group $Q$ and all
other nodes. Concretely, we propose and study the problem of minimizing
$\mathcal{R}_Q$ by adding $k$ new edges with each incident to a node in $Q$. We
show that the objective function is monotone and supermodular. We then propose
a simple greedy algorithm with an approximation factor $1-1/e$ that
approximately solves the problem in $O((n-q)^3)$ time. To speed up the
computation, we also provide a fast algorithm to compute
$(1-1/e-\eps)$-approximate effective resistance $\mathcal{R}_Q$, the running
time of which is $\Otil (mk\eps^{-2})$ for any $\eps>0$, where the $\Otil
(\cdot)$ notation suppresses the ${\rm poly} (\log n)$ factors. Extensive
experiment results show that our second algorithm is both effective and
efficient.
- Abstract（参考訳）: エッジを作成する操作は、関連する意見ダイナミクスの量を最適化するために広く適用されてきた。
本稿では,ノードがn$,エッジがm$,ノードがq$,ノードがq$,ノードがn〜q$,ノードがフォロワである,うるさいソーシャルネットワークにおいて,リーダ-フォロワーの意見ダイナミクスに対する分極最適化の問題を考える。
私たちは、すべてのリーダの意見が同じで変わらず、すべてのリーダの意見がホワイトノイズの対象となる、一般的なリーダフォローのdegrootモデルを採用しています。
偏極化は、各ノードの意見のずれをリーダーの意見から定常的分散と定義されており、これは、ノード群 $q$ と他の全てのノードとの間の効果的な抵抗 $\mathcal{r}_q$ の半減に等しい。
具体的には、ノードにインシデント毎に$k$の新たなエッジを追加することで、$\mathcal{r}_q$を最小化する問題を提案し、検討する。
目的関数は単調かつ超モジュラーであることを示す。
次に、近似係数が1-1/e$の単純なグリージーアルゴリズムを提案し、O((n-q)^3) の時間で問題を解く。
計算を高速化するために、$(1-1/e-\eps)$-approximate effective resistance $\mathcal{r}_q$ を計算する高速アルゴリズムも提供しています。
実験の結果,第2のアルゴリズムは効率的かつ効率的であることが判明した。
関連論文リスト
- Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time [19.25942907402098]
動的相関クラスタリング問題について,textitadaptive$ edge label flipsを用いて検討した。
相関クラスタリングでは、エッジを$(+)$または$(-)$とラベル付けした$n$-vertex完全グラフが与えられる。
本稿では, 対数ロバスト性を持つ動的設定について考察する。ここでは, $textitadaptive$ adversary がアルゴリズムの現在の出力に基づいてエッジのラベルを反転させることができる。
論文 参考訳（メタデータ） (2024-11-15T06:26:37Z) - Online Matrix Completion: A Collaborative Approach with Hott Items [19.781869063637387]
M$ユーザ,$N$アイテム,$T$ラウンド,未知のランク-$r$報酬行列$Rin mathbbRMtimes N$のオンライン設定における下位行列補完問題について検討する。
論文 参考訳（メタデータ） (2024-08-11T18:49:52Z) - Dynamic Correlation Clustering in Sublinear Update Time [33.079608335361286]
動的ノードストリームにおける相関クラスタリングの古典的問題について検討する。
この設定では、ノードは時間とともに追加またはランダムに削除され、各ノードペアは正または負のエッジで接続される。
我々は,$O(1)$-approximationを$O$(polylog $n$)アモートした更新時間で維持するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-13T14:07:15Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - Faster Sampling from Log-Concave Distributions over Polytopes via a
Soft-Threshold Dikin Walk [28.431572772564518]
我々は、$d$-dimensional log-concave distribution $pi(theta) propto e-f(theta)$からポリトープ$K$に制約された$m$不等式をサンプリングする問題を考える。
我々の主な成果は、少なくとも$O((md + d L2 R2) times MDomega-1) log(fracwdelta)$ arithmetic operation to sample from $pi$ の "soft-warm' variant of the Dikin walk Markov chain" である。
論文 参考訳（メタデータ） (2022-06-19T11:33:07Z) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳（メタデータ） (2022-03-18T18:50:52Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - Maximizing Influence of Leaders in Social Networks [15.05158252504978]
我々は、$n$ノードと$m$エッジを持つソーシャルネットワークにおける意見力学のDeGrootモデルに対するエッジ加算問題を考察する。
提案アルゴリズムは,100万以上のノードを持つ大規模ネットワークに対して,効率的かつ効果的であることを示す。
論文 参考訳（メタデータ） (2021-06-11T02:31:46Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。