データサイエンス設計マニュアル

10.3 グラフ、ネットワーク、距離 297

名前や識別子が与えられている。ラベルなしグラフには、そのように区別できる手段はない。

データサイエンスで使われるグラフは、交通ネットワークの都市名などのように、自然に意味のある

形でラベルが付けられていることが多い。こういったラベルは代表例の識別子として役に立つ。適切

であれば、外部データソースとのリンクの手段にもなる。

10.3.3 グラフ理論

グラフ理論は、ネットワークの基本的な性質やそれらの計算方法を扱う数学の重要な分野である。計算機

科学を学んだ学生の大半は、離散構造やアルゴリズムの授業を通じてグラフ理論に触れている。

最短

経路、連結成分、全域木、カット、マッチング、トポロジカルソート用の古典的なアルゴリズムは、

一般的なグラフにすべて応用できる。データサイエンスでもこのようなアルゴリズムは使われていてよいは

ずだが、私が期待するほどには、これらは広く使われていないようだ。その理由の 1 つは、データサイエン

スのグラフが非常に大規模になり、それらに対してできることの複雑度におのずと限度があることだろう。

しかし、理由の大部分はものの見方が浅いことにある。人々は、距離や類似度の行列が実際には他のツール

を利用できるグラフにすぎないことに気付いていないのである。

この機会を利用して、本書ではこれらの基本問題とデータサイエンスのつながりを見直しておきたい。興

味のある読者は、ぜひ私のアルゴリズム本 [Ski08] を使って理解を深めてほしい。

• 最短経路