論文の概要: The Bayan Algorithm: Detecting Communities in Networks Through Exact and
Approximate Optimization of Modularity
- arxiv url: http://arxiv.org/abs/2209.04562v3
- Date: Sat, 8 Jul 2023 16:23:56 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-11 22:46:59.344442
- Title: The Bayan Algorithm: Detecting Communities in Networks Through Exact and
Approximate Optimization of Modularity
- Title(参考訳): bayanアルゴリズム:モジュラリティの完全および近似最適化によるネットワーク内のコミュニティの検出
- Authors: Samin Aref, Hriday Chheda, and Mahdi Mostajabdaveh
- Abstract要約: コミュニティのモジュール化は、ネットワーク科学における古典的な問題である。
Bayan は最適性または最適エッジに近接したパーティションを返す。
Bayanはオープンソースや商用のソリューションよりも数倍高速だ。
- 参考スコア(独自算出の注目度): 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. Among numerous approaches, the most common
method is modularity maximization. Despite their design philosophy and wide
adoption, heuristic modularity maximization algorithms rarely return an optimal
partition or anything similar. We propose a specialized algorithm, Bayan, which
returns partitions with a guarantee of either optimality or proximity to an
optimal partition. At the core of the Bayan algorithm is a branch-and-cut
scheme that solves an integer programming formulation of the modularity
maximization problem to optimality or approximate it within a factor. We
compare Bayan against 30 alternative community detection methods using
structurally diverse synthetic and real networks. Our results demonstrate
Bayan's distinctive accuracy and stability in retrieving ground-truth
communities of standard benchmark graphs. Bayan is several times faster than
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. Overall, our assessments point to Bayan as a
suitable choice for exact maximization of modularity in real networks with up
to 3000 edges (in their largest connected component) and approximating maximum
modularity in larger instances on ordinary computers. A Python implementation
of the Bayan algorithm (the bayanpy library) is publicly available through the
package installer for Python (pip).
- Abstract(参考訳): コミュニティ検出はネットワーク科学における古典的な問題であり、様々な分野に幅広く応用されている。
多くのアプローチの中で、最も一般的な方法はモジュラリティの最大化である。
設計哲学と広く採用されているにもかかわらず、ヒューリスティックなモジュラリティ最大化アルゴリズムが最適分割を返すことは滅多にない。
そこで我々は,最適性あるいは最適分割への近さを保証した分割を返却する特殊アルゴリズムbayanを提案する。
ベイアンアルゴリズムの中核は、モジュラリティ最大化問題の整数計画式を最適性や係数内で近似する分岐とカットのスキームである。
構造的に多様な合成および実ネットワークを用いた30種類のコミュニティ検出手法と比較した。
この結果は,標準ベンチマークグラフの基幹コミュニティの検索におけるベイアンの特異な精度と安定性を示す。
Bayanは、モジュラリティの最大化のためにオープンソースや商用の解決器よりも数倍高速で、既存の方法では最適化できないインスタンスの最適なパーティションを見つけることができる。
全体として、ベイアンは最大3000のエッジを持つ実ネットワークにおけるモジュラリティの正確な最大化と、通常のコンピュータ上での大規模インスタンスにおける最大モジュラリティの近似に適した選択であると評価している。
Bayanアルゴリズム(bayanpyライブラリ)のPython実装は、Pythonのパッケージインストーラ(pip)を通じて公開されている。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。