密な部分グラフを探して: 貪欲なピールの効果はいかに？

与えられたグラフにおける最も密な部分グラフを見つける問題は、特にソーシャルネットワーク分析、タンパク質、遺伝子ネットワークなどの分野において、いくつかの実世界の応用があります。アプリケーションによっては、密な部分グラフを見つけることで、高い重要性を持つ領域、類似の特徴、または強化された相互作用を特定することができます。最も密な部分グラフの抽出問題は根本的に非線形最適化問題です。それにもかかわらず、最大流サブ問題の一連を反復的に解くことに基づく正確なアルゴリズムにより、多項式時間内に解決できます。その多項式時間の複雑さにもかかわらず、非常に大きなグラフに対する正確なアルゴリズムに必要な計算時間は高くつく可能性があります。そのため、数百万の頂点や辺を持つグラフに対処するためには、ヒューリスティックアルゴリズムに頼る必要があります。文献からの非常に速く、いくつかの優れた理論的特性を持つ貪欲なヒューリスティックの効率的な実装を提供します。また、貪欲法と正確な方法に基づいた新しいヒューリスティックアルゴリズムも導入します。文献と実世界から取得した86のインスタンスで構成されたベンチマークに対し、さまざまなアルゴリズムの性能を評価するための広範な計算研究が提示されています。この分析は、提案されたヒューリスティックアルゴリズムが多くのテストインスタンスに対して非常に効果的であり、しばしば最適解または短時間の計算内で準最適解を提供することを示しています。