論文の概要: Inference of a Rumor's Source in the Independent Cascade Model
- arxiv url: http://arxiv.org/abs/2205.12125v1
- Date: Tue, 24 May 2022 14:57:22 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-25 15:48:50.352584
- Title: Inference of a Rumor's Source in the Independent Cascade Model
- Title（参考訳）: 独立カスケードモデルにおけるうわさの発生源の推定
- Authors: Petra Berenbrink and Max Hahn-Klimroth and Dominik Kaaser and Lena
Krieg and Malin Rau
- Abstract要約: 能動ノードの集合の観点から,その過程のスナップショットを考慮し, 噂の情報源に対する最大確率推定器を提案する。
この結果は、サイクルフリーグラフに対して、確率推定器は関数 $t$ として非自明な位相遷移を行うことを示している。
- 参考スコア（独自算出の注目度）: 1.539942973115038
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the so-called Independent Cascade Model for rumor spreading or
epidemic processes popularized by Kempe et al.\ [2003]. In this model, a small
subset of nodes from a network are the source of a rumor. In discrete time
steps, each informed node "infects" each of its uninformed neighbors with
probability $p$. While many facets of this process are studied in the
literature, less is known about the inference problem: given a number of
infected nodes in a network, can we learn the source of the rumor? In the
context of epidemiology this problem is often referred to as patient zero
problem. It belongs to a broader class of problems where the goal is to infer
parameters of the underlying spreading model, see, e.g., Lokhov [NeurIPS'16] or
Mastakouri et al. [NeurIPS'20].
In this work we present a maximum likelihood estimator for the rumor's
source, given a snapshot of the process in terms of a set of active nodes $X$
after $t$ steps. Our results show that, for cycle-free graphs, the likelihood
estimator undergoes a non-trivial phase transition as a function $t$. We
provide a rigorous analysis for two prominent classes of acyclic network,
namely $d$-regular trees and Galton-Watson trees, and verify empirically that
our heuristics work well in various general networks.
- Abstract（参考訳）: 我々は、kempeらによって広められたうわさの拡散や流行の過程の、いわゆる独立カスケードモデルを考える。
\ [2003].
このモデルでは、ネットワークからのノードの小さなサブセットが、噂の源である。
離散時間ステップでは、各情報ノードは、確率$p$で、各非情報隣人に「影響」を与える。
このプロセスの多くの側面が文献で研究されているが、推論の問題についてはあまり知られていない。
疫学の文脈では、この問題は患者ゼロ問題と呼ばれることが多い。
これは、基盤となる拡散モデルのパラメータ、例えばlokhov [neurips'16] やmastakouri et alを推測することを目的とした、より広い種類の問題に属する。
〔neurips'20〕
本研究では,一組のアクティブノードが$X$の後に$t$のステップで処理のスナップショットを与えられた場合,噂の情報源に対する最大可能性推定器を示す。
その結果, サイクルフリーグラフの場合, 確率推定器は関数 $t$ として非自明な位相遷移を行うことがわかった。
d$-regular tree と galton-watson tree という2つの有名な非環状ネットワークの厳密な解析を行い、我々のヒューリスティックスが様々な一般ネットワークでうまく機能することを実証的に検証した。
関連論文リスト
- Identifying General Mechanism Shifts in Linear Causal Representations [58.6238439611389]
我々は,未知の潜在因子の線形混合を観測する線形因果表現学習環境について考察する。
近年の研究では、潜伏要因の復元や、それに基づく構造因果モデルの構築が可能であることが示されている。
非常に穏やかな標準仮定の下では、シフトしたノードの集合を識別することが可能である。
論文 参考訳（メタデータ） (2024-10-31T15:56:50Z) - Information-Theoretic Thresholds for Planted Dense Cycles [52.076657911275525]
本研究では,社会科学や生物科学においてユビキタスな小世界ネットワークのランダムグラフモデルについて検討する。
植え込み高密度サイクルの検出と回復の両面において、情報理論の閾値を$n$, $tau$、エッジワイド信号対雑音比$lambda$で特徴づける。
論文 参考訳（メタデータ） (2024-02-01T03:39:01Z) - Backward and Forward Inference in Interacting Independent-Cascade
Processes: A Scalable and Convergent Message-Passing Approach [1.1470070927586018]
本研究では,ネットワーク上に並列に分散する2つの拡散過程の過去と将来の進化を推定する問題について検討する。
ネットワークの初期状態と観測ショット$mathcalO_n$の正確な結合確率を導出する。
論文 参考訳（メタデータ） (2023-10-29T20:03:38Z) - Differentially Private Non-convex Learning for Multi-layer Neural
Networks [35.24835396398768]
本稿では,単一出力ノードを持つ(多層)完全連結ニューラルネットワークに対する差分的タンジェント最適化の問題に焦点をあてる。
ニューラルカーネル理論の最近の進歩を利用して、サンプルサイズとネットワーク幅の両方が十分に大きい場合に、最初の過剰人口リスクを提供する。
論文 参考訳（メタデータ） (2023-10-12T15:48:14Z) - Online Centralized Non-parametric Change-point Detection via Graph-based
Likelihood-ratio Estimation [77.81487285123147]
グラフの各ノードを、ほぼリアルタイムで同期して観測されるデータストリームを生成するようにします。
変更ポイント$tau$では、変更はノードのサブセット$C$で発生し、関連するノードストリームの確率分布に影響を与える。
本稿では,ポストチェンジとノードストリームの事前変更分布の確率比の直接推定に基づいて,$tau$を検出して$C$をローカライズするカーネルベースの新しい手法を提案する。
論文 参考訳（メタデータ） (2023-01-08T10:15:24Z) - On the Identifiability and Estimation of Causal Location-Scale Noise
Models [122.65417012597754]
位置スケール・異方性雑音モデル(LSNM)のクラスについて検討する。
症例によっては, 因果方向が同定可能であることが示唆された。
我々は,LSNMの2つの推定器を提案し,その1つは(非線形)特徴写像に基づく推定器と,1つはニューラルネットワークに基づく推定器を提案する。
論文 参考訳（メタデータ） (2022-10-13T17:18:59Z) - Learning the Structure of Large Networked Systems Obeying Conservation
Laws [5.86054250638667]
ネットワーク系における保存法則は、$X = B* Y$という形のバランス方程式としてモデル化することができる。
いくつかの実用的なシステムでは、ネットワーク構造はよく知られておらず、データから推定する必要がある。
高次元状態におけるこの問題に対する新たな$ell_1$-regularized maximum max 推定器を提案する。
論文 参考訳（メタデータ） (2022-06-14T18:16:52Z) - Correlation Functions in Random Fully Connected Neural Networks at
Finite Width [17.51364577113718]
この記事では、ガウスのランダムな重みとバイアスと$L$の隠蔽層を持つ完全に接続されたニューラルネットワークについて考察する。
有界非線形性に対しては、ネットワーク出力とその導関数の共役相関関数に対して1/n$の急激な再帰推定を与える。
いずれの場合も、深さと幅の比$L/n$は、個々のニューロンのゆらぎのスケールとニューロン間相関の大きさの両方を制御し、有効なネットワーク深さの役割を担っている。
論文 参考訳（メタデータ） (2022-04-03T11:57:18Z) - On the Neural Tangent Kernel Analysis of Randomly Pruned Neural Networks [91.3755431537592]
ニューラルネットワークのニューラルカーネル(NTK)に重みのランダムプルーニングが及ぼす影響について検討する。
特に、この研究は、完全に接続されたニューラルネットワークとそのランダムに切断されたバージョン間のNTKの等価性を確立する。
論文 参考訳（メタデータ） (2022-03-27T15:22:19Z) - Causal Inference Despite Limited Global Confounding via Mixture Models [4.721845865189578]
そのようなモデルの有限$k$-mixtureは、図式的により大きなグラフで表される。
空でないDAGの混合を学習するための最初のアルゴリズムを与える。
論文 参考訳（メタデータ） (2021-12-22T01:04:50Z) - The Separation Capacity of Random Neural Networks [78.25060223808936]
標準ガウス重みと一様分布バイアスを持つ十分に大きな2層ReLUネットワークは、この問題を高い確率で解くことができることを示す。
我々は、相互複雑性という新しい概念の観点から、データの関連構造を定量化する。
論文 参考訳（メタデータ） (2021-07-31T10:25:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。