大規模二部グラフにおける最大類似重みバイクリック列挙

本論文では、大規模二部グラフに対する最大類似重みバイクリック列挙の問題を研究します。エッジ重み付き二部グラフ G= (U, \ V, \ E) と重み差の閾値が与えられた場合、我々の目標は、重み差がそれより大きくないような、G の最大完全部分グラフ B (L, \ R) としての最大類似重みバイクリックを効率的に列挙することです。この問題は、アイテム推薦、詐欺検出、遺伝子発現データのバイクラスタリングなど、さまざまな応用があります。我々の知る限り、この問題を体系的に研究したのは初めてです。この問題は #P 完全性のため効率的に解決することが非常に難しいです。本論文では、MSWBE と呼ばれる二段階の枝刈り基準法を提案し、深さ優先の方法で探索空間を探索します。MSWBE は我々の問題に対する有用な計算フレームワークを提供しますが、列挙中の候補集合が大きいため、その性能は満足のいくものではありません。これを緩和するために、我々は MSWBE++ と呼ばれる高度なアプローチを提案します。特に、MSWBE++ はエッジの接続性と重み情報を同時に利用することで探索空間を活用し、候補集合を大幅に精緻化します。深さ優先探索戦略に従って MSWBE++ を単純に実装すると非最大バイクリックが生成されることを認識し、非最大集合を早期に廃棄できる幅優先探索戦略を開発します。計算を加速するために、効果的なグラフ削減技術を導入します。10の実データセットに対する広範な実験結果は、MSWBE++ が基準方法を最大2桁のオーダーで上回ることを示しています。最大類似重みバイクリックが詐欺的な評価検出のための有用な探索手がかりを提供できることを示すケーススタディも実施します。