並列言語Tascellを用いた共通アイテム集合を持つ連結部分グラフ抽出の並列化
Parallelization of Extraction of Connected Subgraphs with Common Itemsets using Parallel Language Tascell
概要
各頂点がアイテムの集合を持つグラフ構造から、ある閾値以上の数の共通アイテム集合を持つ連結部分グラフを抽出するグラフマイニングは様々な分野において有用です。例えば、ソーシャルネットワークにおける各人の興味と友人関係から、共通の興味をもつ友人関係を抽出できます。しかし、一般にグラフの規模が大きくなるに従い部分グラフの数は指数関数的に増加してしまい、部分グラフの抽出に膨大な時間がかかってしまいます。共通のアイテム集合を持つ連結部分グラフを効率良く抽出する逐次用のアルゴリズムは既に提案されていますが、並列化はまだ行われていません。そこで本研究では、並列処理向けにこのアルゴリズムを拡張し、それを我々の研究室で開発中の並列言語Tascellで実装しました。
産業界への展開例・適用分野
本研究が対象とするグラフマイニングはソーシャルネットワークだけでなく生体ネットワークの分析などにも応用できます。例えば、頂点が遺伝子、辺が遺伝子間の相互作用関係を示す遺伝子ネットワークにおいて、投与した薬をアイテムとして対応する頂点に付与させたグラフから共通のアイテム集合を持つ連結部分グラフを抽出できると、どの薬の組み合わせがどの遺伝子間で反応するかがわかり、創薬研究に役立ちます。
研究者
| 氏名 | 専攻 | 研究室 | 役職/学年 |
|---|---|---|---|
| 奥野 伸吾 | システム科学専攻 | 中島研究室 | 修士2回生 |
| 平石 拓 | 学術情報メディアセンター | 中島研究室 | 助教 |
| 中島 浩 | 学術情報メディアセンター | 中島研究室 | 教授 |