論文の概要: Analyzing Modularity Maximization in Approximation, Heuristic, and Graph
Neural Network Algorithms for Community Detection
- arxiv url: http://arxiv.org/abs/2310.10898v2
- Date: Wed, 10 Jan 2024 21:28:46 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-13 03:19:50.032490
- 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, which involves partitioning nodes within a network, has
widespread applications across computational sciences. Modularity-based
algorithms identify communities by attempting to maximize the modularity
function across network node partitions. Our study assesses the performance of
various modularity-based algorithms in obtaining optimal partitions. Our
analysis utilizes 104 networks, including both real-world instances from
diverse contexts and modular graphs from two families of synthetic benchmarks.
We analyze ten inexact modularity-based algorithms against the exact integer
programming baseline that globally optimizes modularity. Our comparative
analysis includes eight heuristics, two variants of a graph neural network
algorithm, and nine variations of the Bayan approximation algorithm.
Our findings reveal that the average modularity-based heuristic yields
optimal partitions in only 43.9% of the 104 networks analyzed. Graph neural
networks and approximate Bayan, on average, achieve optimality on 68.7% and
82.3% of the networks respectively. Additionally, our analysis of three
partition similarity metrics exposes substantial dissimilarities between
high-modularity sub-optimal partitions and any optimal partition of the
networks. We observe 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 modularity-based methods: 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, we recommend approximate optimization algorithms for a
more methodologically sound usage of modularity within its applicability
limits.
- Abstract（参考訳）: ネットワーク内のノードを分割するコミュニティ検出は、計算科学に広く応用されている。
モジュール性に基づくアルゴリズムは,ネットワークノード分割におけるモジュラリティ関数の最大化を試み,コミュニティを識別する。
本研究は,最適分割を求めるために,様々なモジュール性に基づくアルゴリズムの性能を評価する。
この分析は104のネットワークを用いており、多様なコンテキストからの実世界インスタンスと、2種類の合成ベンチマークによるモジュラーグラフの両方を含む。
モジュール性をグローバルに最適化する正確な整数プログラミングベースラインに対して、10の不正確なモジュラリティベースのアルゴリズムを解析する。
比較分析には,8つのヒューリスティック,グラフニューラルネットワークアルゴリズムの2つの変種,ベイアン近似アルゴリズムの9つの変種を含む。
その結果,104ネットワークの43.9%で平均モジュラリティに基づくヒューリスティックな分配が最適であることがわかった。
グラフニューラルネットワークと近似ベイアン平均は、それぞれ68.7%と82.3%の最適性を達成している。
さらに,3つの分割類似度尺度の解析により,高モジュラリティ部分最適分割とネットワークの最適分割との間にかなりの相違が生じる。
ほぼ最適な分割はしばしば、任意の最適分割と不均等に異なる。
モジュール構造を持つネットワーク上でも最適なパーティションや最適なパーティションに似たパーティションを生成することは滅多にありません。
コミュニティの検出にモジュール性を用いる場合は,その適用範囲内でモジュール性をより適切に利用するための近似最適化アルゴリズムを推奨する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。