論文の概要: Heuristic Modularity Maximization Algorithms for Community Detection
Rarely Return an Optimal Partition or Anything Similar
- arxiv url: http://arxiv.org/abs/2302.14698v1
- Date: Tue, 28 Feb 2023 16:11:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-01 15:40:09.549522
- 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要約: 本稿では,現在のモジュラリティアルゴリズムがモジュラリティ最大(最適)パーティションの返却にどの程度成功したかを検討する。
平均モジュラリティに基づくアルゴリズムは、考慮された80グラフのうち16.9%の最適分割を返す。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Community detection is a classic problem in network science 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 into communities. 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 modularity-maximum
(optimal) partitions. We evaluate (1) the ratio of their 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. Our
computational experiments involve eight existing heuristic algorithms which we
compare against an exact integer programming method that globally maximizes
modularity. The average modularity-based heuristic algorithm returns optimal
partitions for only 16.9% of the 80 graphs considered. Results on adjusted
mutual information show considerable dissimilarity between the sub-optimal
partitions and any optimal partitions of the graphs in our experiments. More
importantly, our results show that near-optimal partitions tend to be
disproportionally dissimilar to any optimal partition. Taken together, our
analysis points to a crucial limitation of commonly used modularity-based
algorithms for discovering communities: they rarely return an optimal partition
or a partition resembling an optimal partition. Given this finding, developing
an exact or approximate algorithm for modularity maximization is recommendable
for a more methodologically sound usage of modularity in community detection.
- Abstract(参考訳): コミュニティ検出はネットワーク科学における古典的な問題であり、様々な分野に幅広く応用されている。
最もよく使われる方法は、ネットワークノードの異なるパーティションからコミュニティへのモジュラリティを最大化するアルゴリズムである。
幅広い文脈から80個の実ネットワークとランダムネットワークを用いて、現在のヒューリスティックモジュラリティ最大化アルゴリズムがモジュラリティ最大(最適)パーティションの返却に成功する範囲について検討する。
1) 出力のモジュラリティと各入力グラフの最大モジュラリティとの比、(2) 出力のパーティションとそのグラフの任意の最適パーティションとの最大類似度を評価する。
我々の計算実験では、モジュラリティをグローバルに最大化する完全整数計画法と比較する8つの既存のヒューリスティックアルゴリズムを含む。
平均モジュラリティに基づくヒューリスティックアルゴリズムは、考慮された80グラフのうち16.9%の最適分割を返す。
調整された相互情報の結果は、実験において、準最適分割とグラフの最適分割との間にかなりの相似性を示す。
さらに, この結果から, ほぼ最適分割は任意の最適分割と不均等に異なる傾向を示した。
まとめると、我々の分析は、コミュニティを発見するためによく使われるモジュラリティベースのアルゴリズムが決定的に制限されていることを指摘している。
この発見を踏まえ、モジュール性最大化のための正確なあるいは近似アルゴリズムの開発は、コミュニティ検出におけるモジュール性をより方法論的に活用するために推奨される。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。