サイト内の現在位置

Frovedisによるグラフ解析(GraphXとの処理速度比較)

no.0172022.3.4

 今回はグラフ解析におけるFrovedisとNetworkXのアルゴリズム実行時間を比較します。

 使用するデータセットはGraph partitioning and graph clustering : 10th DIMACS Implementation Challenge Workshopで用意されたものの一部をダウンロードしたものです。なお、new windowDIMACSはRutgers Universityをはじめとする大学や企業研究機関により共同運営されている離散数学に関する各種問題を取り扱うプロジェクトです。過去のImplementation Challengesはnew windowここから確認することができます。

 8種類のデータセットは論文における引用文献や共著者としての関係性を示すもの、インターネットのネットワーク形態をグラフデータ化したものなどを含んでいます。

 サンプルコードでは、初めにこれら8種類のグラフデータセットをロードする際に要する時間をFrovedisとNetworkXで比較します。

 続いて、Single Source Shortest Path (SSSP)、PageRank、Breadth First Search (BFS)、そしてConnected Components (CC)アルゴリズム実行時間を同様に比較していきます。


graph_analysis_column

 なお、今回取り上げたグラフアルゴリズムについては前回のブログの中でも使用していますので、new windowそちらもご参照ください。

 最後に、データセットロード、グラフアルゴリズム実行時間の比較結果を以下の各アルゴリズムに分けてグラフにまとめます。

グラフ
 
グラフ
 
グラフ
 
グラフ
 
グラフ

 各アルゴリズムにおいて、概ねFrovedisの方が高速であることが確認できました。ただしBreadth First SearchとConnected Componentsでは一部のデータにおいてFrovedisで多く時間がかかっています。しかし、時間の絶対値で見るとそれらほとんどは、およそ0.001~0.010secの範囲内での比較であり、総括的にはFrovedisの優位性を損なうものではないと考えます。

 離散数学の一分野として組合せ論などと共に取り上げられることが多いグラフ理論は、有限であるノード、エッジから構成されるネットワークを解析する手段として大学等の教育テーマとして多く取り上げられています。グラフ理論を活用することで様々な社会問題が効率的に解決されることが期待されていますが、その他AI・機械学習と比較して広く実社会で利用され始めるのはこれからと言われています。

 Frovedisを使用した高速なグラフ解析によって、より大規模で複雑なネットワークに関する問題解決にお役立てください。

関連リンク