論文の概要: Consistency of spectral clustering for directed network community
detection
- arxiv url: http://arxiv.org/abs/2109.10319v1
- Date: Tue, 21 Sep 2021 17:01:36 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-22 14:29:56.082776
- Title: Consistency of spectral clustering for directed network community
detection
- Title(参考訳): 有向ネットワークコミュニティ検出のためのスペクトルクラスタリングの一貫性
- Authors: Huan Qing and Jingli Wang
- Abstract要約: 有向ネットワークは、生物学、社会学、生理学、コンピュータ科学など、様々な分野に現れる。
本研究では,隣接行列の特異分解に基づくスペクトルクラスタリング手法を構築し,有向ブロックモデルにおけるコミュニティの不均一性を検出する。
我々の理論的結果は、バランスの取れたクラスタを持つ有向ネットワーク、類似の次数を持つノードを持つ有向ネットワーク、および有向Erd"os-R'enyiグラフなど、いくつかの特別な有向ネットワークに革新をもたらす。
- 参考スコア(独自算出の注目度): 1.370633147306388
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Directed networks appear in various areas, such as biology, sociology,
physiology and computer science. However, at present, most network analysis
ignores the direction. In this paper, we construct a spectral clustering method
based on the singular decomposition of the adjacency matrix to detect community
in directed stochastic block model (DiSBM). By considering a sparsity
parameter, under some mild conditions, we show the proposed approach can
consistently recover hidden row and column communities for different scaling of
degrees.
By considering the degree heterogeneity of both row and column nodes, we
further establish a theoretical framework for directed degree corrected
stochastic block model (DiDCSBM). We show that the spectral clustering method
stably yields consistent community detection for row clusters and column
clusters under mild constraints on the degree heterogeneity. Our theoretical
results under DiSBM and DiDCSBM provide some innovations on some special
directed networks, such as directed network with balanced clusters, directed
network with nodes enjoying similar degrees, and the directed Erd\"os-R\'enyi
graph. Furthermore, our theoretical results under DiDCSBM are consistent with
those under DiSBM when DiDCSBM degenerates to DiSBM.
- Abstract(参考訳): 有向ネットワークは生物学、社会学、生理学、計算機科学など様々な分野に現れる。
しかし、現在、ほとんどのネットワーク分析は方向を無視している。
本稿では, 隣接行列の特異分解に基づくスペクトルクラスタリング法を構築し, 有向確率ブロックモデル (disbm) におけるコミュニティを検出する。
疎度パラメータを考慮し、いくつかの温和な条件下で、隠れた列と列のコミュニティを連続的に復元し、次数の異なるスケールで再現可能であることを示す。
列ノードと列ノードの次数不均一性を考慮し,有向次数補正確率ブロックモデル(didcsbm)の理論的枠組みをさらに確立する。
スペクトルクラスタリング法は, 次数不均一性の軽度制約下で, 行クラスタと列クラスタに対して一貫したコミュニティ検出を安定的に行うことを示す。
DiSBMとDiDCSBMの理論的結果は、バランスの取れたクラスタを持つ有向ネットワーク、類似の次数を持つノードを持つ有向ネットワーク、Erd\"os-R\'enyiグラフなど、いくつかの特別な有向ネットワークに革新をもたらす。
さらに,DiDCSBM が DiSBM に退縮した場合に,DiDCSBM の理論的結果は DiSBM と一致する。
関連論文リスト
- Community Detection in the Multi-View Stochastic Block Model [47.43048484980115]
本稿では,無神論的な観点から,複数の潜在的相関グラフ上でのコミュニティ検出の問題について考察する。
我々はまず,同じノードの集合上で相関グラフを生成するために設計された多視点情報ブロックモデル (MVSBM) と呼ばれるランダムグラフモデルを考案した。
論文 参考訳(メタデータ) (2024-01-17T13:39:38Z) - Bipartite mixed membership distribution-free model. A novel model for community detection in overlapping bipartite weighted networks [0.4972323953932129]
本稿では,BiMMDF(Bipartite Mixed Membership Distribution-Free)モデルを提案する。
我々のモデルでは、ノードのメンバシップに関連するブロック構造が期待されている限り、隣接行列は任意の分布に従うことができる。
理論的に一貫した推定を保証した効率的なアルゴリズムをBiMMDFに適合させる。
論文 参考訳(メタデータ) (2022-11-02T06:26:47Z) - Interpolation-based Correlation Reduction Network for Semi-Supervised
Graph Learning [49.94816548023729]
補間型相関低減ネットワーク(ICRN)と呼ばれる新しいグラフコントラスト学習手法を提案する。
提案手法では,決定境界のマージンを大きくすることで,潜在特徴の識別能力を向上させる。
この2つの設定を組み合わせることで、豊富なラベル付きノードと稀に価値あるラベル付きノードから豊富な監視情報を抽出し、離散表現学習を行う。
論文 参考訳(メタデータ) (2022-06-06T14:26:34Z) - Geometric Graph Representation Learning via Maximizing Rate Reduction [73.6044873825311]
学習ノード表現は、コミュニティ検出やノード分類などのグラフ解析において、さまざまな下流タスクの恩恵を受ける。
教師なしの方法でノード表現を学習するための幾何学グラフ表現学習(G2R)を提案する。
G2R は異なるグループ内のノードを異なる部分空間にマッピングし、各部分空間はコンパクトで異なる部分空間が分散される。
論文 参考訳(メタデータ) (2022-02-13T07:46:24Z) - Spectral embedding and the latent geometry of multipartite networks [67.56499794542228]
多くのネットワークはマルチパーティションであり、ノードはパーティションに分割され、同じパーティションのノードは接続されない。
本稿では,高次元空間の分割特異的な低次元部分空間近傍のスペクトル埋め込みにより得られるノード表現について述べる。
スペクトル埋め込み後の追従ステップとして,周辺次元ではなく固有次元のノード表現を復元する手法を提案する。
論文 参考訳(メタデータ) (2022-02-08T15:52:03Z) - Distribution-Free Models for Community Detection [0.0]
ノードを異なるコミュニティに分割するネットワークに対して,分散自由モデル (DFM) を提案する。
DFMは、非重み付きネットワークと重み付きネットワークの両方の一般的な、解釈可能な、識別可能なモデルである。
雑音行列を導入することにより、摂動解析の理論的枠組みを構築し、提案アルゴリズムが安定して一貫したコミュニティ検出をもたらすことを示す。
論文 参考訳(メタデータ) (2021-11-15T02:10:52Z) - Bipartite mixed membership stochastic blockmodel [1.370633147306388]
本研究では,BiMMSB (Bipartite mixed membership blockmodel) とBiMMSB (BiMMSB) の相互運用モデルを提案する。
また、BiMPCAと呼ばれる効率的なスペクトルアルゴリズムを開発し、有向ネットワーク内の行ノードと列ノードの両方の混合メンバーシップを推定します。
論文 参考訳(メタデータ) (2021-01-07T00:21:50Z) - Spectral Embedding of Graph Networks [76.27138343125985]
ローカルノードの類似性と接続性、グローバル構造をトレードオフする教師なしグラフ埋め込みを導入する。
埋め込みは一般化されたグラフ Laplacian に基づいており、固有ベクトルは1つの表現においてネットワーク構造と近傍近傍の両方をコンパクトにキャプチャする。
論文 参考訳(メタデータ) (2020-09-30T04:59:10Z) - A Multi-Semantic Metapath Model for Large Scale Heterogeneous Network
Representation Learning [52.83948119677194]
大規模不均一表現学習のためのマルチセマンティックメタパス(MSM)モデルを提案する。
具体的には,マルチセマンティックなメタパスに基づくランダムウォークを生成し,不均衡な分布を扱うヘテロジニアスな近傍を構築する。
提案するフレームワークに対して,AmazonとAlibabaの2つの挑戦的なデータセットに対して,体系的な評価を行う。
論文 参考訳(メタデータ) (2020-07-19T22:50:20Z) - Consistency of Spectral Clustering on Hierarchical Stochastic Block
Models [5.983753938303726]
実世界のネットワークにおけるコミュニティの階層構造について,汎用ブロックモデルを用いて検討する。
本手法の強い一貫性を,幅広いモデルパラメータで証明する。
既存のほとんどの研究とは異なり、我々の理論は接続確率が桁違いに異なるかもしれないマルチスケールネットワークをカバーしている。
論文 参考訳(メタデータ) (2020-04-30T01:08:59Z) - Community Detection in Bipartite Networks with Stochastic Blockmodels [0.0]
バイパーティイトネットワークでは、あるタイプのノードは、他のタイプのノードとの共通の接続パターンに従ってグループ化される。
これにより、ブロックモデル(SBM)が2部構成のコミュニティ検出の直感的な選択となる。
我々はSBMの非パラメトリックな定式化とそれに対応するアルゴリズムを導入し、二部ネットワークのコミュニティを効率的に見つける。
論文 参考訳(メタデータ) (2020-01-22T05:58:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。