論文の概要: The Hyperspherical Geometry of Community Detection: Modularity as a Distance

• arxiv url: http://arxiv.org/abs/2107.02645v1
• Date: Tue, 6 Jul 2021 14:32:32 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-07 13:41:17.651678
• Title: The Hyperspherical Geometry of Community Detection: Modularity as a Distance
• Title（参考訳）: コミュニティ検出の超球面形状:距離としてのモジュラリティ
• Authors: Martijn G\"osgens, Remco van der Hofstad, Nelly Litvak
• Abstract要約: Louvainアルゴリズムは、最も人気のあるコミュニティ検出手法の1つである。 モジュラリティの最大化は、クラスタリングベクトルの集合上のモジュラリティベクトルに角距離を最小化することと同値であることを示す。 この同値性により、ルーヴァンアルゴリズムを、このモジュラリティベクトルへの距離をほぼ最小化する最寄りの探索と見なすことができる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Louvain algorithm is currently one of the most popular community detection methods. This algorithm finds communities by maximizing a quantity called modularity. In this work, we describe a metric space of clusterings, where clusterings are described by a binary vector indexed by the vertex-pairs. We extend this geometry to a hypersphere and prove that maximizing modularity is equivalent to minimizing the angular distance to some modularity vector over the set of clustering vectors. This equivalence allows us to view the Louvain algorithm as a nearest-neighbor search that approximately minimizes the distance to this modularity vector. By replacing this modularity vector by a different vector, many alternative community detection methods can be obtained. We explore this wider class and compare it to existing modularity-based methods. Our experiments show that these alternatives may outperform modularity-based methods. For example, when communities are large compared to vertex neighborhoods, a vector based on numbers of common neighbors outperforms existing community detection methods. While the focus of the present work is community detection in networks, the proposed methodology can be applied to any clustering problem where pair-wise similarity data is available.
• Abstract（参考訳）: Louvainアルゴリズムは、現在最も人気のあるコミュニティ検出手法の1つである。 このアルゴリズムはモジュラリティと呼ばれる量を最大化することでコミュニティを見つける。 本稿では,頂点ペアによってインデックスづけされた2進ベクトルによってクラスタリングを記述する,クラスタリングの計量空間について述べる。 この幾何学を超球面に拡張し、モジュラリティの最大化は、クラスタリングベクトルの集合上のあるモジュラリティベクトルへの角距離を最小化することと同値であることを示す。 この等価性により、ルービンアルゴリズムを、このモジュラリティベクトルまでの距離をほぼ最小化する最寄り探索と見なすことができる。 このモジュラリティベクトルを別のベクトルに置き換えることで、多くの代替のコミュニティ検出方法を得ることができる。 このより広いクラスを探索し、既存のモジュラリティベースのメソッドと比較する。 実験により,これらの代替手段はモジュール性に基づく手法より優れていることが示された。 例えば、コミュニティが頂点付近に比べて大きい場合、近隣住民の数に基づくベクトルは、既存のコミュニティ検出方法より優れている。 本研究の焦点はネットワークにおけるコミュニティ検出であるが,提案手法は,ペア間の類似性が利用可能な任意のクラスタリング問題に適用できる。

関連論文リスト

• Faithful Density-Peaks Clustering via Matrix Computations on MPI Parallelization System [7.594123537718585]
  密度ピーククラスタリング(DP)は任意の形状のクラスタを検出し、非ユークリッド空間データをクラスタリングする能力を持つ。 本稿では,2種類のベクトル状距離行列と逆前ノードファイリングポリシを併用した忠実かつ並列なDP法を提案する。 本手法は,コミュニティ検出などの非ユークリッドデータをクラスタリングすると同時に,大規模ユークリッドデータをクラスタリングする場合の精度において,最先端の手法よりも優れる。
  論文  参考訳（メタデータ） (2024-06-18T06:05:45Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar [0.0]
  本稿では,現在のモジュラリティアルゴリズムが最大モジュラリティ分割を返却する成功度について検討する。 既存の8つのアルゴリズムを、モジュラリティを世界規模で最大化する正確な整数計画法と比較する。 以上の結果から, ほぼ最適分割は任意の最適分割と不均等に異なることが示唆された。
  論文  参考訳（メタデータ） (2023-02-28T16:11:08Z)
• Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity [0.8450726582512176]
  最適性と近似保証を提供するアルゴリズムを含む30のコミュニティ検出手法を比較した。 他の29のアルゴリズムのパーティションと比較すると、最大モジュラリティパーティションは、記述の長さ、カバレッジ、パフォーマンス、平均コンダクタンス、クラスタ度に最も適している。 Bayan(bayanpy)のPython実装は、Pythonのパッケージインストーラを通じて公開されている。
  論文  参考訳（メタデータ） (2022-09-10T00:17:09Z)
• On Mitigating Hard Clusters for Face Clustering [48.39472979642971]
  顔クラスタリングは、大規模な未ラベルの顔画像を使用して顔認識システムをスケールアップするための有望な方法である。 我々はNDDe(Neighborhood-Diffusion-based Density)とTPDi(Transition-Probability-based Distance)の2つの新しいモジュールを紹介した。 複数のベンチマーク実験により,各モジュールが最終性能に寄与することが示された。
  論文  参考訳（メタデータ） (2022-07-25T03:55:15Z)
• Interpretable Clustering via Multi-Polytope Machines [12.69310440882225]
  本稿では,クラスタデータポイントと,検出したクラスタの周辺にポリトープを構築して説明する,解釈可能なクラスタリングのための新しい手法を提案する。 我々は,我々の手法を,人工クラスタリングと実世界のクラスタリングの一連の問題にベンチマークし,我々のアルゴリズムは,アート解釈可能で非解釈可能なクラスタリングアルゴリズムの状態を上回ります。
  論文  参考訳（メタデータ） (2021-12-10T16:36:32Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• Finding Geometric Models by Clustering in the Consensus Space [61.65661010039768]
  本稿では,未知数の幾何学的モデル,例えばホモグラフィーを求めるアルゴリズムを提案する。 複数の幾何モデルを用いることで精度が向上するアプリケーションをいくつか提示する。 これには、複数の一般化されたホモグラフからのポーズ推定、高速移動物体の軌道推定が含まれる。
  論文  参考訳（メタデータ） (2021-03-25T14:35:07Z)
• (k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time Warping [57.316437798033974]
  本研究では,トラジェクトリの集中型クラスタリングの問題について考察する。 我々はDTWの連続バージョンを距離測定として使用することを提案し、これをCDTW(Continuous dynamic time warping)と呼ぶ。 一連の軌道から中心を計算し、その後反復的に改善する実践的な方法を示す。
  論文  参考訳（メタデータ） (2020-12-01T13:17:27Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。 我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
  論文  参考訳（メタデータ） (2020-10-22T15:58:35Z)
• Hierarchical clustering of bipartite data sets based on the statistical significance of coincidences [0.0]
  本稿では,2つのエンティティが共有する特徴が単なるチャンスに起因する確率を定量化するエンティティ間の相似性に基づく階層的クラスタリングアルゴリズムを提案する。 アルゴリズムのパフォーマンスは n 個のエンティティの集合に適用された場合$O(n2)$であり、その結果はそれらのエンティティの接続を示すデンドログラムである。
  論文  参考訳（メタデータ） (2020-04-27T23:30:18Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。