論文の概要: 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のアルゴリズムは効率的かつ効率的であることが判明した。
関連論文リスト
- 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) - Lower Bounds on the Worst-Case Complexity of Efficient Global
Optimization [11.523746174066702]
我々は、その対応する再生核ヒルベルト空間(RKHS)における球の計量エントロピーの観点から、効率的な大域最適化の複雑さに対する統一された下界を導出する。
この下界は、一般に使用される2乗指数核とマタン核の非適応探索アルゴリズムによって達成された上界にほぼ一致することを示す。
論文 参考訳(メタデータ) (2022-09-20T11:57:13Z) - 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) - Repeated Averages on Graphs [2.363388546004777]
我々は$frac(1-epsilon)2log2nlog n-O(n)$が$n$ノード上のすべての連結グラフに対する一般的な下界であることを証明する。
また、星、膨張星、ダンベル、サイクルなど、いくつかの重要なグラフの族に対して、$t_epsilon,1$の急激な等級も得られる。
論文 参考訳(メタデータ) (2022-05-09T20:18:31Z) - 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) - On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。
本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。
我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
論文 参考訳(メタデータ) (2020-08-15T11:06:45Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳(メタデータ) (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。