論文の概要: Hierarchical clustering of bipartite data sets based on the statistical
significance of coincidences
- arxiv url: http://arxiv.org/abs/2004.14764v2
- Date: Fri, 24 Jul 2020 09:04:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-09 06:18:05.133474
- Title: Hierarchical clustering of bipartite data sets based on the statistical
significance of coincidences
- Title(参考訳): 偶然の統計的意義に基づく2成分データセットの階層的クラスタリング
- Authors: Ignacio Tamarit, Mar\'ia Pereda, and Jos\'e A. Cuesta
- Abstract要約: 本稿では,2つのエンティティが共有する特徴が単なるチャンスに起因する確率を定量化するエンティティ間の相似性に基づく階層的クラスタリングアルゴリズムを提案する。
アルゴリズムのパフォーマンスは n 個のエンティティの集合に適用された場合$O(n2)$であり、その結果はそれらのエンティティの接続を示すデンドログラムである。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: When some 'entities' are related by the 'features' they share they are
amenable to a bipartite network representation. Plant-pollinator ecological
communities, co-authorship of scientific papers, customers and purchases, or
answers in a poll, are but a few examples. Analyzing clustering of such
entities in the network is a useful tool with applications in many fields, like
internet technology, recommender systems, or detection of diseases. The
algorithms most widely applied to find clusters in bipartite networks are
variants of modularity optimization. Here we provide an hierarchical clustering
algorithm based on a dissimilarity between entities that quantifies the
probability that the features shared by two entities is due to mere chance. The
algorithm performance is $O(n^2)$ when applied to a set of n entities, and its
outcome is a dendrogram exhibiting the connections of those entities. Through
the introduction of a 'susceptibility' measure we can provide an 'optimal'
choice for the clustering as well as quantify its quality. The dendrogram
reveals further useful structural information though -- like the existence of
sub-clusters within clusters or of nodes that do not fit in any cluster. We
illustrate the algorithm by applying it first to a set of synthetic networks,
and then to a selection of examples. We also illustrate how to transform our
algorithm into a valid alternative for one-mode networks as well, and show that
it performs at least as well as the standard, modularity-based algorithms --
with a higher numerical performance. We provide an implementation of the
algorithm in Python freely accessible from GitHub.
- Abstract(参考訳): ある「エンティティ」が「機能」によって関連付けられている場合、それらは二部ネットワーク表現に順応できる。
植物汚染者コミュニティ、科学論文の共著者、顧客と購入、あるいは世論調査の回答などは、ごく一部の例である。
ネットワーク内のそのようなエンティティのクラスタリングを分析することは、インターネット技術、レコメンダシステム、病気の検出など、多くの分野のアプリケーションで有用なツールである。
二部ネットワークのクラスタを見つけるために最も広く用いられるアルゴリズムはモジュラリティ最適化の変種である。
ここでは、2つのエンティティが共有する特徴が単なるチャンスに起因する確率を定量化するエンティティ間の相似性に基づく階層的クラスタリングアルゴリズムを提案する。
アルゴリズムのパフォーマンスは n 個の実体の集合に適用すると$O(n^2)$ となり、その結果はそれらの実体の接続を示すデンドログラムとなる。
サセプティビリティ(susceptibility)"尺度を導入することで、クラスタリングの'最適'の選択と、その品質の定量化が可能になります。
dendrogramは、クラスタ内のサブクラスタの存在や、任意のクラスタに適合しないノードの存在など、さらに有用な構造情報を示している。
まず、合成ネットワークのセットに適用し、次にサンプルを選択することで、アルゴリズムを説明します。
また、我々のアルゴリズムを1モードネットワークの有効な代替品にする方法も説明し、より高い数値性能で、少なくとも標準のモジュラリティベースのアルゴリズムと同様に性能を発揮することを示す。
githubから自由にアクセス可能なpythonのアルゴリズムの実装を提供する。
関連論文リスト
- FLASC: A Flare-Sensitive Clustering Algorithm [0.0]
本稿では,クラスタ内の分岐を検知してサブポピュレーションを同定するアルゴリズムFLASCを提案する。
アルゴリズムの2つの変種が提示され、ノイズの堅牢性に対する計算コストが取引される。
両変種は計算コストの観点からHDBSCAN*と類似してスケールし,安定した出力を提供することを示す。
論文 参考訳(メタデータ) (2023-11-27T14:55:16Z) - Exact Recovery and Bregman Hard Clustering of Node-Attributed Stochastic
Block Model [0.16385815610837165]
本稿では,コミュニティラベルの正確な回復のための情報理論的基準を提案する。
ネットワークと属性情報をどのように交換して正確なリカバリを行うかを示す。
また、共同確率を最大化する反復的クラスタリングアルゴリズムも提示する。
論文 参考訳(メタデータ) (2023-10-30T16:46:05Z) - Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。
提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。
フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
論文 参考訳(メタデータ) (2023-08-13T18:12:28Z) - Dink-Net: Neural Clustering on Large Graphs [59.10189693120368]
ディープグラフクラスタリング法 (Dink-Net) は, 拡張と縮小という概念を用いて提案される。
ノードを識別することにより、拡張によって劣化しても、表現は自己教師された方法で学習される。
クラスタリング分布は、提案したクラスタ拡張損失とクラスタ縮小損失を最小化することにより最適化される。
ランナアップと比較して、Dink-Net 9.62%は1100万ノードと16億エッジを持つogbn-papers100MデータセットでNMIの改善を実現している。
論文 参考訳(メタデータ) (2023-05-28T15:33:24Z) - Community detection in complex networks via node similarity, graph
representation learning, and hierarchical clustering [4.264842058017711]
コミュニティ検出は、実際のグラフを分析する上で重要な課題である。
この記事では,この課題に対処する3つの新しい階層型フレームワークを提案する。
ブロックモデルグラフと実生活データセットにおける100以上のモジュールの組み合わせを比較します。
論文 参考訳(メタデータ) (2023-03-21T22:12:53Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳(メタデータ) (2022-02-09T06:05:05Z) - Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
クラスタリングのA*探索に基づく新しいアプローチを紹介します。
A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。
実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
論文 参考訳(メタデータ) (2021-04-14T18:15:27Z) - 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) - Towards Deeper Graph Neural Networks with Differentiable Group
Normalization [61.20639338417576]
グラフニューラルネットワーク(GNN)は、隣接するノードを集約することでノードの表現を学習する。
オーバースムーシングは、レイヤーの数が増えるにつれてGNNのパフォーマンスが制限される重要な問題のひとつです。
2つのオーバースムースなメトリクスと新しいテクニック、すなわち微分可能群正規化(DGN)を導入する。
論文 参考訳(メタデータ) (2020-06-12T07:18:02Z) - Graph Neural Networks with Composite Kernels [60.81504431653264]
カーネル重み付けの観点からノード集約を再解釈する。
本稿では,アグリゲーション方式における特徴類似性を考慮したフレームワークを提案する。
特徴空間における特徴類似性をエンコードするために,元の隣り合うカーネルと学習可能なカーネルの合成として特徴集約を提案する。
論文 参考訳(メタデータ) (2020-05-16T04:44:29Z) - Data Structures & Algorithms for Exact Inference in Hierarchical
Clustering [41.24805506595378]
本稿では,新しいトレリスデータ構造に基づく階層クラスタリングにおける表現型推論のための動的プログラミングアルゴリズムを提案する。
我々のアルゴリズムは時間と空間に比例してN$要素のパワーセットをスケールし、これは(2N-3)! 可能な階層のそれぞれを明示的に考慮するよりも指数関数的に効率的である。
論文 参考訳(メタデータ) (2020-02-26T17:43:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。