論文の概要: KCoreMotif: An Efficient Graph Clustering Algorithm for Large Networks
by Exploiting k-core Decomposition and Motifs
- arxiv url: http://arxiv.org/abs/2008.10380v1
- Date: Fri, 21 Aug 2020 12:21:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-26 21:29:29.300879
- Title: KCoreMotif: An Efficient Graph Clustering Algorithm for Large Networks
by Exploiting k-core Decomposition and Motifs
- Title(参考訳): KCoreMotif: kコア分解とモチーフの爆発による大規模ネットワークのための効率的なグラフクラスタリングアルゴリズム
- Authors: Gang Mei, Jingzhi Tu, Lei Xiao, Francesco Piccialli
- Abstract要約: スペクトルクラスタリングは、グラフ構造化データ(ネットワーク)の最も一般的なアルゴリズムの1つである
そこで本稿では,kコア分解とモチーフを利用したグラフクラスタリングアルゴリズムKCoreMotifを提案する。
提案したグラフクラスタリングアルゴリズムは,大規模ネットワークに対して正確かつ効率的であることを示す。
- 参考スコア(独自算出の注目度): 6.1734015475373765
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Clustering analysis has been widely used in trust evaluation on various
complex networks such as wireless sensors networks and online social networks.
Spectral clustering is one of the most commonly used algorithms for
graph-structured data (networks). However, the conventional spectral clustering
is inherently difficult to work with large-scale networks due to the fact that
it needs computationally expensive matrix manipulations. To deal with large
networks, in this paper, we propose an efficient graph clustering algorithm,
KCoreMotif, specifically for large networks by exploiting k-core decomposition
and motifs. The essential idea behind the proposed clustering algorithm is to
perform the efficient motif-based spectral clustering algorithm on k-core
subgraphs, rather than on the entire graph. More specifically, (1) we first
conduct the k-core decomposition of the large input network; (2) we then
perform the motif-based spectral clustering for the top k-core subgraphs; (3)
we group the remaining vertices in the rest (k-1)-core subgraphs into
previously found clusters; and finally obtain the desired clusters of the large
input network. To evaluate the performance of the proposed graph clustering
algorithm KCoreMotif, we use both the conventional and the motif-based spectral
clustering algorithms as the baselines and compare our algorithm with them for
18 groups of real-world datasets. Comparative results demonstrate that the
proposed graph clustering algorithm is accurate yet efficient for large
networks, which also means that it can be further used to evaluate the
intra-cluster and inter-cluster trusts on large networks.
- Abstract(参考訳): クラスタリング分析は、無線センサネットワークやオンラインソーシャルネットワークなど、さまざまな複雑なネットワークの信頼評価に広く使われている。
スペクトルクラスタリングは、グラフ構造化データ(ネットワーク)の最も一般的に使われるアルゴリズムの1つである。
しかし,従来のスペクトルクラスタリングは計算コストの高い行列操作を必要とするため,大規模ネットワークでは本質的に処理が困難である。
本稿では,大規模ネットワークを扱うために,k-core分解とモチーフを活用し,大規模ネットワークを対象とした効率的なグラフクラスタリングアルゴリズムであるkcoremotifを提案する。
提案するクラスタリングアルゴリズムの背後にある基本的な考え方は、グラフ全体ではなく、kコアサブグラフ上で効率的なモチーフベースのスペクトルクラスタリングアルゴリズムを実行することである。
より具体的には、(1)最初に大きな入力ネットワークのkコア分解を行い、(2)上位のkコアサブグラフに対してモチーフベースのスペクトルクラスタリングを行い、(3)残りの頂点を残りの(k-1)コアサブグラフにグループ化し、最後に大きな入力ネットワークの所望のクラスタを得る。
提案したグラフクラスタリングアルゴリズムKCoreMotifの性能を評価するために,従来のスペクトルクラスタリングアルゴリズムとモチーフベースのスペクトルクラスタリングアルゴリズムの両方をベースラインとして使用し,実世界の18個のデータセットに対してアルゴリズムを比較検討した。
比較結果から,提案アルゴリズムは大規模ネットワークにおいて正確かつ効率的であり,大規模ネットワーク上でのクラスタ内信頼とクラスタ間信頼のさらなる評価に有効であることが示された。
関連論文リスト
- A Versatile Framework for Attributed Network Clustering via K-Nearest Neighbor Augmentation [14.327262299413789]
ANCKAは、属性グラフクラスタリング(AGC)、属性多重グラフクラスタリング(AMGC)、属性ハイパーグラフクラスタリング(AHC)が可能な汎用属性ネットワーククラスタリングフレームワークとして開発されている。
我々は,提案手法を8つの属性付きハイパーグラフ上の19の競合,6つの属性付きグラフ上の16の競合,および3つの属性付き多重グラフ上の16の競合と比較した。
論文 参考訳(メタデータ) (2024-08-10T06:59:51Z) - Cluster-based Graph Collaborative Filtering [55.929052969825825]
グラフ畳み込みネットワーク(GCN)は、レコメンデーションシステムのためのユーザおよびアイテム表現の学習に成功している。
既存のGCNベースのほとんどのメソッドは、高階グラフ畳み込みを実行しながら、ユーザの複数の関心事を見落としている。
クラスタベースグラフ協調フィルタリング(ClusterGCF)と呼ばれる新しいGCNベースのレコメンデーションモデルを提案する。
論文 参考訳(メタデータ) (2024-04-16T07:05:16Z) - Deep Contrastive Graph Learning with Clustering-Oriented Guidance [61.103996105756394]
グラフ畳み込みネットワーク(GCN)は、グラフベースのクラスタリングを改善する上で大きな可能性を秘めている。
モデルはGCNを適用するために初期グラフを事前に推定する。
一般的なデータクラスタリングには,Deep Contrastive Graph Learning (DCGL)モデルが提案されている。
論文 参考訳(メタデータ) (2024-02-25T07:03:37Z) - Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。
提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。
フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
論文 参考訳(メタデータ) (2023-08-13T18:12:28Z) - 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) - A Modular Framework for Centrality and Clustering in Complex Networks [0.6423239719448168]
本稿では,集中度とクラスタリングという2つの重要なネットワーク解析手法について検討する。
クラスタリングには情報フローベースのモデルが採用されている。
我々のクラスタリングは、エッジウェイトとノードの度合いの異なる解釈と相互作用と同様に、エッジ指向性に対応する柔軟性を自然に継承する。
論文 参考訳(メタデータ) (2021-11-23T03:01:29Z) - Self-supervised Contrastive Attributed Graph Clustering [110.52694943592974]
我々は,自己教師型コントラストグラフクラスタリング(SCAGC)という,新たな属性グラフクラスタリングネットワークを提案する。
SCAGCでは,不正確なクラスタリングラベルを活用することで,ノード表現学習のための自己教師付きコントラスト損失を設計する。
OOSノードでは、SCAGCはクラスタリングラベルを直接計算できる。
論文 参考訳(メタデータ) (2021-10-15T03:25:28Z) - Hierarchical clustering of bipartite data sets based on the statistical
significance of coincidences [0.0]
本稿では,2つのエンティティが共有する特徴が単なるチャンスに起因する確率を定量化するエンティティ間の相似性に基づく階層的クラスタリングアルゴリズムを提案する。
アルゴリズムのパフォーマンスは n 個のエンティティの集合に適用された場合$O(n2)$であり、その結果はそれらのエンティティの接続を示すデンドログラムである。
論文 参考訳(メタデータ) (2020-04-27T23:30:18Z) - Randomized spectral co-clustering for large-scale directed networks [15.486507430729052]
共同クラスタリングは、有向ネットワークの送信者と受信者を同時にクラスタ化することを目的としている。
スケッチ技術を活用し、2つのランダム化スペクトルコクラスタリングアルゴリズムを導出する。
我々は、それらの近似誤差率と誤クラスタリング誤差率を確立し、共クラスタリング文学の最先端結果よりも優れた境界を示す。
論文 参考訳(メタデータ) (2020-04-25T15:00:55Z) - Motif-Based Spectral Clustering of Weighted Directed Networks [6.1448102196124195]
クラスタリングは、様々な分野の応用において、ネットワーク分析に不可欠な技術である。
一つのアプローチは、モチーフ隣接行列を用いて高次構造を捕捉し、クラスタ化することである。
本稿では,重み付きネットワーク上での隣接行列のモチーフとして,新しい,計算に有用な行列式を提案する。
論文 参考訳(メタデータ) (2020-04-02T22:45:28Z) - Learning to Cluster Faces via Confidence and Connectivity Estimation [136.5291151775236]
重複する部分グラフを多数必要とせず,完全に学習可能なクラスタリングフレームワークを提案する。
提案手法はクラスタリングの精度を大幅に向上させ,その上で訓練した認識モデルの性能を向上させるが,既存の教師付き手法に比べて桁違いに効率的である。
論文 参考訳(メタデータ) (2020-04-01T13:39:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。