論文の概要: A practical test for a planted community in heterogeneous networks

• arxiv url: http://arxiv.org/abs/2101.05928v1
• Date: Fri, 15 Jan 2021 01:34:14 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-28 23:58:54.363919
• Title: A practical test for a planted community in heterogeneous networks
• Title（参考訳）: 異種ネットワークにおける植栽コミュニティの実践的テスト
• Authors: Mingao Yuan and Qian Wen
• Abstract要約: 実ネットワークデータの場合、密な部分グラフの存在は一般に不明である。 テストのパワーを理論的に検討し、シミュレーションと実データ例を用いてテストの性能を評価します。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: One of the fundamental task in graph data mining is to find a planted community(dense subgraph), which has wide application in biology, finance, spam detection and so on. For a real network data, the existence of a dense subgraph is generally unknown. Statistical tests have been devised to testing the existence of dense subgraph in a homogeneous random graph. However, many networks present extreme heterogeneity, that is, the degrees of nodes or vertexes don't concentrate on a typical value. The existing tests designed for homogeneous random graph are not straightforwardly applicable to the heterogeneous case. Recently, scan test was proposed for detecting a dense subgraph in heterogeneous(inhomogeneous) graph(\cite{BCHV19}). However, the computational complexity of the scan test is generally not polynomial in the graph size, which makes the test impractical for large or moderate networks. In this paper, we propose a polynomial-time test that has the standard normal distribution as the null limiting distribution. The power of the test is theoretically investigated and we evaluate the performance of the test by simulation and real data example.
• Abstract（参考訳）: グラフデータマイニングにおける基本的なタスクの1つは、生物学、ファイナンス、スパム検出などに広く応用されている、植栽されたコミュニティ(dense subgraph)を見つけることである。 実際のネットワークデータでは、密度の高い部分グラフの存在は一般に不明である。 統計的テストは、均質なランダムグラフにおける密な部分グラフの存在をテストするために考案された。 しかし、多くのネットワークは極端な不均一性を示し、すなわちノードや頂点の次数は典型的な値に集中しない。 均質なランダムグラフ用に設計された既存のテストは、不均質なケースに簡単には適用できない。 近年,不均質(不均質)グラフ(\cite{BCHV19})中の高密度部分グラフを検出するための走査試験が提案されている。 しかし、スキャンテストの計算複雑性は一般にグラフサイズの多項式ではないため、大規模なネットワークや中程度のネットワークでは実用的ではない。 本稿では,標準正規分布をヌル極限分布とする多項式時間テストを提案する。 実験のパワーを理論的に検討し,シミュレーションと実データを用いて実験の性能評価を行った。

関連論文リスト

• Testing Dependency of Weighted Random Graphs [4.0554893636822]
  本研究では,2つのランダムグラフ間のエッジ依存性を検出するタスクについて検討する。 一般のエッジウェイト分布に対して、最適テストが情報理論上可能か不可能となるしきい値を確立する。
  論文  参考訳（メタデータ） (2024-09-23T10:07:41Z)
• Network two-sample test for block models [16.597465729143813]
  2組のネットワークが同じモデルに由来するかどうかを判定することを目的とするネットワークの2サンプルテスト問題を考える。 ネットワーク分布にブロックモデル(SBM)を適用するのは,その解釈可能性と,より一般的なモデルに近似する可能性からである。 推定されたネットワークパラメータにマッチする効率的なアルゴリズムを導入し、サンプル内およびサンプル間の情報を適切に組み合わせ、コントラスト化することで、強力なテストを実現する。
  論文  参考訳（メタデータ） (2024-06-10T04:28:37Z)
• Collaborative non-parametric two-sample testing [55.98760097296213]
  目標は、null仮説の$p_v = q_v$が拒否されるノードを特定することである。 グラフ構造を効率的に活用する非パラメトリックコラボレーティブ2サンプルテスト(CTST)フレームワークを提案する。 提案手法は,f-divergence Estimation, Kernel Methods, Multitask Learningなどの要素を統合する。
  論文  参考訳（メタデータ） (2024-02-08T14:43:56Z)
• Precise Error Rates for Computationally Efficient Testing [75.63895690909241]
  本稿では,計算複雑性に着目した単純な対数-単純仮説テストの問題を再考する。 線形スペクトル統計に基づく既存の試験は、I型とII型の誤差率の間の最良のトレードオフ曲線を達成する。
  論文  参考訳（メタデータ） (2023-11-01T04:41:16Z)
• Graph Out-of-Distribution Generalization with Controllable Data Augmentation [51.17476258673232]
  グラフニューラルネットワーク(GNN)は,グラフ特性の分類において異常な性能を示した。 トレーニングとテストデータの選択バイアスが原因で、分散偏差が広まっています。 仮想サンプルの分布偏差を測定するためのOODキャリブレーションを提案する。
  論文  参考訳（メタデータ） (2023-08-16T13:10:27Z)
• Seq-HGNN: Learning Sequential Node Representation on Heterogeneous Graph [57.2953563124339]
  本稿では,シーケンシャルノード表現,すなわちSeq-HGNNを用いた新しい異種グラフニューラルネットワークを提案する。 Heterogeneous Graph Benchmark (HGB) と Open Graph Benchmark (OGB) の4つの広く使われているデータセットについて広範な実験を行った。
  論文  参考訳（メタデータ） (2023-05-18T07:27:18Z)
• Lost in the Shuffle: Testing Power in the Presence of Errorful Network Vertex Labels [2.8406702588667807]
  2サンプルネットワーク仮説テストは、医学、神経科学、社会学といった様々な分野に適用するための重要な推論タスクである。 これらのテスト手法の多くは、ネットワーク間の通信が既知であるという暗黙の仮定の下で機能する。 このシャッフルによる電力損失は、ランダムドット積とブロックモデルネットワークの文脈で理論的に検討されている。
  論文  参考訳（メタデータ） (2022-08-18T05:27:18Z)
• AZ-whiteness test: a test for uncorrelated noise on spatio-temporal graphs [19.407150082045636]
  グラフに対する最初の白さテスト、すなわちグラフのノードに関連付けられた連続時系列に対する連続白さテストを示す。 グラフストリームの予測残差を解析することにより、品質時間予測モデルの評価にどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2022-04-23T19:43:19Z)
• 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)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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