論文の概要: Is it easier to count communities than find them?

• arxiv url: http://arxiv.org/abs/2212.10872v1
• Date: Wed, 21 Dec 2022 09:35:19 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-22 15:48:04.744159
• Title: Is it easier to count communities than find them?
• Title（参考訳）: コミュニティを見つけるより、コミュニティを数えるのは簡単か?
• Authors: Cynthia Rush, Fiona Skerman, Alexander S. Wein and Dana Yang
• Abstract要約: コミュニティ構造が異なるモデル間の仮説テスト問題について考察する。 2つの選択肢間のテストは、コミュニティを見つけるのと同じくらい難しいことを示しています。
• 参考スコア（独自算出の注目度）: 82.90505487525533
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Random graph models with community structure have been studied extensively in the literature. For both the problems of detecting and recovering community structure, an interesting landscape of statistical and computational phase transitions has emerged. A natural unanswered question is: might it be possible to infer properties of the community structure (for instance, the number and sizes of communities) even in situations where actually finding those communities is believed to be computationally hard? We show the answer is no. In particular, we consider certain hypothesis testing problems between models with different community structures, and we show (in the low-degree polynomial framework) that testing between two options is as hard as finding the communities. In addition, our methods give the first computational lower bounds for testing between two different `planted' distributions, whereas previous results have considered testing between a planted distribution and an i.i.d. `null' distribution.
• Abstract（参考訳）: コミュニティ構造を持つランダムグラフモデルは文献で広く研究されている。 コミュニティ構造の検出と回復の両面で、統計学的および計算的相転移の興味深い展望が生まれている。 自然の未解決の疑問は、実際にコミュニティを見つけることが計算的に困難であると信じられている状況であっても、コミュニティ構造(例えば、コミュニティの数とサイズ)の特性を推測することは可能か? 答えはノーです。 特に,異なるコミュニティ構造を持つモデル間の仮説テスト問題を検討し,(低次多項式フレームワークにおいて)2つの選択肢間のテストはコミュニティを見つけるのと同じくらい困難であることを示す。 さらに,本手法は,2つの異なる'植物'分布間のテストにおいて,最初の計算下限を付与するが,以前の結果は,植木分布と'ヌル'分布間のテストについて検討している。

関連論文リスト

• Identifying General Mechanism Shifts in Linear Causal Representations [58.6238439611389]
  我々は,未知の潜在因子の線形混合を観測する線形因果表現学習環境について考察する。 近年の研究では、潜伏要因の復元や、それに基づく構造因果モデルの構築が可能であることが示されている。 非常に穏やかな標準仮定の下では、シフトしたノードの集合を識別することが可能である。
  論文  参考訳（メタデータ） (2024-10-31T15:56:50Z)
• On an application of graph neural networks in population based SHM [0.0]
  本研究の目的は,異なる大きさのトラスの最初の自然発生頻度を,異なる環境温度,異なるバー部材タイプで予測することである。 回帰の精度は、訓練に使われたものよりも多くのノードとメンバーを持つ構造でも満足できる。
  論文  参考訳（メタデータ） (2022-03-03T11:11:57Z)
• Sequential Community Mode Estimation [7.693649834261879]
  本研究では,集団内最大の集団を個体の連続的無作為なサンプリングによって同定する問題について検討する。 この問題に対する新しいアルゴリズムを提案し,解析し,任意のアルゴリズムの下でエラーの確率に関する情報理論の下限を確立する。
  論文  参考訳（メタデータ） (2021-11-16T15:05:40Z)
• Average-Case Communication Complexity of Statistical Problems [48.03761288397421]
  通信の複雑さは、ストリーミング、スケッチ、クエリベースのモデルにおける下位境界を証明する主要なツールである。 本稿では,ランダムグラフやマトリクスに植木構造を組み込んだ問題に対して,入力分布を保存する一般還元法を提案する。 我々は,植林した傾斜地を検知・発見するために,二者間・多者間通信の下限を導出する。
  論文  参考訳（メタデータ） (2021-07-03T03:31:37Z)
• Group Testing with a Graph Infection Spread Model [61.48558770435175]
  感染は個人間のつながりを通じて広がり、その結果、確率的クラスター形成構造と、個人に対する非i.d.感染状態が生じる。 そこで本研究では,既知の確率的感染拡散モデルを利用する2段階のサンプルグループテストアルゴリズムを提案する。 その結果, 感染率が高い場合でも, 集団検査により必要な検査数を大幅に削減できることが示唆された。
  論文  参考訳（メタデータ） (2021-01-14T18:51:32Z)
• Adjusted chi-square test for degree-corrected block models [13.122543280692641]
  次数補正ブロックモデル(DCSBM)の適合性テストを提案する。 単純な調整により、$d_i$ の調和平均が無限に成長する限り、統計は null の下で分布に収束する。 我々の分布結果は漸近的ではなく、明示的な定数を持ち、目標分布へのコルモゴロフ-スミルノフ距離の有限サンプル境界を与える。
  論文  参考訳（メタデータ） (2020-12-30T05:20:59Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  補間分類器間のテストエラーの完全な分布を正確に計算する手法を開発した。 テストエラーは、最悪の補間モデルのテストエラーから大きく逸脱する、小さな典型的な$varepsilon*$に集中する傾向にある。 以上の結果から,統計的学習理論における通常の解析手法は,実際に観測された優れた一般化性能を捉えるのに十分な粒度にはならない可能性が示唆された。
  論文  参考訳（メタデータ） (2020-06-22T21:12:31Z)
• Revealing consensus and dissensus between network partitions [0.0]
  コミュニティ検出手法は、ネットワークを同様の特性を持つノードのグループに分割し、その大規模構造を明らかにする。 分布全体を要約する単一分割「ポイント推定」という形で、それらの間のコンセンサスを確立するための多くの方法が存在する。 ここでは、一般に、基底分布が不均一すぎるとき、そのような点から一貫した答えを得ることはできないことを示す。 我々は,分割の複雑な集団を,既存のコンセンサスだけでなく,人口の要素間の不一致を捉える方法で特徴付け,要約するために設計された,包括的手法のセットを提供する。
  論文  参考訳（メタデータ） (2020-05-28T13:29:42Z)
• Provable Overlapping Community Detection in Weighted Graphs [3.04585143845864]
  重み付きグラフにおける重なり合うコミュニティを、純粋ノードの仮定を明示的に定義することなく検出する証明可能な方法を提案する。 我々のアプローチは凸最適化に基づいており、多くの有用な理論的性質がすでに知られている。 人工および実世界のデータセット上でのアルゴリズムの成功を実証する。
  論文  参考訳（メタデータ） (2020-04-15T15:25:46Z)
• Certified Robustness of Community Detection against Adversarial Structural Perturbation via Randomized Smoothing [81.71105567425275]
  本研究は, 対向構造摂動に対するコミュニティ検出の信頼性保証を初めて開発した。 このスムーズなコミュニティ検出手法は,任意のノード群を同一のコミュニティにグループ化する。 また,本手法を複数の実世界グラフ上で実験的に評価した。
  論文  参考訳（メタデータ） (2020-02-09T18:39:39Z)

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

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