論文の概要: Analyzing Modularity Maximization in Approximation, Heuristic, and Graph
Neural Network Algorithms for Community Detection
- arxiv url: http://arxiv.org/abs/2310.10898v1
- Date: Tue, 17 Oct 2023 00:12:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-18 18:23:58.589620
- Title: Analyzing Modularity Maximization in Approximation, Heuristic, and Graph
Neural Network Algorithms for Community Detection
- Title（参考訳）: コミュニティ検出のための近似・ヒューリスティック・グラフニューラルネットワークアルゴリズムにおけるモジュラリティ最大化の解析
- Authors: Samin Aref and Mahdi Mostajabdaveh
- Abstract要約: ヒューリスティックスは、ネットワークノードのパーティション上の目的関数、モジュラリティを最大化することで、コミュニティを検出するためにしばしば使用される。
我々の研究は、最適な分割を達成するために、異なるモジュラリティアルゴリズムの性能について検討している。
- 参考スコア（独自算出の注目度）: 1.1220356822493742
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Community detection, a fundamental problem in computational sciences, finds
applications in various domains. Heuristics are often employed to detect
communities through maximizing an objective function, modularity, over
partitions of network nodes. Our research delves into the performance of
different modularity maximization algorithms in achieving optimal partitions.
We use 104 networks, comprising real-world instances from diverse contexts and
synthetic graphs with modular structures. We analyze ten inexact
modularity-based algorithms against an exact baseline which is an exact integer
programming method that globally optimizes modularity. The ten algorithms
analyzed include eight heuristics, two variations of a graph neural network
algorithm, and several variations of the Bayan approximation algorithm. Our
analysis uncovers substantial dissimilarities between the partitions obtained
by most commonly used modularity-based methods and any optimal partition of the
networks, as indicated by both adjusted and reduced mutual information metrics.
Importantly, our results show that near-optimal partitions are often
disproportionately dissimilar to any optimal partition. Taken together, our
analysis points to a crucial limitation of the commonly used unguaranteed
modularity-based methods for discovering communities: they rarely produce an
optimal partition or a partition resembling an optimal partition even on
networks with modular structures. If modularity is to be used for detecting
communities, approximate optimization algorithms are recommendable for a more
methodologically sound usage of modularity within its applicability limits.
- Abstract（参考訳）: 計算科学における基本的な問題であるコミュニティ検出は、様々な分野の応用を見出す。
ヒューリスティックスは、ネットワークノードのパーティション上の目的関数、モジュラリティを最大化することで、コミュニティを検出するためにしばしば使用される。
本研究では,最適分割を達成する際のモジュラリティ最大化アルゴリズムの性能について考察する。
我々は104のネットワークを使用し、多様なコンテキストから実世界のインスタンスとモジュール構造を持つ合成グラフで構成されている。
我々は,モジュラリティをグローバルに最適化する厳密な整数計画法である厳密なベースラインに対して,モジュラリティに基づくアルゴリズムを10種類分析する。
解析された10のアルゴリズムには、8つのヒューリスティック、グラフニューラルネットワークアルゴリズムの2つのバリエーション、ベイアン近似アルゴリズムのいくつかのバリエーションが含まれる。
本研究は,モジュール性に基づく手法で得られる分割と,調整された相互情報メトリクスと縮小された相互情報メトリクスの両方で示されるネットワークの最適分割との間に,大きな相違点を明らかにする。
以上の結果から,至近距離分割はしばしば最適分割と不釣り合いに異なっていた。
まとめると、我々はコミュニティを発見するためによく使われるモジュール性に基づくモジュール性に基づく方法の限界を指摘している:それらはモジュラ構造を持つネットワーク上でも最適なパーティションや最適なパーティションに似たパーティションをほとんど生成しない。
モジュラリティがコミュニティの検出に使用される場合、近似最適化アルゴリズムは適用範囲内でのモジュラリティのより方法論的な使用を推奨する。
関連論文リスト
- Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
グラフマッチングはコンピュータビジョンやパターン認識において一般的に用いられる技法である。
最近のデータ駆動型アプローチは、グラフマッチングの精度を著しく改善した。
データ駆動手法と従来の手法の利点を組み合わせたグラフニューラルネットワーク(GNN)に基づくアプローチを提案する。
論文 参考訳（メタデータ） (2024-03-11T06:34:05Z) - Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
実データと人工雑音のロジスティックな損失として目的を定式化することにより, ノイズコントラスト推定(NCE)を提案する。
本稿では,非正規化モデルの負の対数類似度を最適化するための直接的アプローチについて検討する。
論文 参考訳（メタデータ） (2023-06-13T01:18:16Z) - 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) - Late Fusion Multi-view Clustering via Global and Local Alignment
Maximization [61.89218392703043]
マルチビュークラスタリング(MVC)は、異なるビューからの補完情報を最適に統合し、クラスタリング性能を改善する。
既存のアプローチの多くは、クラスタリングに最適な類似性行列を学ぶために、複数の事前定義された類似性を直接融合する。
これらの問題に対処するために、アライメントを通してレイトフュージョンMVCを提案する。
論文 参考訳（メタデータ） (2022-08-02T01:49:31Z) - Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。
厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。
このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
論文 参考訳（メタデータ） (2021-11-29T15:10:09Z) - Partition-based formulations for mixed-integer optimization of trained
ReLU neural networks [66.88252321870085]
本稿では,訓練されたReLUニューラルネットワークのための混合整数式について紹介する。
1つの極端な場合、入力毎に1つのパーティションがノードの凸殻、すなわち各ノードの最も厳密な可能な定式化を回復する。
論文 参考訳（メタデータ） (2021-02-08T17:27:34Z) - Partition of unity networks: deep hp-approximation [0.0]
本稿では,これらの要素を直接アーキテクチャに組み込む統一ネットワーク(POUnets)の分割を提案する。
POUnets は滑らかな関数に対して hp-収束をもたらし、多くの不連続性を持つピースワイズ関数を一貫して上回る。
論文 参考訳（メタデータ） (2021-01-27T08:26:11Z) - Efficient semidefinite-programming-based inference for binary and
multi-class MRFs [83.09715052229782]
分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。
一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
論文 参考訳（メタデータ） (2020-12-04T15:36:29Z) - Distributed Optimization, Averaging via ADMM, and Network Topology [0.0]
センサローカライゼーションの現実問題において,ネットワークトポロジと異なるアルゴリズムの収束率の関係について検討する。
また、ADMMと持ち上げマルコフ連鎖の間の興味深い関係を示すとともに、その収束を明示的に特徴づける。
論文 参考訳（メタデータ） (2020-09-05T21:44:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。