論文の概要: Better Bounds on the Adaptivity Gap of Influence Maximization under
Full-adoption Feedback
- arxiv url: http://arxiv.org/abs/2006.15374v1
- Date: Sat, 27 Jun 2020 14:43:34 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-16 08:17:48.820160
- Title: Better Bounds on the Adaptivity Gap of Influence Maximization under
Full-adoption Feedback
- Title(参考訳): 完全適応フィードバックによる影響最大化の適応ギャップに関するより良い境界
- Authors: Gianlorenzo D'Angelo, Debashmita Poddar, Cosimo Vinci
- Abstract要約: 影響カスケードによって到達されるノードの期待数を最大化する$k$ノードのセットを探します。
適応性ギャップは $lceil nrceil $ で上界であることを示し、$n$ はグラフ内のノード数である。
また、0-有界グラフ、すなわち無向グラフにおいて、適応性ギャップは少なくとも$frac3e3e3-1approx 3.16$であることを示す。
- 参考スコア(独自算出の注目度): 15.533908352376853
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the influence maximization (IM) problem, we are given a social network and
a budget $k$, and we look for a set of $k$ nodes in the network, called seeds,
that maximize the expected number of nodes that are reached by an influence
cascade generated by the seeds, according to some stochastic model for
influence diffusion. In this paper, we study the adaptive IM, where the nodes
are selected sequentially one by one, and the decision on the $i$th seed can be
based on the observed cascade produced by the first $i-1$ seeds. We focus on
the full-adoption feedback in which we can observe the entire cascade of each
previously selected seed and on the independent cascade model where each edge
is associated with an independent probability of diffusing influence.
Our main result is the first sub-linear upper bound that holds for any graph.
Specifically, we show that the adaptivity gap is upper-bounded by $\lceil
n^{1/3}\rceil $, where $n$ is the number of nodes in the graph. Moreover, we
improve over the known upper bound for in-arborescences from
$\frac{2e}{e-1}\approx 3.16$ to $\frac{2e^2}{e^2-1}\approx 2.31$. Finally, we
study $\alpha$-bounded graphs, a class of undirected graphs in which the sum of
node degrees higher than two is at most $\alpha$, and show that the adaptivity
gap is upper-bounded by $\sqrt{\alpha}+O(1)$. Moreover, we show that in
0-bounded graphs, i.e. undirected graphs in which each connected component is a
path or a cycle, the adaptivity gap is at most $\frac{3e^3}{e^3-1}\approx
3.16$. To prove our bounds, we introduce new techniques to relate adaptive
policies with non-adaptive ones that might be of their own interest.
- Abstract(参考訳): 影響最大化(im)問題では、ソーシャルネットワークと予算$k$が与えられ、影響拡散の確率モデルによれば、その影響カスケードによって生じる影響カスケードによって達成される期待ノード数を最大化する、seedと呼ばれるネットワーク内の一連の$k$ノードを探します。
本稿では,ノードを順次1つずつ選択する適応型imについて検討し,最初の$i-1$シードが生成する観察したカスケードに基づいて,$i$thシードの決定を行う。
我々は,事前に選択した各種子のカスケード全体を観察できるフルオプションフィードバックと,各エッジが拡散する影響の独立確率に関連付けられる独立カスケードモデルに注目した。
私たちの主な結果は、任意のグラフに対する最初の部分線型上界です。
具体的には、適応性ギャップが$\lceil n^{1/3}\rceil $によって上界であることを示し、$n$はグラフ内のノードの数である。
さらに, in-arborescenceの既知の上限を$\frac{2e}{e-1}\approx 3.16$から$\frac{2e^2}{e^2-1}\approx 2.31$に改善する。
最後に、次数 2 以上のノードの和が少なくとも$\alpha$であるような非方向グラフのクラスである $\alpha$-bounded graphs を研究し、適応性ギャップが $\sqrt{\alpha}+O(1)$ で上界であることを示す。
さらに、0-有界グラフ、すなわち各連結成分が経路あるいはサイクルである無向グラフにおいて、適応性ギャップは最大$\frac{3e^3}{e^3-1}\approx 3.16$であることを示す。
我々の限界を証明するために、適応政策と、彼ら自身の関心を持つ可能性のある非適応政策を関連付ける新しい手法を導入する。
関連論文リスト
- Causal Bandits for Linear Structural Equation Models [58.2875460517691]
本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。
グラフの構造は知られており、ノードは$N$である。
頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-08-26T16:21:31Z) - Graph Neural Network Bandits [89.31889875864599]
グラフ構造データ上で定義された報酬関数を用いた帯域最適化問題を考察する。
この設定の主な課題は、大きなドメインへのスケーリングと、多くのノードを持つグラフへのスケーリングである。
グラフニューラルネットワーク(GNN)を用いて報酬関数を推定できることを示す。
論文 参考訳(メタデータ) (2022-07-13T18:12:36Z) - Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
グラフに基づく相対的制約のない最小二乗重要度フィッティング(GRULSIF)
我々はこの考え方を、グラフベースの相対的非制約最小二乗重要度フィッティング(GRULSIF)と呼ばれる具体的な非パラメトリック手法で開発する。
我々は、ノード当たりの観測回数、グラフのサイズ、およびグラフ構造がタスク間の類似性をどの程度正確にエンコードしているかといった変数が果たす役割を強調する、協調的なアプローチの収束率を導出する。
論文 参考訳(メタデータ) (2022-05-28T15:37:03Z) - Effects of Graph Convolutions in Deep Networks [8.937905773981702]
多層ネットワークにおけるグラフ畳み込みの効果に関する厳密な理論的理解を示す。
単一のグラフ畳み込みは、多層ネットワークがデータを分類できる手段間の距離のレギュレーションを拡大することを示す。
ネットワーク層間の異なる組み合わせに配置されたグラフ畳み込みの性能に関する理論的および実証的な知見を提供する。
論文 参考訳(メタデータ) (2022-04-20T08:24:43Z) - Geometric Graph Representation Learning via Maximizing Rate Reduction [73.6044873825311]
学習ノード表現は、コミュニティ検出やノード分類などのグラフ解析において、さまざまな下流タスクの恩恵を受ける。
教師なしの方法でノード表現を学習するための幾何学グラフ表現学習(G2R)を提案する。
G2R は異なるグループ内のノードを異なる部分空間にマッピングし、各部分空間はコンパクトで異なる部分空間が分散される。
論文 参考訳(メタデータ) (2022-02-13T07:46:24Z) - RaWaNet: Enriching Graph Neural Network Input via Random Walks on Graphs [0.0]
グラフニューラルネットワーク(GNN)の人気が高まっており、グラフで表されるデータに対して非常に有望な結果を示している。
本稿では,3つの選択された長さに基づいて,グラフのランダムなウォークデータ処理を提案する。すなわち,グラフ上の局所的および大域的ダイナミクスを捉えるために,長さ1,2の(正規)ウォークと長さ0,1$の分節ウォークを提案する。
本手法は, 処理ノードの特徴をネットワークに渡すことによって, 様々な分子データセット上で検証し, 分類および回帰処理を行う。
論文 参考訳(メタデータ) (2021-09-15T20:04:01Z) - Maximizing Influence of Leaders in Social Networks [15.05158252504978]
我々は、$n$ノードと$m$エッジを持つソーシャルネットワークにおける意見力学のDeGrootモデルに対するエッジ加算問題を考察する。
提案アルゴリズムは,100万以上のノードを持つ大規模ネットワークに対して,効率的かつ効果的であることを示す。
論文 参考訳(メタデータ) (2021-06-11T02:31:46Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳(メタデータ) (2021-03-02T06:53:44Z) - The Power of $D$-hops in Matching Power-Law Graphs [20.88345367293753]
適切な定義のD$ホップ地区における低次種子を利用する効率的なアルゴリズムを開発した。
Chung-Luランダムグラフモデルにおいて、$n$頂点, max degree$Theta(sqrtn)$, and the power-law exponent $2beta3$, we show that as soon as $D> frac4-beta3-beta$, by optimally select the first slice, with high probability our algorithm can correct with a constant fraction of the true pairs。
論文 参考訳(メタデータ) (2021-02-23T05:36:58Z) - Pipeline Interventions [15.27567660320295]
本稿では, 層状有向非巡回グラフと連続層間の遷移を規定する行列の集合によって定義されるエンフェペリン介入問題について述べる。
このグラフは、異なる人口の人々が機会を提供する方法のスタイル化されたモデルであり、最終的には何らかの報酬をもたらす。
我々は、社会福祉と、最も高い期待値の人口に対する価値を最大化しようとする公正なモチベーションの最大化という2つの目的を考察する。
論文 参考訳(メタデータ) (2020-02-16T15:28:29Z) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
論文 参考訳(メタデータ) (2020-02-08T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。