論文の概要: Overlapping community detection in networks via sparse spectral
decomposition
- arxiv url: http://arxiv.org/abs/2009.10641v2
- Date: Mon, 15 Feb 2021 06:43:18 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-16 12:53:13.899999
- Title: Overlapping community detection in networks via sparse spectral
decomposition
- Title(参考訳): スパーススペクトル分解によるネットワーク上の重複コミュニティ検出
- Authors: Jes\'us Arroyo, Elizaveta Levina
- Abstract要約: 各ノードが複数のコミュニティに属することができるネットワークにおいて,重複するコミュニティメンバシップを推定する問題を考える。
本アルゴリズムは,反復しきい値を用いたスパース主部分空間推定に基づく。
アルゴリズムの固定点がブロックモデルの下での正しいノードメンバシップに対応することを示す。
- 参考スコア(独自算出の注目度): 1.0660480034605242
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of estimating overlapping community memberships in a
network, where each node can belong to multiple communities. More than a few
communities per node are difficult to both estimate and interpret, so we focus
on sparse node membership vectors. Our algorithm is based on sparse principal
subspace estimation with iterative thresholding. The method is computationally
efficient, with a computational cost equivalent to estimating the leading
eigenvectors of the adjacency matrix, and does not require an additional
clustering step, unlike spectral clustering methods. We show that a fixed point
of the algorithm corresponds to correct node memberships under a version of the
stochastic block model. The methods are evaluated empirically on simulated and
real-world networks, showing good statistical performance and computational
efficiency.
- Abstract(参考訳): 各ノードが複数のコミュニティに属することができるネットワークにおいて,重複するコミュニティメンバシップを推定する問題を考える。
ノード当たりのいくつかのコミュニティは、推定と解釈の両方が難しいため、スパースノードのメンバシップベクトルに焦点を当てる。
本アルゴリズムは反復しきい値付きスパース主部分空間推定に基づいている。
この方法は計算効率が良く、隣接行列の先頭固有ベクトルを推定する計算コストと同等であり、スペクトルクラスタリング法とは異なり、追加のクラスタリングステップを必要としない。
確率ブロックモデルのバージョンの下で,アルゴリズムの固定点が正しいノードメンバシップに対応することを示す。
これらの手法はシミュレーションおよび実世界のネットワーク上で実証的に評価され、優れた統計性能と計算効率を示す。
関連論文リスト
- Semi-supervised Community Detection via Structural Similarity Metrics [0.0]
本研究では,新しいノードのコミュニティラベルを推定することを目的とした,半教師付きコミュニティ検出問題について検討する。
本稿では,新しいノードとK$コミュニティ間の構造的類似度メトリック'を計算するアルゴリズムを提案する。
我々の知る限りでは、理論的な保証を提供する最初の半教師付きコミュニティ検出アルゴリズムである。
論文 参考訳(メタデータ) (2023-06-01T19:02:50Z) - Rethinking k-means from manifold learning perspective [122.38667613245151]
平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。
具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。
異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
論文 参考訳(メタデータ) (2023-05-12T03:01:41Z) - Implicit models, latent compression, intrinsic biases, and cheap lunches
in community detection [0.0]
コミュニティ検出は、ネットワークをノードのクラスタに分割して、その大規模な構造を要約することを目的としている。
いくつかのコミュニティ検出手法は、確率的生成モデルを通じてクラスタリングの目的を明示的に導出する。
他の方法は記述的であり、特定のアプリケーションによって動機付けられた目的に応じてネットワークを分割する。
本稿では,コミュニティ検出対象,推論対象,記述対象とそれに対応する暗黙的ネットワーク生成モデルとを関連付けるソリューションを提案する。
論文 参考訳(メタデータ) (2022-10-17T15:38:41Z) - Perfect Spectral Clustering with Discrete Covariates [68.8204255655161]
本稿では,大規模なスパースネットワークのクラスにおいて,高い確率で完全クラスタリングを実現するスペクトルアルゴリズムを提案する。
本手法は,スペクトルクラスタリングによる一貫した潜在構造回復を保証する最初の方法である。
論文 参考訳(メタデータ) (2022-05-17T01:41:06Z) - Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs [5.301300942803395]
カットベースの有向グラフ(グラフ)クラスタリングは、しばしばクラスタ内あるいはクラスタ間の疎結合を見つけることに焦点を当てる。
フローベースのクラスタリングでは、クラスタ間のエッジは一方向を向く傾向にあり、マイグレーションデータ、フードウェブ、トレーディングデータに見出されている。
論文 参考訳(メタデータ) (2022-03-02T20:07:04Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳(メタデータ) (2022-02-09T06:05:05Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳(メタデータ) (2021-12-07T18:50:17Z) - Mixed Membership Graph Clustering via Systematic Edge Query [22.77704627076251]
この研究は、ほとんど不完全なグラフのクラスタリングノードを考慮する。
問題設定の下では、エッジに関する少数のクエリしか作成できないが、グラフ全体はオブザーバブルではない。
この問題は,限定アノテーションを用いた大規模データクラスタリング,限定された調査リソースによるコミュニティ検出,グラフトポロジ推論などに適用できる。
論文 参考訳(メタデータ) (2020-11-25T19:19:05Z) - Spectral clustering on spherical coordinates under the degree-corrected
stochastic blockmodel [5.156484100374058]
次数補正ブロックモデルに基づく新しいスペクトルクラスタリングアルゴリズムを提案する。
その結果,コンピュータネットワークにおける競合手法よりも性能が向上した。
論文 参考訳(メタデータ) (2020-11-09T16:55:38Z) - A General Method for Robust Learning from Batches [56.59844655107251]
本稿では,バッチから頑健な学習を行う一般的なフレームワークについて考察し,連続ドメインを含む任意の領域に対する分類と分布推定の限界について考察する。
本手法は,一括分節分類,一括分節,単調,対数凹,ガウス混合分布推定のための,最初の頑健な計算効率の学習アルゴリズムを導出する。
論文 参考訳(メタデータ) (2020-02-25T18:53:25Z) - Quantized Decentralized Stochastic Learning over Directed Graphs [52.94011236627326]
有向グラフ上で通信する計算ノード間でデータポイントが分散される分散学習問題を考える。
モデルのサイズが大きくなるにつれて、分散学習は、各ノードが隣人にメッセージ(モデル更新)を送信することによる通信負荷の大きなボトルネックに直面します。
本稿では,分散コンセンサス最適化におけるプッシュサムアルゴリズムに基づく有向グラフ上の量子化分散学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-02-23T18:25:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。