Triangle-Countingのための大規模グラフ分割手法
平野 竜洋 (1351090)
近年，ソーシャルネットワークやインターネットのWebページ間の接続関係などのグラフとして表現されるデータの高速処理の需要が高まっている．
その中でも，Triangle-Countingと呼ばれるグラフ中の頂点間に形成される三角形の数を求めるアルゴリズムは，Webにおけるスパムページの検出などに用いられており，非常に重要である．
これまでに提案されてきたTriangle-Countingのアルゴリズムは，計算機のメモリ量の制約により大規模なグラフに対して適用できない，または，並列計算機上での分散処理に対応していても，計算資源間のロードバランスが不十分であるなどの問題が存在した．
本研究では大規模グラフのTriangle-Countingの高効率化を目指して，均等なロードバランスを実現するグラフデータの分割手法を提案する．点を基準に分割しており，辺は同じ領域か，異なる領域を結んでいるかの2つである．
三角形の数を正確に数えるためには，分割後の領域内だけではなく，複数の領域にまたがる辺から形成される三角形を考慮しなければならない．従来手法では複数の領域にまたがる辺が多く，それが処理のボトルネックとなっていた．
そのため，複数の領域にまたがる辺を少なくすることが課題である．
本研究では，グラフデータは一部の点に辺が集中しており，大多数の点は小さい次数を持つことに着目した．
次数が高い点とそれに付随する点を同じ領域にすることで課題を解決した．
評価の結果，従来手法と比較した場合，同程度の最大で約66%の処理時間を削減することに成功した．