論文の概要: When Does Bottom-up Beat Top-down in Hierarchical Community Detection?
- arxiv url: http://arxiv.org/abs/2306.00833v2
- Date: Wed, 24 Jul 2024 13:13:20 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-25 19:59:51.029809
- Title: When Does Bottom-up Beat Top-down in Hierarchical Community Detection?
- Title（参考訳）: 階層型コミュニティ検出においてボトムアップはいつトップダウンになるのか?
- Authors: Maximilien Dreveton, Daichi Kuroda, Matthias Grossglauser, Patrick Thiran,
- Abstract要約: 階層的なネットワークのクラスタリングは、階層の低いレベルがよりきめ細かいコミュニティ構造を明らかにするように、コミュニティのツリーを見つけることで構成される。
Agglomerative ($textitbottom-up$)アルゴリズムは、まず最小のコミュニティ構造を特定し、その後、$textitlinkage$メソッドを使ってコミュニティを何度もマージする。
ボトムアップアルゴリズムにより階層木と階層ブロックモデルのコミュニティ構造を復元するための理論的保証を確立する。
- 参考スコア（独自算出の注目度）: 8.097200145973389
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Hierarchical clustering of networks consists in finding a tree of communities, such that lower levels of the hierarchy reveal finer-grained community structures. There are two main classes of algorithms tackling this problem. Divisive ($\textit{top-down}$) algorithms recursively partition the nodes into two communities, until a stopping rule indicates that no further split is needed. In contrast, agglomerative ($\textit{bottom-up}$) algorithms first identify the smallest community structure and then repeatedly merge the communities using a $\textit{linkage}$ method. In this article, we establish theoretical guarantees for the recovery of the hierarchical tree and community structure of a Hierarchical Stochastic Block Model by a bottom-up algorithm. We also establish that this bottom-up algorithm attains the information-theoretic threshold for exact recovery at intermediate levels of the hierarchy. Notably, these recovery conditions are less restrictive compared to those existing for top-down algorithms. This shows that bottom-up algorithms extend the feasible region for achieving exact recovery at intermediate levels. Numerical experiments on both synthetic and real data sets confirm the superiority of bottom-up algorithms over top-down algorithms. We also observe that top-down algorithms can produce dendrograms with inversions. These findings contribute to a better understanding of hierarchical clustering techniques and their applications in network analysis.
- Abstract（参考訳）: 階層的なネットワークのクラスタリングは、階層の低いレベルがよりきめ細かいコミュニティ構造を明らかにするように、コミュニティのツリーを見つけることで構成される。
この問題に対処するアルゴリズムには2つの主要なクラスがある。
Divisive ($\textit{top-down}$)アルゴリズムはノードを2つのコミュニティに再帰的に分割する。
これとは対照的に、agglomerative$\textit{bottom-up}$)アルゴリズムは、まず最小のコミュニティ構造を特定し、次に$\textit{linkage}$メソッドを使ってコミュニティを何度もマージする。
本稿では,階層的確率ブロックモデルの階層木回復とコミュニティ構造をボトムアップアルゴリズムにより理論的に保証する。
また、このボトムアップアルゴリズムは、階層の中間レベルにおいて正確な回復のための情報理論しきい値を得る。
特に、これらのリカバリ条件は、トップダウンアルゴリズムで存在するものに比べて制限が小さい。
これはボトムアップアルゴリズムが中間レベルで正確な回復を達成するために実現可能な領域を拡張していることを示している。
合成データセットと実データセットの数値実験により、トップダウンアルゴリズムよりもボトムアップアルゴリズムの方が優れていることが確認された。
また、トップダウンアルゴリズムがインバージョン付きデンドログラムを生成可能であることも観察した。
これらの知見は階層的クラスタリング技術とそのネットワーク解析への応用の理解に寄与する。
関連論文リスト
- Hierarchical Clustering via Local Search [0.0]
階層クラスタリングのための局所探索アルゴリズムを提案する。
任意の局所最適木は少なくとも$fracn-23sum_i jw(i,j)$の収益を保証し、そこでは$n$はオブジェクトの数で、$w: [n] times [n] mathbbR+$は関連する類似関数である。
論文 参考訳（メタデータ） (2024-05-24T23:46:24Z) - Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
本稿では,階層構造の回復に着目した凝集クラスタリングアルゴリズムの新しい視点を提案する。
クラスタを最大平均点積でマージし、例えば最小距離やクラスタ内分散でマージしないような、標準的なアルゴリズムの単純な変種を推奨する。
このアルゴリズムにより得られた木は、汎用確率的グラフィカルモデルの下で、データ中の生成的階層構造をボナフェイド推定することを示した。
論文 参考訳（メタデータ） (2023-05-24T11:05:12Z) - Natural Hierarchical Cluster Analysis by Nearest Neighbors with
Near-Linear Time Complexity [0.0]
そこで本研究では,クラスタの自然な階層化を実現する,近接クラスタリングアルゴリズムを提案する。
集約的および分割的階層的クラスタリングアルゴリズムとは対照的に,我々のアプローチはアルゴリズムの反復的な動作に依存しない。
論文 参考訳（メタデータ） (2022-03-15T16:03:42Z) - Frequent Itemset-driven Search for Finding Minimum Node Separators in
Complex Networks [61.2383572324176]
本稿では,データマイニングにおける頻繁なアイテムセットマイニングの概念をよく知られたメメティック検索フレームワークに統合する,頻繁なアイテムセット駆動探索手法を提案する。
頻繁なアイテムセット組換え演算子を反復的に使用して、高品質なソリューションで頻繁に発生するアイテムセットに基づいた有望な子孫ソリューションを生成する。
特に、29個の新しい上界を発見し、以前の18個の最もよく知られた境界と一致する。
論文 参考訳（メタデータ） (2022-01-18T11:16:40Z) - Hierarchical clustering by aggregating representatives in
sub-minimum-spanning-trees [5.877624540482919]
本稿では,クラスタリングデンドログラムを構築しながら,代表点を効果的に検出できる階層的クラスタリングアルゴリズムを提案する。
解析の結果,提案アルゴリズムはO(nlogn)時間複雑度とO(nlogn)空間複雑度を有し,大規模データ処理のスケーラビリティを示す。
論文 参考訳（メタデータ） (2021-11-11T07:36:55Z) - Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
クラスタリングのA*探索に基づく新しいアプローチを紹介します。
A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。
実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
論文 参考訳（メタデータ） (2021-04-14T18:15:27Z) - Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。
我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
論文 参考訳（メタデータ） (2020-10-22T15:58:35Z) - On the use of local structural properties for improving the efficiency
of hierarchical community detection methods [77.34726150561087]
本研究では,階層型コミュニティ検出の効率向上のために,局所構造ネットワーク特性をプロキシとして利用する方法について検討する。
また,ネットワークプルーニングの性能への影響を,階層的コミュニティ検出をより効率的にするための補助的手法として検証する。
論文 参考訳（メタデータ） (2020-09-15T00:16:12Z) - Data Structures & Algorithms for Exact Inference in Hierarchical
Clustering [41.24805506595378]
本稿では,新しいトレリスデータ構造に基づく階層クラスタリングにおける表現型推論のための動的プログラミングアルゴリズムを提案する。
我々のアルゴリズムは時間と空間に比例してN$要素のパワーセットをスケールし、これは(2N-3)! 可能な階層のそれぞれを明示的に考慮するよりも指数関数的に効率的である。
論文 参考訳（メタデータ） (2020-02-26T17:43:53Z) - Scalable Hierarchical Clustering with Tree Grafting [66.68869706310208]
Grinchは、大規模で非階層的な階層的クラスタリングと一般的なリンク関数のための新しいアルゴリズムである。
Grinchは、リンケージ関数を持つクラスタリングのための分離性という新しい概念によって動機付けられている。
論文 参考訳（メタデータ） (2019-12-31T20:56:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。