論文の概要: Randomized spectral co-clustering for large-scale directed networks
- arxiv url: http://arxiv.org/abs/2004.12164v3
- Date: Sat, 9 Apr 2022 06:05:26 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-09 21:34:37.058429
- Title: Randomized spectral co-clustering for large-scale directed networks
- Title(参考訳): 大規模指向ネットワークのためのランダム化スペクトルクラスタリング
- Authors: Xiao Guo, Yixuan Qiu, Hai Zhang, Xiangyu Chang
- Abstract要約: 共同クラスタリングは、有向ネットワークの送信者と受信者を同時にクラスタ化することを目的としている。
スケッチ技術を活用し、2つのランダム化スペクトルコクラスタリングアルゴリズムを導出する。
我々は、それらの近似誤差率と誤クラスタリング誤差率を確立し、共クラスタリング文学の最先端結果よりも優れた境界を示す。
- 参考スコア(独自算出の注目度): 15.486507430729052
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Directed networks are broadly used to represent asymmetric relationships
among units. Co-clustering aims to cluster the senders and receivers of
directed networks simultaneously. In particular, the well-known spectral
clustering algorithm could be modified as the spectral co-clustering to
co-cluster directed networks. However, large-scale networks pose great
computational challenges to it. In this paper, we leverage sketching techniques
and derive two randomized spectral co-clustering algorithms, one
\emph{random-projection-based} and the other \emph{random-sampling-based}, to
accelerate the co-clustering of large-scale directed networks. We theoretically
analyze the resulting algorithms under two generative models -- the stochastic
co-block model and the degree-corrected stochastic co-block model, and
establish their approximation error rates and misclustering error rates,
indicating better bounds than the state-of-the-art results of co-clustering
literature. Numerically, we design and conduct simulations to support our
theoretical results and test the efficiency of the algorithms on real networks
with up to millions of nodes. A publicly available R package \textsf{RandClust}
is developed for better usability and reproducibility of the proposed methods.
- Abstract(参考訳): 有向ネットワークは、単位間の非対称関係を表すために広く使われる。
共同クラスタリングは、有向ネットワークの送信者と受信者を同時にクラスタ化することを目的としている。
特に、よく知られたスペクトルクラスタリングアルゴリズムは、共クラスタ指向ネットワークへのスペクトルクラスタリングとして修正することができる。
しかし、大規模ネットワークは大きな計算上の課題をもたらす。
本稿では,2つのランダム化スペクトル共クラスタ化アルゴリズムを導出する。1つは \emph{random-projection-based} ともう1つは \emph{random-sampling-based} を用いて,大規模有向ネットワークの共クラスタ化を高速化する。
統計的共ブロックモデルと次数補正共ブロックモデルという2つの生成モデルの下で得られたアルゴリズムを理論的に解析し、それらの近似誤差率と誤クラスタリング誤差率を確立し、共クラスタリング文学の最先端結果よりも優れた境界を示す。
理論的結果を支援するシミュレーションを設計・実行し,最大数百万のノードを持つ実ネットワーク上でアルゴリズムの効率性をテストする。
提案手法のユーザビリティ向上と再現性向上のために, 公開されている R パッケージ \textsf{RandClust} を開発した。
関連論文リスト
- Rethinking Clustered Federated Learning in NOMA Enhanced Wireless
Networks [60.09912912343705]
本研究では,新しいクラスタ化フェデレーション学習(CFL)アプローチと,非独立かつ同一に分散した(非IID)データセットを統合することのメリットについて検討する。
データ分布における非IIDの度合いを測定する一般化ギャップの詳細な理論的解析について述べる。
非IID条件によって引き起こされる課題に対処する解決策は、特性の分析によって提案される。
論文 参考訳(メタデータ) (2024-03-05T17:49:09Z) - Optimal Clustering of Discrete Mixtures: Binomial, Poisson, Block
Models, and Multi-layer Networks [9.57586103097079]
多層ネットワークが存在する場合のクラスタリングネットワークの基本的限界について検討する。
混合多層ブロックモデル (MMSBM) では, 最適ネットワーククラスタリング誤差率の最小値が指数関数形式であることを示す。
本稿では,ノード分割とサンプル分割の両方を含むテンソルベースアルゴリズムを含む,新しい2段階ネットワーククラスタリング手法を提案する。
論文 参考訳(メタデータ) (2023-11-27T07:48:50Z) - Efficient Bilateral Cross-Modality Cluster Matching for Unsupervised Visible-Infrared Person ReID [56.573905143954015]
本稿では, クラスタ間マッチングによるモダリティギャップを低減するための, クラスタマッチングに基づく新たな学習フレームワークを提案する。
このような監視信号の下では、クラスタレベルで特徴を協調的に整列させるために、モダリティ・特定・モダリティ・非依存(MSMA)コントラスト学習フレームワークが提案されている。
公開SYSU-MM01とRegDBデータセットの実験により,提案手法の有効性が示された。
論文 参考訳(メタデータ) (2023-05-22T03:27:46Z) - DeepCluE: Enhanced Image Clustering via Multi-layer Ensembles in Deep
Neural Networks [53.88811980967342]
本稿では,Ensembles (DeepCluE) を用いたDeep Clusteringを提案する。
ディープニューラルネットワークにおける複数のレイヤのパワーを活用することで、ディープクラスタリングとアンサンブルクラスタリングのギャップを埋める。
6つの画像データセットの実験結果から、最先端のディープクラスタリングアプローチに対するDeepCluEの利点が確認されている。
論文 参考訳(メタデータ) (2022-06-01T09:51:38Z) - Perfect Spectral Clustering with Discrete Covariates [68.8204255655161]
本稿では,大規模なスパースネットワークのクラスにおいて,高い確率で完全クラスタリングを実現するスペクトルアルゴリズムを提案する。
本手法は,スペクトルクラスタリングによる一貫した潜在構造回復を保証する最初の方法である。
論文 参考訳(メタデータ) (2022-05-17T01:41:06Z) - Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
結合ネットワークトポロジ推論は、異種グラフ信号から複数のグラフラプラシア行列を学習する標準的な問題を表す。
新規な構造化融合正規化に基づく一般グラフ推定器を提案する。
提案するグラフ推定器は高い計算効率と厳密な理論保証の両方を享受できることを示す。
論文 参考訳(メタデータ) (2021-03-05T04:42:32Z) - KCoreMotif: An Efficient Graph Clustering Algorithm for Large Networks
by Exploiting k-core Decomposition and Motifs [6.1734015475373765]
スペクトルクラスタリングは、グラフ構造化データ(ネットワーク)の最も一般的なアルゴリズムの1つである
そこで本稿では,kコア分解とモチーフを利用したグラフクラスタリングアルゴリズムKCoreMotifを提案する。
提案したグラフクラスタリングアルゴリズムは,大規模ネットワークに対して正確かつ効率的であることを示す。
論文 参考訳(メタデータ) (2020-08-21T12:21:05Z) - Local Graph Clustering with Network Lasso [90.66817876491052]
局所グラフクラスタリングのためのネットワークLasso法の統計的および計算的性質について検討する。
nLassoによって提供されるクラスタは、クラスタ境界とシードノードの間のネットワークフローを通じて、エレガントに特徴付けられる。
論文 参考訳(メタデータ) (2020-04-25T17:52:05Z) - Motif-Based Spectral Clustering of Weighted Directed Networks [6.1448102196124195]
クラスタリングは、様々な分野の応用において、ネットワーク分析に不可欠な技術である。
一つのアプローチは、モチーフ隣接行列を用いて高次構造を捕捉し、クラスタ化することである。
本稿では,重み付きネットワーク上での隣接行列のモチーフとして,新しい,計算に有用な行列式を提案する。
論文 参考訳(メタデータ) (2020-04-02T22:45:28Z) - Randomized Spectral Clustering in Large-Scale Stochastic Block Models [13.366036495177923]
統計的観点からランダム化されたスケッチアルゴリズムを用いてスペクトルクラスタリングについて検討する。
弱い条件下では、ランダム化されたスペクトルクラスタリングアルゴリズムは、元のスペクトルクラスタリングアルゴリズムと同じ理論的境界に導かれる。
Rclustと呼ばれる新しいRパッケージが開発され、一般に公開されている。
論文 参考訳(メタデータ) (2020-01-20T04:15:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。