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

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

今後の課題

グラ

フあるいは距離行列によって、点の集合における点の関連性の高さを示すことができる。ま

た、点集合が空間に埋め込まれたことにより、グラフあるいは距離行列における具体的な距離や

長さがわかる。

点の距離によって定義される幾何学的グラフは、私が「誘導ネットワーク」と名付けたグラフの代表例で

ある。誘導ネットワークでは、何らかの外部データソースから機械的な方法で辺が定義される。これはデー

タサイエンスでネットワークを構築するためによく使われている方法であり、データセットをどうすればグ

ラフに変換できるかに注意する必要がある。

一連の要素からネットワークを作るには、普通は距離関数や類似度関数が使われる。一般に、個々の頂点

を k 個の最も近い頂点や類似する頂点に接続する辺に注目する。k を小さく保てば（目安は k ≈ 10）疎グ

ラフが得られる。疎グラフは、n が大きくても簡単に操作できる。

しかし、誘導ネットワークには他の種類もある。よくあるのは、意味のある属性を共有する頂点 x と y を

接続するものだ。例えば、履歴書を使えば人々の誘導ソーシャルネットワークが作れる。同じ時期に同じ会

社に在籍していたり、同じ学校に通っていた 2 人を結ぶのである。このようなネットワークは、クリークを

形成する頂点の大規模な部分集合を含む塊状の構造を含むことが多い。x が y と同じ大学を卒業し、y が z

と同じ大学を卒業していれば、(x, z) も同じグラフの辺でなければならない。 ...