論文の概要: Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
- arxiv url: http://arxiv.org/abs/2209.04562v5
- Date: Thu, 24 Oct 2024 21:45:34 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-28 13:33:07.928113
- Title: Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
- Title（参考訳）: Bayanアルゴリズム: モジュール性の厳密かつ近似最適化によるネットワーク内のコミュニティの検出
- Authors: Samin Aref, Mahdi Mostajabdaveh, Hriday Chheda,
- Abstract要約: 最適性と近似保証を提供するアルゴリズムを含む30のコミュニティ検出手法を比較した。
他の29のアルゴリズムのパーティションと比較すると、最大モジュラリティパーティションは、記述の長さ、カバレッジ、パフォーマンス、平均コンダクタンス、クラスタ度に最も適している。
Bayan(bayanpy)のPython実装は、Pythonのパッケージインストーラを通じて公開されている。
- 参考スコア（独自算出の注目度）: 0.8450726582512176
- License:
- Abstract: Community detection is a classic network problem with extensive applications in various fields. Its most common method is using modularity maximization heuristics which rarely return an optimal partition or anything similar. Partitions with globally optimal modularity are difficult to compute, and therefore have been underexplored. Using structurally diverse networks, we compare 30 community detection methods including our proposed algorithm that offers optimality and approximation guarantees: the Bayan algorithm. Unlike existing methods, Bayan globally maximizes modularity or approximates it within a factor. Our results show the distinctive accuracy and stability of maximum-modularity partitions in retrieving planted partitions at rates higher than most alternatives for a wide range of parameter settings in two standard benchmarks. Compared to the partitions from 29 other algorithms, maximum-modularity partitions have the best medians for description length, coverage, performance, average conductance, and well clusteredness. These advantages come at the cost of additional computations which Bayan makes possible for small networks (networks that have up to 3000 edges in their largest connected component). Bayan is several times faster than using open-source and commercial solvers for modularity maximization, making it capable of finding optimal partitions for instances that cannot be optimized by any other existing method. Our results point to a few well performing algorithms, among which Bayan stands out as the most reliable method for small networks. A Python implementation of the Bayan algorithm (bayanpy) is publicly available through the package installer for Python.
- Abstract（参考訳）: コミュニティ検出は、様々な分野で広範囲に応用された古典的なネットワーク問題である。
その最も一般的な方法はモジュラリティ最大化ヒューリスティック(英語版)を使い、最適分割や同様のものを返すことは滅多にない。
グローバルな最適モジュラリティを持つ分割は計算が困難であり、従って探索が過小評価されている。
構造的に多様性のあるネットワークを用いて,最適化と近似を保証するアルゴリズムを含む30のコミュニティ検出手法を比較した。
既存の方法とは異なり、ベイアンはモジュラリティを世界規模で最大化するか、あるいはその因子内で近似する。
その結果,2つの標準ベンチマークにおいて,最大モジュラリティパーティションの精度と安定性は,多くの代替品よりも高い値を示した。
他の29のアルゴリズムのパーティションと比較すると、最大モジュラリティパーティションは、記述の長さ、カバレッジ、パフォーマンス、平均コンダクタンス、クラスタ度に最も適している。
これらのアドバンテージは、Bayan氏が小さなネットワーク(最大の接続コンポーネントで3000のエッジを持つネットワーク)で実現した計算の追加コストによるものである。
Bayanは、モジュラリティの最大化のためにオープンソースや商用のソルバを使用するよりも数倍高速で、既存の方法では最適化できないインスタンスの最適なパーティションを見つけることができる。
この結果から,小ネットワークにおいてベイアンが最も信頼性の高い手法として注目されているアルゴリズムがいくつか示された。
Bayanアルゴリズム(bayanpy)のPython実装は、Pythonのパッケージインストーラを通じて公開されている。
関連論文リスト
- Scaling LLM Inference with Optimized Sample Compute Allocation [56.524278187351925]
我々は、異なる推論構成の最適な混合を見つけるアルゴリズムであるOSCAを提案する。
実験の結果,学習した混合アロケーションでは,最高の単一構成よりも精度がよいことがわかった。
OSCAはシングルターンタスク以外のエージェント処理にも有効であることが示されており、デフォルト設定よりも3倍少ない計算でSWE-Benchの精度が向上している。
論文 参考訳（メタデータ） (2024-10-29T19:17:55Z) - Multimodal Optimization with k-Cluster Big Bang-Big Crunch Algorithm and Postprocessing Methods for Identification and Quantification of Optima [0.7639610349097473]
マルチモーダル最適化は工学的な問題、特に異なる代替解を求める場合にしばしば発生する。
本稿では,あまり知られていないビッグバン・ビッグ・Crunch(BBBC)アルゴリズムがマルチモーダル最適化に適しているかを検討する。
論文 参考訳（メタデータ） (2023-12-21T06:16:32Z) - Analyzing Modularity Maximization in Approximation, Heuristic, and Graph
Neural Network Algorithms for Community Detection [1.1220356822493742]
本研究は,最適分割を求めるために,様々なモジュール性に基づくアルゴリズムの性能を評価する。
概最適分割は、しばしば任意の最適分割と不均等に異なる。
モジュラリティがコミュニティの検出に使用される場合、より方法論的なモジュラリティ利用のための近似最適化アルゴリズムを推奨する。
論文 参考訳（メタデータ） (2023-10-17T00:12:18Z) - Heuristic Modularity Maximization Algorithms for Community Detection
Rarely Return an Optimal Partition or Anything Similar [0.0]
本稿では,現在のモジュラリティアルゴリズムが最大モジュラリティ分割を返却する成功度について検討する。
既存の8つのアルゴリズムを、モジュラリティを世界規模で最大化する正確な整数計画法と比較する。
以上の結果から, ほぼ最適分割は任意の最適分割と不均等に異なることが示唆された。
論文 参考訳（メタデータ） (2023-02-28T16:11:08Z) - Late Fusion Multi-view Clustering via Global and Local Alignment
Maximization [61.89218392703043]
マルチビュークラスタリング(MVC)は、異なるビューからの補完情報を最適に統合し、クラスタリング性能を改善する。
既存のアプローチの多くは、クラスタリングに最適な類似性行列を学ぶために、複数の事前定義された類似性を直接融合する。
これらの問題に対処するために、アライメントを通してレイトフュージョンMVCを提案する。
論文 参考訳（メタデータ） (2022-08-02T01:49:31Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-03-28T21:34:16Z) - Learning a Large Neighborhood Search Algorithm for Mixed Integer
Programs [6.084888301899142]
混合整数プログラム(MIP)に対する学習型LSSアプローチの検討
ニューラル・ディバイディング・モデルを用いて代入よりも確率分布を表現し、既製のMIPソルバとともに初期代入を生成する。
そこで我々はニューラル近隣選択ポリシーを訓練し,各ステップで探索地区を選択する。
論文 参考訳（メタデータ） (2021-07-21T16:43:46Z) - Bayesian Algorithm Execution: Estimating Computable Properties of
Black-box Functions Using Mutual Information [78.78486761923855]
多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。
本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。
これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
論文 参考訳（メタデータ） (2021-04-19T17:22:11Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Efficient semidefinite-programming-based inference for binary and
multi-class MRFs [83.09715052229782]
分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。
一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
論文 参考訳（メタデータ） (2020-12-04T15:36:29Z) - Learning All Credible Bayesian Network Structures for Model Averaging [3.81379858342235]
近似アルゴリズムの性能保証に着想を得たモデル平均化手法を提案する。
我々のアプローチは既存のアプローチよりも効率的で、ベイズ的ネットワークにスケールする。
論文 参考訳（メタデータ） (2020-08-27T19:56:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。