論文の概要: Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar

• arxiv url: http://arxiv.org/abs/2302.14698v3
• Date: Sun, 25 Jun 2023 14:36:55 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-27 23:30:05.680467
• Title: Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar
• Title（参考訳）: コミュニティ検出のためのヒューリスティックモジュラリティ最大化アルゴリズムは、最適パーティションなどを返すことは滅多にない
• Authors: Samin Aref, Mahdi Mostajabdaveh, and Hriday Chheda
• Abstract要約: 本稿では,現在のモジュラリティアルゴリズムが最大モジュラリティ分割を返却する成功度について検討する。 既存の8つのアルゴリズムを、モジュラリティを世界規模で最大化する正確な整数計画法と比較する。 以上の結果から, ほぼ最適分割は任意の最適分割と不均等に異なることが示唆された。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Community detection is a fundamental problem in computational sciences with extensive applications in various fields. The most commonly used methods are the algorithms designed to maximize modularity over different partitions of the network nodes. Using 80 real and random networks from a wide range of contexts, we investigate the extent to which current heuristic modularity maximization algorithms succeed in returning maximum-modularity (optimal) partitions. We evaluate (1) the ratio of the algorithms' output modularity to the maximum modularity for each input graph, and (2) the maximum similarity between their output partition and any optimal partition of that graph. We compare eight existing heuristic algorithms against an exact integer programming method that globally maximizes modularity. The average modularity-based heuristic algorithm returns optimal partitions for only 19.4% of the 80 graphs considered. Additionally, results on adjusted mutual information reveal substantial dissimilarity between the sub-optimal partitions and any optimal partition of the networks in our experiments. More 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 commonly used modularity-based heuristics for discovering communities: they rarely produce an optimal partition or a partition resembling an optimal partition. If modularity is to be used for detecting communities, exact or approximate optimization algorithms are recommendable for a more methodologically sound usage of modularity within its applicability limits.
• Abstract（参考訳）: コミュニティ検出は計算科学の基本的な問題であり、様々な分野に広く応用されている。 最もよく使われる方法は、ネットワークノードの異なるパーティションに対するモジュラリティを最大化するアルゴリズムである。 幅広い文脈から80個の実ネットワークとランダムネットワークを用いて、現在のヒューリスティックモジュラリティ最大化アルゴリズムが最大モジュラリティ(最適)パーティションの返却に成功する範囲について検討する。 我々は,(1) アルゴリズムの出力モジュラリティと各入力グラフの最大モジュラリティとの比を評価し,(2) 出力分割とそのグラフの任意の最適分割との最大類似度を評価する。 モジュラリティをグローバルに最大化する8つの既存のヒューリスティックアルゴリズムと厳密な整数計画法を比較した。 平均モジュラリティに基づくヒューリスティックアルゴリズムは、考慮された80グラフのうち19.4%の最適分割を返す。 さらに,調整された相互情報に関する結果から,実験におけるサブ最適分割とネットワークの最適分割との間に有意な相似性が認められた。 さらに重要なことは、我々の結果は、ほぼ最適な分割は、しばしば最適な分割と不均等に異なることである。 共同で分析した結果,コミュニティの発見に広く用いられているモジュール性に基づくヒューリスティックが,最適パーティションや最適パーティションに類似したパーティションを生成することは稀であることがわかった。 モジュラリティがコミュニティの検出に使用される場合、その適用可能性の限界内でモジュール性をより適切に利用するために、正確にあるいは近似的な最適化アルゴリズムが推奨される。

関連論文リスト

• Analyzing Modularity Maximization in Approximation, Heuristic, and Graph Neural Network Algorithms for Community Detection [1.1220356822493742]
  本研究は,最適分割を求めるために,様々なモジュール性に基づくアルゴリズムの性能を評価する。 概最適分割は、しばしば任意の最適分割と不均等に異なる。 モジュラリティがコミュニティの検出に使用される場合、より方法論的なモジュラリティ利用のための近似最適化アルゴリズムを推奨する。
  論文  参考訳（メタデータ） (2023-10-17T00:12:18Z)
• Practical Parallel Algorithms for Non-Monotone Submodular Maximization [20.13836086815112]
  Submodularは、人工知能の分野における様々な分野に広く応用されている。 部分モジュラーアルゴリズムの並列化可能性の1つは適応的な複雑性であり、これは対象関数に対する多数のクエリを並列に実行できるラウンドの数を示している。 証明可能な近似比と非単調なサブモジュラー問題に対するサブ適応複雑性をともに持つ最初のアルゴリズムを$k$-systemに提案する。
  論文  参考訳（メタデータ） (2023-08-21T11:48:34Z)
• Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
  実データと人工雑音のロジスティックな損失として目的を定式化することにより, ノイズコントラスト推定(NCE)を提案する。 本稿では,非正規化モデルの負の対数類似度を最適化するための直接的アプローチについて検討する。
  論文  参考訳（メタデータ） (2023-06-13T01:18:16Z)
• Online and Streaming Algorithms for Constrained $k$-Submodular Maximization [25.15934533974176]
  制約付き$k$-submodularは、広告アロケーション、インフルエンス、パーソナライズされたレコメンデーションなど、多くの個別の最適化問題をキャプチャする一般的なフレームワークである。 本研究では,モノトーンと一般(おそらく非モノトーン)の両方の目的に制約された$k$サブモジュールのシングルパスストリーミングとオンラインアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2023-05-25T12:53:17Z)
• 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)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Partition-based formulations for mixed-integer optimization of trained ReLU neural networks [66.88252321870085]
  本稿では,訓練されたReLUニューラルネットワークのための混合整数式について紹介する。 1つの極端な場合、入力毎に1つのパーティションがノードの凸殻、すなわち各ノードの最も厳密な可能な定式化を回復する。
  論文  参考訳（メタデータ） (2021-02-08T17:27:34Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。 一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
  論文  参考訳（メタデータ） (2020-12-04T15:36:29Z)
• Batch greedy maximization of non-submodular functions: Guarantees and applications to experimental design [0.0]
  非部分モジュラーな非退化集合関数の濃度制約に対するグリーディを解析する。 我々の理論的保証は、部分モジュラリティと超モジュラリティ比の組み合わせによって特徴づけられる。
  論文  参考訳（メタデータ） (2020-06-03T18:58:06Z)

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

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