大規模グラフに対する効率的なグラフ要約に関する研究

点击翻译按钮获取中文摘要

本研究課題の目的は実世界の大規模グラフに対する高圧縮率で高速かつ実用的なグラフ要約技術を開発することである．グラフ要約に関する既存手法では (1) 圧縮率の高い，(2) シングルスレッドで動作する，(3) 情報の欠損がないという3つの望ましいを同時に満たせない上，実行速度も十分ではない．本研究期間において，グラフのウェッジと呼ばれる連結な3ノードに着目してノードを集約するウェッジ分割法というアプローチ，およびその効率的な活用法について明らかにした．具体的には，理論解析を通じてウェッジ分割は各スーパーノード・スーパーエッジがなるべく密になるような分割を設計することで効率的になることを定理を用いて示し，それを実現するような3つのアルゴリズムを提案し，それぞれの性能を実験により評価した．我々の実験において，3つのアルゴリズムのうち最も効率的な分割を実現する提案手法は既存手法と比較して最大5ポイント圧縮率が高く，2.5倍高速で，情報の欠損がなく，実装が容易であるという優位性を実世界のグラフに対して実現した．本研究成果は現在1件の学術誌論文として投稿中である．今後の研究としては，更なる圧縮率の向上と要約グラフ上で動作するグラフ分析アプリケーションの開発を進める予定である．そのためのアイデアとしては，3ノード以上の要約を行うためのモジュラリティに基づくスーパーノードの作成，パス単位での集約方式や，コアツリー分解によるコア部とツリー部それぞれに対する最適化などが挙げられる．