グラフデータベース ―Neo4jによるグラフデータモデルとグラフデータベース入門

7章グラフ理論を使った予測分析

本章では、グラフデータを処理するための分析手法やアルゴリズムを検討します。グラフ理論とグラフアルゴリズムはどちらも成熟し十分に理解されたコンピュータ科学の分野であり、この両方を使ってグラフデータベースから高度な情報を取り出す方法を実証します。コンピュータ科学の経験を持つ読者はおそらくこのようなアルゴリズムや手法がわかるでしょうが、本章では好奇心のある読者が足を踏み入れたくなるように数学に頼らずに説明します。

7.1　深さ優先探索と幅優先探索

高次の分析手法を調べる前に、グラフ全体をたどるための基礎となる基本的な幅優先探索アルゴリズムを復習しておく必要があります。本書でいままで登場したほとんどのクエリは、実際は幅優先ではなく深さ優先でした。つまり、開始ノードから終了ノードまで外向きに走査してから、同じ開始ノードからの別の経路を同様に繰り返し探索していきます。深さ優先は、離散した情報を見つけるために経路をたどろうとしているときに優れた戦略です。

情報に基づいた深さ優先探索

古典的な深さ優先アルゴリズム探索は、単にグラフの終端を見つけるまで経路を探索するという点で、情報に基づいていません。終端に到達したら、開始ノードに引き返して別の経路を試します。しかし、グラフデータベースは意味的に豊かなので、特定のブランチに沿った探索を早く終了できます（例えば、適合する外向きの関係がないノードを見つけた場合や「十分遠くまで」走査した場合）。このような情報に基づいた探索は、実行時間の軽減につながります。このような探索は、まさにこれまでの章でCypherによる一致やトラバーサルが行っていた探索です。

一般的なグラフトラバーサルの基礎戦略として深さ優先探索を使ってきましたが、多くの興味深い「高次」アルゴリズムはグラフ全体を ...