論文の概要: Planted Bipartite Graph Detection
- arxiv url: http://arxiv.org/abs/2302.03658v1
- Date: Tue, 7 Feb 2023 18:18:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-08 15:21:05.915804
- Title: Planted Bipartite Graph Detection
- Title(参考訳): 植込み二部グラフ検出
- Authors: Asaf Rotenberg and Wasim Huleihel and Ofer Shayevitz
- Abstract要約: ランダムグラフに隠れた二部グラフを検出するタスクについて検討する。
我々は、この検出問題に対して、密度とスパース状態の両方において、厳密な上界と下界を導出する。
上記の問題の変種を考えると、少なくとも$mathsfQ$ edge queryを使用することで、グラフの比較的小さな部分しか観察できない。
- 参考スコア(独自算出の注目度): 23.50927042762206
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the task of detecting a hidden bipartite subgraph in a given
random graph. Specifically, under the null hypothesis, the graph is a
realization of an Erd\H{o}s-R\'{e}nyi random graph over $n$ vertices with edge
density $q$. Under the alternative, there exists a planted $k_{\mathsf{R}}
\times k_{\mathsf{L}}$ bipartite subgraph with edge density $p>q$. We derive
asymptotically tight upper and lower bounds for this detection problem in both
the dense regime, where $q,p = \Theta\left(1\right)$, and the sparse regime
where $q,p = \Theta\left(n^{-\alpha}\right), \alpha \in \left(0,2\right]$.
Moreover, we consider a variant of the above problem, where one can only
observe a relatively small part of the graph, by using at most $\mathsf{Q}$
edge queries. For this problem, we derive upper and lower bounds in both the
dense and sparse regimes.
- Abstract(参考訳): ランダムグラフに隠れた二部グラフを検出するタスクについて検討する。
特にヌル仮説の下では、グラフは erd\h{o}s-r\'{e}nyi ランダムグラフを、エッジ密度 $q$ を持つ$n$ 頂点上で実現している。
代替として、k_{\mathsf{r}} \times k_{\mathsf{l}}$ bipartite subgraph with edge density $p>q$がある。
我々は、この検出問題に対して、$q,p = \Theta\left(1\right)$, and the sparse regime where $q,p = \Theta\left(n^{-\alpha}\right), \alpha \in \left(0,2\right]$の漸近的に強い上界と下界を導く。
さらに、上記の問題の変種を考えると、グラフの比較的小さな部分のみを、少なくとも$\mathsf{Q}$ edge queryを用いて観測することができる。
この問題に対して、我々は密度と疎結合の両方において上界と下界を導出する。
関連論文リスト
- Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。
我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。
平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
論文 参考訳(メタデータ) (2023-04-17T10:38:08Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳(メタデータ) (2023-02-13T22:51:07Z) - Statistical limits of correlation detection in trees [0.7826806223782055]
本稿では,2本の観測木$(t,t')$が独立に標本化されているか,あるいは相関関係のある関節分布から採取されているかを調べる。
グラフアライメントにより,片側テストの存在条件について検討する。
このようなテストは$s leq sqrtalpha$に対して存在せず、そのようなテストは$s > sqrtalpha$, for $lambda$十分に大きいときに存在します。
論文 参考訳(メタデータ) (2022-09-27T22:26:53Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳(メタデータ) (2022-05-30T14:28:02Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳(メタデータ) (2021-10-21T18:43:00Z) - Inferring Hidden Structures in Random Graphs [13.031167737538881]
本研究では,ランダムなグラフ上に植えられた群集群集の検出と復元の2つの推論問題について検討する。
我々は、パラメータ $(n,k,q)$ や $Gamma_k$ の特定の性質の観点から、構造を検出・復元するための下限を導出し、これらの下限を達成するための計算学的に最適なアルゴリズムを示す。
論文 参考訳(メタデータ) (2021-10-05T09:39:51Z) - Random Subgraph Detection Using Queries [45.55323995672117]
植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。
任意の(おそらくランダム化される)アルゴリズムは、$mathsfQ = Omega(fracn2k2chi4(p||q)log2n)$アダプティブクエリを生成する必要がある。
我々は、$mathsfQ = O(fracn3) とすることで、高い確率で植込み部分グラフを検出する準多項式時間アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-10-02T07:41:17Z) - Testing correlation of unlabeled random graphs [18.08210501570919]
ラベルなしノードを持つ2つのランダムグラフ間のエッジ相関を検出する問題について検討する。
これは仮説テスト問題として定式化され、ヌル仮説の下では、2つのグラフは独立に生成される。
代替として、2つのグラフは、ある潜在ノード対応の下ではエッジ関連であるが、ヌルと同じ辺分布を持つ。
論文 参考訳(メタデータ) (2020-08-23T19:19:45Z) - On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
論文 参考訳(メタデータ) (2019-06-02T03:03:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。