論文の概要: Graph energy as a measure of community detectability in networks

• arxiv url: http://arxiv.org/abs/2601.05065v1
• Date: Thu, 08 Jan 2026 16:10:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-12 13:49:32.58222
• Title: Graph energy as a measure of community detectability in networks
• Title（参考訳）: ネットワークにおけるコミュニティ検出可能性の指標としてのグラフエネルギー
• Authors: Lucas Böttcher, Mason A. Porter, Santo Fortunato,
• Abstract要約: PPM と ER ネットワーク間のグラフエネルギーの差は、検出可能性閾値において異なる遷移を持つことを示す。 この結果から,標準グラフ行列は依然として検出不能かつ検出不能なコミュニティでパラメータ領域を分離することができることが示唆された。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A key challenge in network science is the detection of communities, which are sets of nodes in a network that are densely connected internally but sparsely connected to the rest of the network. A fundamental result in community detection is the existence of a nontrivial threshold for community detectability on sparse graphs that are generated by the planted partition model (PPM). Below this so-called ``detectability limit'', no community-detection method can perform better than random chance. Spectral methods for community detection fail before this detectability limit because the eigenvalues corresponding to the eigenvectors that are relevant for community detection can be absorbed by the bulk of the spectrum. One can bypass the detectability problem by using special matrices, like the non-backtracking matrix, but this requires one to consider higher-dimensional matrices. In this paper, we show that the difference in graph energy between a PPM and an Erdős--Rényi (ER) network has a distinct transition at the detectability threshold even for the adjacency matrices of the underlying networks. The graph energy is based on the full spectrum of an adjacency matrix, so our result suggests that standard graph matrices still allow one to separate the parameter regions with detectable and undetectable communities.
• Abstract（参考訳）: ネットワーク科学における重要な課題は、ネットワーク内のノードの集合であるコミュニティの検出である。 コミュニティ検出の基本的な結果は、植民分割モデル(PPM)によって生成されるスパースグラフに、コミュニティ検出可能性のための非自明なしきい値が存在することである。 このような「検出可能性限界」の下には、コミュニティ検出法はランダムな確率よりも優れた性能を発揮できない。 コミュニティ検出に関係のある固有ベクトルに対応する固有値は、このスペクトルの大部分に吸収されるため、コミュニティ検出のためのスペクトル法はこの検出可能性限界の前に失敗する。 非追跡行列のような特別な行列を用いることで検出可能性問題を回避できるが、これは高次元行列を考える必要がある。 本稿では,PPMとエルデシュ-レーニ (ER) ネットワーク間のグラフエネルギーの差が,基礎となるネットワークの隣接行列であっても,検出可能性しきい値において異なる遷移を持つことを示す。 グラフエネルギーは隣接行列の全スペクトルに基づいており、この結果から、標準グラフ行列は依然として検出不能かつ検出不能なコミュニティでパラメータ領域を分離することができることを示唆している。

関連論文リスト

• Non-Dissipative Graph Propagation for Non-Local Community Detection [14.99394337842476]
  本稿では,新しい教師なしコミュニティ検出手法であるunsupervised Antisymmetric Graph Neural Network (uAGNN)を紹介する。 従来手法では長距離依存性を活用できなかった,中・中程度のヘテロフレンドリーな環境下での uAGNN の優れた性能を示す。 これらの結果は、多様なグラフ環境において、教師なしのコミュニティ検出のための強力なツールとしての uAGNN の可能性を強調している。
  論文  参考訳（メタデータ） (2025-08-15T12:26:48Z)
• Multitask Active Learning for Graph Anomaly Detection [48.690169078479116]
  MultItask acTIve Graph Anomaly Detection framework,すなわちMITIGATEを提案する。 ノード分類タスクを結合することにより、MITIGATEは既知の異常を伴わずに配布外ノードを検出する能力を得る。 4つのデータセットに関する実証的研究は、MITIGATEが異常検出のための最先端の手法を著しく上回っていることを示している。
  論文  参考訳（メタデータ） (2024-01-24T03:43:45Z)
• BOURNE: Bootstrapped Self-supervised Learning Framework for Unified Graph Anomaly Detection [50.26074811655596]
  自己指導型自己学習(BOURNE)に基づく新しい統合グラフ異常検出フレームワークを提案する。 ノードとエッジ間のコンテキスト埋め込みを交換することで、ノードとエッジの異常を相互に検出できる。 BOURNEは、負のサンプリングを必要としないため、大きなグラフを扱う際の効率を高めることができる。
  論文  参考訳（メタデータ） (2023-07-28T00:44:57Z)
• ARISE: Graph Anomaly Detection on Attributed Networks via Substructure Awareness [70.60721571429784]
  サブ構造認識(ARISE)による属性付きネットワーク上の新しいグラフ異常検出フレームワークを提案する。 ARISEは、異常を識別するグラフのサブ構造に焦点を当てている。 実験により、ARISEは最先端の属性付きネットワーク異常検出(ANAD)アルゴリズムと比較して、検出性能が大幅に向上することが示された。
  論文  参考訳（メタデータ） (2022-11-28T12:17:40Z)
• Unsupervised Constrained Community Detection via Self-Expressive Graph Neural Network [17.209458751421018]
  グラフニューラルネットワーク(GNN)は、ノード分類やリンク予測など、複数のグラフ下流タスクで有望なパフォーマンスを達成することができる。 伝統的に、GNNは半教師付きまたは自己教師型損失関数で訓練され、その後、クラスタリングアルゴリズムを適用してコミュニティを検出する。 我々のソリューションはエンドツーエンドでトレーニングされ、複数の公開データセット上で最先端のコミュニティ検出のパフォーマンスを達成する。
  論文  参考訳（メタデータ） (2020-11-28T07:17:30Z)
• Amortized Probabilistic Detection of Communities in Graphs [39.56798207634738]
  そこで我々は,アモータイズされたコミュニティ検出のためのシンプルなフレームワークを提案する。 我々はGNNの表現力と最近のアモータイズクラスタリングの手法を組み合わせる。 我々は、合成および実データセットに関するフレームワークから、いくつかのモデルを評価する。
  論文  参考訳（メタデータ） (2020-10-29T16:18:48Z)
• Community detection in networks using graph embeddings [0.615738282053772]
  ベンチマークグラフ上のコミュニティを検出するために,いくつかのグラフ埋め込み手法をテストした。 埋め込み手法のパラメータが好適に選択された場合、性能は同等である。 この発見は、ネットワークを埋め込み、ポイントをグループ化する高い計算コストとともに、コミュニティ検出において、現在の埋め込み技術はネットワーククラスタリングアルゴリズムよりも改善されたものではないことを示唆している。
  論文  参考訳（メタデータ） (2020-09-11T07:49:21Z)
• A unified framework for spectral clustering in sparse graphs [47.82639003096941]
  正規化ラプラシア行列の便利なパラメータ化形式はスパースネットワークにおけるスペクトルクラスタリングに利用できることを示す。 また、この提案された行列と、現在一般的な非バックトラック行列であるベーテ・ヘッセン行列との間の重要な関係を示す。
  論文  参考訳（メタデータ） (2020-03-20T10:58:37Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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