高速クリーク・密部分グラフマイニングアルゴリズム

High-Speed Clique/Dense subgraph Mining Algorithms

Takeaki Uno

近年のデータの巨大化・複雑化になる。単に項目数の増加だけだなく、データの構造の変化しつつある。代表的な例は、SNSなどのソーシャルネットワークにおいてはユーザがどのようにつながり、コミュニティを形成しているかが解析の大きなトピックである。伝統的なクラスタリングにより、グラフ頂点（ユーザ）を分割するアプローチがあるが、前述のようなデータには、効率なアプローチとは限らない。このような場合には、クラスタマイニング、あるいは、コミュニティマイニングと呼ばれる手法が有効である。

　クリークは、すべての頂点間に枝があるような部分グラフである。クリークはグラフ理論や組み合わせアルゴリズムにおいて基礎的なものであるため、非常に多くの研究がある。最大クリークの発見はNP完全であるが、疎な実データでは効率的に解ける。

　違う分野だから、アルゴリズムを詳しくわかるのが要らない。クリーク・密部分グラフマイニングの応用・問題点について知っておくだけでいいだろう。

パターンマイニングへの応用

与えられたデータベースと項目の間の関係を似部グラフで表現すると、「アイテムの集合」とアイテムを含む項目の集合」が２部クリークを構成することがわかる。その時、飽和集合マイニングは極大二部クリークの列挙と等価である。

頻出アイテム集合マイニング、特に飽和集合マイニングにおいては、極大二部クリークのアルゴリズムは非常に高速で、他の手法より大幅に計算時間が短くなる。

密部分グラフの列挙

グラフの部分グラフで、中に枝が多く存在するものを密部分グラフと呼ぶ。（密部分グラフには、密度の定義が様々存在する）

アルゴリズムは、「Uno,T:An efficient algorithm for solving pseudo Clique Enumeration Problem」の論文に参考してください。

この手法を頻出パターンに応用すると、多くの項目に曖昧に含まれるパターンを列挙するアルゴリズムができる。(Ambiguous frequent itemset mining and polynomial delay enumeration).

本稿で紹介しているアルゴリズムはすべてUnoさんのHPから実装がダウンロードできる。