論文の概要: 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)を通じて公開されている。
関連論文リスト
- Multi-Modal Optimization with k-Cluster Big Bang-Big Crunch Algorithm [0.7639610349097473]
本稿では,クラスタリング,すなわちk-BBBCに基づくBig Bang-Big Crunchアルゴリズムのマルチモーダル最適化版を提案する。
このアルゴリズムは全人口の完全な収束を保証し、特定の問題に対する局所最適化の99%を平均で取得する。
論文 参考訳(メタデータ) (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) - BOtied: Multi-objective Bayesian optimization with tied multivariate
ranks [49.85896045032822]
非支配解と最高多変量階との自然な関係を示し、これは合同累積分布関数(CDF)の最外層線と一致する。
我々はCDFインジケータに基づくBOtiedと呼ばれる取得関数を提案する。
論文 参考訳(メタデータ) (2023-06-01T04:50:06Z) - Online and Streaming Algorithms for Constrained $k$-Submodular
Maximization [25.15934533974176]
制約付き$k$-submodularは、広告アロケーション、インフルエンス、パーソナライズされたレコメンデーションなど、多くの個別の最適化問題をキャプチャする一般的なフレームワークである。
本研究では,モノトーンと一般(おそらく非モノトーン)の両方の目的に制約された$k$サブモジュールのシングルパスストリーミングとオンラインアルゴリズムを開発する。
論文 参考訳(メタデータ) (2023-05-25T12:53:17Z) - 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) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳(メタデータ) (2021-06-02T22:03:36Z) - 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) - Combinatorial Bayesian Optimization with Random Mapping Functions to
Convex Polytopes [43.19936635161588]
大規模空間でうまく動作するような空間におけるベイズ最適化法を提案する。
提案アルゴリズムは,既存手法と比較して良好な性能を示す。
論文 参考訳(メタデータ) (2020-11-26T02:22:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。