グラフアルゴリズム

第1章 はじめに

この作品はAIを使って翻訳されている。ご意見、ご感想をお待ちしている：[e-mail]

グラフはコンピュータ・サイエンスの統一テーマのひとつであり、交通システム、人間関係、通信ネットワークなどの組織を記述する抽象化表現である。これほど多くの異なる構造を単一の形式を用いてモデル化できることは、教養あるプログラマにとって大きな力の源である。

アルゴリズム・デザイン・マニュアル』（スティーブン・S・スキエナ著、シュプリンガー）、 ストーニーブルック大学コンピュータサイエンス特別教授

今日、最も差し迫ったデータの課題は、単なる個別データの集計ではなく、関係性を中心に据えている。グラフ・テクノロジーとアナリティクスは、研究、社会的イニシアティブ、そして以下のようなビジネス・ソリューションで使用される、接続されたデータのための強力なツールを提供する：

• 金融市場からITサービスまで、ダイナミックな環境をモデリングする

• 伝染病の蔓延や、波及するサービスの遅延や停止を予測する。

• 金融犯罪に対抗するためのマシンラーニングの予測特徴の発見

• パーソナライズされた体験と推奨のためのパターンを発見する

データがますます相互接続され、システムがますます高度化するにつれ、データ内の豊かで進化する関係を活用することが不可欠になっている。

この章では、グラフ解析とグラフ・アルゴリズムについて紹介する。まずグラフの起源について簡単に復習してから、グラフアルゴリズムを紹介し、グラフデータベースとグラフ処理の違いについて説明する。現代のデータそのものの性質や、つながりの中に含まれる情報が、基本的な統計メソッドで明らかにできるものよりもはるかに高度なものであることを探る。この章の最後では、グラフ・アルゴリズムが採用されるユースケースを紹介する。

グラフとは何か？

グラフの歴史は、レオンハルト・オイラーが「ケーニヒスベルクの7つの橋」問題を解いた1736年に遡る。この問題は、7つの橋で結ばれた都市の4つのエリアすべてを、それぞれの橋を1度だけ渡りながら訪れることが可能かどうかを問うものだった。それは不可能だった。

オイラーは、接続そのものだけが重要であるという洞察によって、グラフ理論とその数学の基礎を築いたのである。図1-1は、論文"Solutio problematis ad geometriam situs pertinentis "に書かれたオイラーの当初のスケッチである。

図1-1. グラフ理論の起源ケーニヒスベルクの街は、2つの大きな島と本土の2つの島を7つの橋で結んでいた。パズルは、各橋を一度だけ渡り、街を歩くコースを作成することだった。

グラフは数学に端を発するが、データをモデル化し分析するための実用的で忠実度の高い方法でもある。グラフを構成するオブジェクトはノードまたは頂点と呼ばれ、それらの間のリンクはリレーションシップ、リンク、またはエッジと呼ばれる。本書ではノードと リレーションシップという用語を使う。ノードは文中の名詞、 リレーションシップはノードに文脈を与える動詞と考えることができる。混乱を避けるために言っておくが、本書で扱うグラフは、図1-2のような方程式やグラフのグラフ化とは何の関係もない。 ...