論文の概要: 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$であることを示す。
我々の限界を証明するために、適応政策と、彼ら自身の関心を持つ可能性のある非適応政策を関連付ける新しい手法を導入する。
関連論文リスト
- Identifying General Mechanism Shifts in Linear Causal Representations [58.6238439611389]
我々は,未知の潜在因子の線形混合を観測する線形因果表現学習環境について考察する。
近年の研究では、潜伏要因の復元や、それに基づく構造因果モデルの構築が可能であることが示されている。
非常に穏やかな標準仮定の下では、シフトしたノードの集合を識別することが可能である。
論文 参考訳（メタデータ） (2024-10-31T15:56:50Z) - The Heterophilic Snowflake Hypothesis: Training and Empowering GNNs for Heterophilic Graphs [59.03660013787925]
ヘテロフィリー・スノーフレーク仮説を導入し、ヘテロ親和性グラフの研究をガイドし、促進するための効果的なソリューションを提供する。
観察の結果,我々のフレームワークは多種多様なタスクのための多目的演算子として機能することがわかった。
さまざまなGNNフレームワークに統合することができ、パフォーマンスを詳細に向上し、最適なネットワーク深さを選択するための説明可能なアプローチを提供する。
論文 参考訳（メタデータ） (2024-06-18T12:16:00Z) - Graph Sparsification via Mixture of Graphs [67.40204130771967]
そこで我々はMixture-of-Graphs (MoG)を導入し、各ノードに対して動的に調整されたプルーニングソリューションを選択する。
MoGには複数のスパシファイアの専門家が組み込まれており、それぞれが独自のスパーシリティレベルとプルーニング基準によって特徴付けられ、各ノードに対して適切な専門家を選択する。
5つのGNNを備えた4つの大規模OGBデータセットと2つのスーパーピクセルデータセットの実験により、MoGはより高い空間レベルのサブグラフを識別することを示した。
論文 参考訳（メタデータ） (2024-05-23T07:40:21Z) - 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) - Effects of Graph Convolutions in Deep Networks [8.937905773981702]
多層ネットワークにおけるグラフ畳み込みの効果に関する厳密な理論的理解を示す。
単一のグラフ畳み込みは、多層ネットワークがデータを分類できる手段間の距離のレギュレーションを拡大することを示す。
ネットワーク層間の異なる組み合わせに配置されたグラフ畳み込みの性能に関する理論的および実証的な知見を提供する。
論文 参考訳（メタデータ） (2022-04-20T08:24:43Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。