論文の概要: Contextual Stochastic Block Model: Sharp Thresholds and Contiguity

• arxiv url: http://arxiv.org/abs/2011.09841v1
• Date: Sun, 15 Nov 2020 16:14:14 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-25 07:12:07.297067
• Title: Contextual Stochastic Block Model: Sharp Thresholds and Contiguity
• Title（参考訳）: 文脈確率ブロックモデル:シャープ閾値と連続性
• Authors: Chen Lu, Subhabrata Sen
• Abstract要約: 本研究では,文脈ブロックモデルarXiv:1807.09596[cs.SI],arXiv:1607.02675[stat.ME]におけるコミュニティ検出について検討する。
• 参考スコア（独自算出の注目度）: 5.735930507508431
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We study community detection in the contextual stochastic block model arXiv:1807.09596 [cs.SI], arXiv:1607.02675 [stat.ME]. In arXiv:1807.09596 [cs.SI], the second author studied this problem in the setting of sparse graphs with high-dimensional node-covariates. Using the non-rigorous cavity method from statistical physics, they conjectured the sharp limits for community detection in this setting. Further, the information theoretic threshold was verified, assuming that the average degree of the observed graph is large. It is expected that the conjecture holds as soon as the average degree exceeds one, so that the graph has a giant component. We establish this conjecture, and characterize the sharp threshold for detection and weak recovery.
• Abstract（参考訳）: コンテクスト確率ブロックモデルarxiv:1807.09596 [cs.si], arxiv:1607.02675 [stat.me]におけるコミュニティ検出について検討した。 arXiv:1807.09596 [cs.SI] において、第2の著者は高次元ノード共変量を持つスパースグラフの設定においてこの問題を研究した。 統計物理学の非リゴラスキャビティ法を用いて、彼らはこの設定におけるコミュニティ検出の鋭い限界を予想した。 さらに、観測されたグラフの平均度が大きいと仮定して、情報理論しきい値が検証された。 予想は、平均次数が 1 を超えるとすぐに成立し、グラフが巨大な成分を持つことが期待される。 我々はこの予想を確立し、検出と弱い回復のための鋭い閾値を特徴づける。

関連論文リスト

• Testing Dependency of Weighted Random Graphs [4.0554893636822]
  本研究では,2つのランダムグラフ間のエッジ依存性を検出するタスクについて検討する。 一般のエッジウェイト分布に対して、最適テストが情報理論上可能か不可能となるしきい値を確立する。
  論文  参考訳（メタデータ） (2024-09-23T10:07:41Z)
• Information-Theoretic Thresholds for Planted Dense Cycles [52.076657911275525]
  本研究では,社会科学や生物科学においてユビキタスな小世界ネットワークのランダムグラフモデルについて検討する。 植え込み高密度サイクルの検出と回復の両面において、情報理論の閾値を$n$, $tau$、エッジワイド信号対雑音比$lambda$で特徴づける。
  論文  参考訳（メタデータ） (2024-02-01T03:39:01Z)
• arXiv4TGC: Large-Scale Datasets for Temporal Graph Clustering [52.63652741011945]
  我々は、時間グラフクラスタリングのための新しい学術データセットであるarXiv4TGCを構築した。 特に、最大のデータセットであるarXivLargeには、13万のラベル付き利用可能なノードと1000万の時間エッジが含まれている。 arXiv4TGCのクラスタリング性能は、異なるモデルを評価する上でより明白である。
  論文  参考訳（メタデータ） (2023-06-08T06:37:04Z)
• Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold [3.6052935394000234]
  ブロックモデルは、ネットワーク構造データのクラスタリングとコミュニティ検出のための標準ランダムグラフモデルである。 ネットワークトポロジに基づく推定器は、モデルパラメータが一定の閾値以下である場合、スパースグラフの確率よりも大幅に向上する。 パラメータ領域全体でラベルの任意の部分で実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-05-24T00:03:25Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。 我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
  論文  参考訳（メタデータ） (2021-12-29T18:46:52Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。 次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
  論文  参考訳（メタデータ） (2021-05-03T16:36:27Z)
• Statistical and computational thresholds for the planted $k$-densest sub-hypergraph problem [13.808053718325635]
  我々は,$d$-uniform ハイパーグラフ上に$k$-densest サブハイパーグラフを植え付けることで回復する問題を考察する。 この根本的な問題は、例えば、コミュニティの検出、平均ケースの複雑さ、神経科学の応用など、様々な文脈に現れる。
  論文  参考訳（メタデータ） (2020-11-23T16:02:12Z)
• Robustness of Community Detection to Random Geometric Perturbations [16.575947847660778]
  我々は、頂点間の接続が、潜在(かつ観測されていない)ランダムな幾何グラフによって摂動されるブロックモデルを考える。 目的は、スペクトル法がランダムグラフの存在(あるいはそうでない)に非依存であっても、この種のノイズに対して堅牢であることを証明することである。
  論文  参考訳（メタデータ） (2020-11-09T10:15:40Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。