大規模における効率的な並列Dコア分解

有向グラフは、ソーシャルネットワーク、ウェブネットワーク、通信ネットワークなどで広く見られます。有向グラフのよく知られた概念はDコア、または(k, l)-コアであり、それは各頂点が入次数k以上、出次数l以上を持つ最大部分グラフです。すべての可能なkおよびlの値に対する非空Dコアを計算すること、すなわちDコア分解は、ソーシャルネットワーク分析、コミュニティ探索、グラフ可視化など多様な応用が見られます。しかし、既存のDコア分解アルゴリズムは、大規模なグラフにおいて効率性とスケーラビリティの問題に直面しています。なぜなら、直列ペリングベースのアルゴリズムは単一コアの利用に制限され、スカイラインコアネスベースの手法は非常に高い時間複雑度を示すからです。これらの問題に対処するため、本論文ではマルチコアCPUの計算能力を活用してDコア分解の効率的な並列アルゴリズムを提案します。具体的には、まず、各可能なk値に対するDコアを計算する新しいアルゴリズムを提案します。これは暗黙のレベルごとの頂点削除戦略を利用するもので、頂点間の依存関係を軽減するだけでなく、時間複雑度を直列アルゴリズムに類似させることも維持します。さらに、D-shellという新しい概念を導入することにより、対応するDコアを計算する際に必要なk値を減少させ、現在計算されたDコアから大きなk値を持つDコアを導出することによって冗長な計算を削減する高度なアルゴリズムを開発します。10の現実の大規模グラフに対する広範な実験は、我々のアルゴリズムが非常に効率的でスケーラブルであることを示しており、高度なアルゴリズムは32スレッドを用いた最先端の並列分解アルゴリズムよりも最大で2桁のオーダーで速いことが分かりました。