論文の概要: Information-Theoretic Thresholds for Planted Dense Cycles
- arxiv url: http://arxiv.org/abs/2402.00305v1
- Date: Thu, 1 Feb 2024 03:39:01 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-02 16:35:19.812578
- Title: Information-Theoretic Thresholds for Planted Dense Cycles
- Title（参考訳）: 植物密集サイクルの情報理論しきい値
- Authors: Cheng Mao, Alexander S. Wein, Shenduo Zhang
- Abstract要約: 本研究では,社会科学や生物科学においてユビキタスな小世界ネットワークのランダムグラフモデルについて検討する。
植え込み高密度サイクルの検出と回復の両面において、情報理論の閾値を$n$, $tau$、エッジワイド信号対雑音比$lambda$で特徴づける。
- 参考スコア（独自算出の注目度）: 52.076657911275525
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a random graph model for small-world networks which are ubiquitous
in social and biological sciences. In this model, a dense cycle of expected
bandwidth $n \tau$, representing the hidden one-dimensional geometry of
vertices, is planted in an ambient random graph on $n$ vertices. For both
detection and recovery of the planted dense cycle, we characterize the
information-theoretic thresholds in terms of $n$, $\tau$, and an edge-wise
signal-to-noise ratio $\lambda$. In particular, the information-theoretic
thresholds differ from the computational thresholds established in a recent
work for low-degree polynomial algorithms, thereby justifying the existence of
statistical-to-computational gaps for this problem.
- Abstract（参考訳）: 社会・生物科学においてユビキタスな小世界ネットワークのためのランダムグラフモデルについて検討する。
このモデルでは、期待される帯域幅$n \tau$の密度サイクルは、頂点の隠れた一次元幾何学を表し、n$頂点上の周囲ランダムグラフに植え付けられる。
植え込み高密度サイクルの検出と回復の両面において、情報理論の閾値を$n$, $\tau$、エッジワイド信号対雑音比$\lambda$で特徴づける。
特に、情報理論閾値は、最近の低次多項式アルゴリズムの研究で確立された計算しきい値とは異なるため、この問題に対する統計的-計算的ギャップの存在を正当化する。
関連論文リスト
- Aligning Embeddings and Geometric Random Graphs: Informational Results and Computational Approaches for the Procrustes-Wasserstein Problem [12.629532305482423]
Procrustes-Wstein問題(英語版)は、2つの高次元の点雲を教師なしの設定でマッチングするものである。
2つのデータセットが$X,Y$で、$mathbbRd$の$n$データポイントで構成されています。
そこで我々は,フランク=ウルフ凸緩和法を用いて,変換とレバーベリングを代替的に推定するPing-Passerongアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-23T13:18:51Z) - Analysis and Approximate Inference of Large Random Kronecker Graphs [4.417282202068703]
大規模なランダムクロネッカーグラフの隣接性は分解可能であることを示す。
本稿では,鍵グラフパラメータを推論するデノワーズ・アンド・ソルブの手法を提案する。
論文 参考訳（メタデータ） (2023-06-14T13:09:38Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳（メタデータ） (2023-02-13T22:51:07Z) - Unveiling the Sampling Density in Non-Uniform Geometric Graphs [69.93864101024639]
グラフを幾何学グラフとみなす: ノードは基礎となる計量空間からランダムにサンプリングされ、その距離が指定された近傍半径以下であれば任意のノードが接続される。
ソーシャルネットワークでは、コミュニティは密集したサンプル領域としてモデル化でき、ハブはより大きな近傍半径を持つノードとしてモデル化できる。
我々は,未知のサンプリング密度を自己監督的に推定する手法を開発した。
論文 参考訳（メタデータ） (2022-10-15T08:01:08Z) - Semi-Supervised Clustering of Sparse Graphs: Crossing the
Information-Theoretic Threshold [3.6052935394000234]
ブロックモデルは、ネットワーク構造データのクラスタリングとコミュニティ検出のための標準ランダムグラフモデルである。
ネットワークトポロジに基づく推定器は、モデルパラメータが一定の閾値以下である場合、スパースグラフの確率よりも大幅に向上する。
パラメータ領域全体でラベルの任意の部分で実現可能であることを示す。
論文 参考訳（メタデータ） (2022-05-24T00:03:25Z) - Inverting brain grey matter models with likelihood-free inference: a
tool for trustable cytoarchitecture measurements [62.997667081978825]
脳の灰白質細胞構造の特徴は、体密度と体積に定量的に敏感であり、dMRIでは未解決の課題である。
我々は新しいフォワードモデル、特に新しい方程式系を提案し、比較的スパースなb殻を必要とする。
次に,提案手法を逆転させるため,確率自由推論 (LFI) として知られるベイズ解析から最新のツールを適用した。
論文 参考訳（メタデータ） (2021-11-15T09:08:27Z) - Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on
Higher-Order Voronoi Diagrams [69.4411417775822]
逆例は機械学習モデルにおいて広く研究されている現象である。
そこで本研究では,$k$-nearest 近傍分類の逆ロバスト性を評価するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-11-19T08:49:10Z) - Fractal Gaussian Networks: A sparse random graph model based on Gaussian
Multiplicative Chaos [12.096252285460814]
フラクタルガウスネットワーク(FGN)と呼ばれる新しいネットワークモデルを提案する。
FGNはよく定義され解析的に抽出可能なフラクタル構造を具現化する。
論文 参考訳（メタデータ） (2020-08-07T08:37:36Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。