論文の概要: Exact Community Recovery in Bipartite Networks

• arxiv url: http://arxiv.org/abs/2609.12445v1
• Date: Fri, 11 Sep 2026 05:08:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-15 07:38:31.628016
• Title: Exact Community Recovery in Bipartite Networks
• Title（参考訳）: バイパルタイトネットワークにおけるエクササイズ・コミュニティ・リカバリ
• Authors: Huan Qing,
• Abstract要約: バイパーティイトネットワークにおけるコミュニティ検出は、現代のデータ分析における根本的な問題である。 簡単なスペクトルクラスタリングアルゴリズムは、弱い条件下で高い確率で正確なリカバリを実現する。
• 参考スコア（独自算出の注目度）: 4.314956204483074
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Community detection in bipartite networks is a fundamental problem in modern data analysis, with applications in recommendation systems, biological networks, and social network analysis. Unlike conventional unipartite graphs, bipartite networks consist of two distinct types of nodes with edges only connecting across types, so recovering latent communities requires estimating labels on the two node types. The stochastic co-blockmodel is a classical probabilistic framework for such networks, yet theoretical guarantees for exact community recovery in this setting remain limited, especially when the number of communities grows, the community sizes are unbalanced, or the degrees are heterogeneous. In this work, we prove that a simple spectral clustering algorithm based on the diagonal-deleted Gram matrix achieves exact recovery with high probability under mild conditions on sparsity, community balance, and the number of clusters. We further extend the result to the degree-corrected stochastic co-blockmodel, where each node carries its own degree heterogeneity parameter, and show that a row-normalized version of the same algorithm maintains the exact recovery guarantee. Extensive experiments validate our theoretical findings.
• Abstract（参考訳）: 二部ネットワークにおけるコミュニティ検出は、リコメンデーションシステム、生物学的ネットワーク、ソーシャルネットワーク分析など、現代のデータ分析における根本的な問題である。 従来のユニパートグラフとは異なり、二部ネットワークは2つの異なるタイプのノードで構成されており、エッジはタイプをまたいでのみ接続される。 確率的コブロックモデルは、そのようなネットワークの古典的な確率的フレームワークであるが、この設定における正確なコミュニティ回復の理論的保証は、特にコミュニティの数が増えても、コミュニティのサイズが不均衡であるか、あるいは等級が不均一である場合に限られている。 本研究では, 対角線削除グラム行列に基づく単純なスペクトルクラスタリングアルゴリズムが, 疎度, コミュニティバランス, クラスタ数に対する軽度条件下で, 高い確率で正確なリカバリを実現することを証明した。 さらに、各ノードが独自の次数不均一性パラメータを持ち、同じアルゴリズムの行正規化バージョンが正確な回復保証を維持していることを示す。 大規模な実験は、我々の理論的な結果を検証する。

関連論文リスト

• Matrix Factorization Framework for Community Detection under the Degree-Corrected Block Model [48.989531198582704]
  我々は,DCBM推論を制約付き非負行列分解問題として再定義できることを示した。 我々のアプローチは、任意の特定のネットワーク構造に適応し、DCBMで表現可能な任意の構造を持つグラフに適用する。 合成および実ベンチマークネットワークの実験により,本手法はDCBMの推測に匹敵するコミュニティを検出する。
  論文  参考訳（メタデータ） (2026-01-09T19:16:29Z)
• Contrastive clustering based on regular equivalence for influential node identification in complex networks [10.538045764554019]
  ReCCは、影響のあるノード識別のための新しい非教師なしフレームワークである。 ネットワーク再構成損失を使用して事前トレーニングを行い、コントラストとクラスタリングの損失を組み合わせた微調整を行う。 大規模な実験により、ReCCはいくつかのベンチマークで最先端のアプローチより優れていることが示された。
  論文  参考訳（メタデータ） (2025-08-30T09:34:39Z)
• Semi-supervised Community Detection via Structural Similarity Metrics [0.0]
  本研究では,新しいノードのコミュニティラベルを推定することを目的とした,半教師付きコミュニティ検出問題について検討する。 本稿では,新しいノードとK$コミュニティ間の構造的類似度メトリック'を計算するアルゴリズムを提案する。 我々の知る限りでは、理論的な保証を提供する最初の半教師付きコミュニティ検出アルゴリズムである。
  論文  参考訳（メタデータ） (2023-06-01T19:02:50Z)
• Perfect Spectral Clustering with Discrete Covariates [68.8204255655161]
  本稿では,大規模なスパースネットワークのクラスにおいて,高い確率で完全クラスタリングを実現するスペクトルアルゴリズムを提案する。 本手法は,スペクトルクラスタリングによる一貫した潜在構造回復を保証する最初の方法である。
  論文  参考訳（メタデータ） (2022-05-17T01:41:06Z)
• Community detection for weighted bipartite networks [1.0965065178451106]
  citerohe2016coは、ネットワーク研究における二部グラフデータのコミュニティ構造を検出するツールとして、co-Blockmodel (ScBM)を提案した。 ここでは、重み付き二部ネットワークをモデル化するために、ScBMの分布制限を解放することにより、二部分布自由モデルを導入する。 我々のモデルは、隣接行列の生成要素に関する特定の分布を必要としないが、期待される隣接行列上のブロック構造のみである。
  論文  参考訳（メタデータ） (2021-09-21T17:01:36Z)
• Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
  本稿では,d-uniform hypergraph block model(d-HSBM)の正確な回復の基本的な限界について検討する。 精度の高いしきい値が存在し、正確な回復がしきい値の上に達成でき、その下には不可能であることを示す。
  論文  参考訳（メタデータ） (2021-05-11T03:39:08Z)
• Amortized Probabilistic Detection of Communities in Graphs [39.56798207634738]
  そこで我々は,アモータイズされたコミュニティ検出のためのシンプルなフレームワークを提案する。 我々はGNNの表現力と最近のアモータイズクラスタリングの手法を組み合わせる。 我々は、合成および実データセットに関するフレームワークから、いくつかのモデルを評価する。
  論文  参考訳（メタデータ） (2020-10-29T16:18:48Z)
• Consistency of Spectral Clustering on Hierarchical Stochastic Block Models [5.983753938303726]
  実世界のネットワークにおけるコミュニティの階層構造について,汎用ブロックモデルを用いて検討する。 本手法の強い一貫性を,幅広いモデルパラメータで証明する。 既存のほとんどの研究とは異なり、我々の理論は接続確率が桁違いに異なるかもしれないマルチスケールネットワークをカバーしている。
  論文  参考訳（メタデータ） (2020-04-30T01:08:59Z)
• Detecting Communities in Heterogeneous Multi-Relational Networks:A Message Passing based Approach [89.19237792558687]
  コミュニティは、ソーシャルネットワーク、生物学的ネットワーク、コンピュータおよび情報ネットワークを含むネットワークの共通の特徴である。 我々は,全同種ネットワークのコミュニティを同時に検出する効率的なメッセージパッシングに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-06T17:36:24Z)
• A unified framework for spectral clustering in sparse graphs [47.82639003096941]
  正規化ラプラシア行列の便利なパラメータ化形式はスパースネットワークにおけるスペクトルクラスタリングに利用できることを示す。 また、この提案された行列と、現在一般的な非バックトラック行列であるベーテ・ヘッセン行列との間の重要な関係を示す。
  論文  参考訳（メタデータ） (2020-03-20T10:58:37Z)

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

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