論文の概要: Maximizing Influence of Leaders in Social Networks
- arxiv url: http://arxiv.org/abs/2106.06128v1
- Date: Fri, 11 Jun 2021 02:31:46 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-26 23:55:43.235806
- Title: Maximizing Influence of Leaders in Social Networks
- Title（参考訳）: ソーシャルネットワークにおけるリーダーの影響の最大化
- Authors: Xiaotian Zhou and Zhongzhi Zhang
- Abstract要約: 我々は、$n$ノードと$m$エッジを持つソーシャルネットワークにおける意見力学のDeGrootモデルに対するエッジ加算問題を考察する。
提案アルゴリズムは,100万以上のノードを持つ大規模ネットワークに対して,効率的かつ効果的であることを示す。
- 参考スコア（独自算出の注目度）: 15.05158252504978
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The operation of adding edges has been frequently used to the study of
opinion dynamics in social networks for various purposes. In this paper, we
consider the edge addition problem for the DeGroot model of opinion dynamics in
a social network with $n$ nodes and $m$ edges, in the presence of a small
number $s \ll n$ of competing leaders with binary opposing opinions 0 or 1.
Concretely, we pose and investigate the problem of maximizing the equilibrium
overall opinion by creating $k$ new edges in a candidate edge set, where each
edge is incident to a 1-valued leader and a follower node. We show that the
objective function is monotone and submodular. We then propose a simple greedy
algorithm with an approximation factor $(1-\frac{1}{e})$ that approximately
solves the problem in $O(n^3)$ time. Moreover, we provide a fast algorithm with
a $(1-\frac{1}{e}-\epsilon)$ approximation ratio and
$\tilde{O}(mk\epsilon^{-2})$ time complexity for any $\epsilon>0$, where
$\tilde{O}(\cdot)$ notation suppresses the ${\rm poly} (\log n)$ factors.
Extensive experiments demonstrate that our second approximate algorithm is
efficient and effective, which scales to large networks with more than a
million nodes.
- Abstract（参考訳）: エッジの追加操作は、様々な目的のソーシャルネットワークにおける意見力学の研究に頻繁に用いられている。
本稿では,2つの対立する意見が 0 または 1 で競合するリーダー数 $s \ll n$ の存在下で,$n$ノードと$m$エッジを持つソーシャルネットワークにおいて,DeGroot の意見力学モデルに対するエッジ加算問題を考察する。
具体的には、各エッジが1値のリードと追従ノードにインシデントされる候補エッジセットに$k$新しいエッジを作成することで、均衡全体の意見の最大化という問題を提起し、調査する。
目的関数は単調かつ部分モジュラーであることが示される。
次に、近似係数$(1-\frac{1}{e})$の単純なグリージーアルゴリズムを提案し、この問題をおよそ$O(n^3)$時間で解く。
さらに、$(1--\frac{1}{e}-\epsilon)$の近似比と$\tilde{o}(mk\epsilon^{-2})$の任意の$\epsilon>0$の時間複雑性を持つ高速アルゴリズムを提供し、ここで$\tilde{o}(\cdot)$表記は${\rm poly} (\log n)$因子を抑制する。
大規模な実験により、我々の2番目の近似アルゴリズムは効率的かつ効果的であることが証明された。
関連論文リスト
- Deep Neural Networks: Multi-Classification and Universal Approximation [0.0]
我々は,幅2ドル,深さ2N+4M-1$のReLUディープニューラルネットワークが,$N$要素からなる任意のデータセットに対して有限標本記憶を達成できることを実証した。
また、$W1,p$関数を近似するための深さ推定と$Lp(Omega;mathbbRm)$ for $mgeq1$を近似するための幅推定も提供する。
論文 参考訳（メタデータ） (2024-09-10T14:31:21Z) - A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering [18.29151197560866]
我々は[Makarychev, Makarychev and Vijayaraghavan, STOC'12] の半ランダムグラフモデルを考える。
時間アルゴリズムは、カットされた$(A, B)$がサイズ$Omega(alpha)$である限り、alphad Cutの問題を最大$O(alpha)$ [MMV'12]に近似することが知られている。
この問題の微細な複雑さについて検討し,[MMV'12]と同じような性能を示す最初のニア線形時間サブルーチンを提示する。
論文 参考訳（メタデータ） (2024-06-07T11:40:54Z) - Minimizing Polarization in Noisy Leader-Follower Opinion Dynamics [17.413930396663833]
本稿では,ノイズの多いソーシャルネットワークにおけるリーダ・フォロワーの意見ダイナミクスに対する偏極最適化の問題について考察する。
私たちは、すべてのリーダの意見が同一であり、変化のない、一般的なリーダフォローのDeGrootモデルを採用しています。
目的関数が単調で超モジュラーであることを示し、その後、近似係数が1-1/e$の単純なグレディアルゴリズムを提案し、O((n-q)3)$時間で問題を解く。
論文 参考訳（メタデータ） (2023-08-14T08:52:24Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Most Neural Networks Are Almost Learnable [52.40331776572531]
固定された$epsilon>0$とdeep $i$に対して、深さ$i$のランダムなXavierネットワークを学習するポリ時間アルゴリズムが存在することを示す。
このアルゴリズムは時間とサンプルの複雑さが$(bard)mathrmpoly(epsilon-1)$であり、$bar d$はネットワークのサイズである。
シグモイドやReLU様の活性化の場合、境界は$(bard)mathrmpolylog(eps)に改善できる。
論文 参考訳（メタデータ） (2023-05-25T22:27:42Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳（メタデータ） (2021-07-22T14:25:16Z) - Quantum complexity of minimum cut [0.2538209532048867]
隣接行列モデルにおける最小カット問題の量子クエリと時間複雑性を特徴付ける。
我々のアルゴリズムは、Apers and de Wolf (FOCS 2020) によるグラフスカラー化のための量子アルゴリズムを用いており、Kawarabayashi and Thorup (STOC 2015) と Rubinstein, Schramm and Weinberg (ITCS 2018) による準最小カットの構造に関する結果である。
論文 参考訳（メタデータ） (2020-11-19T13:51:49Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。