データ分析によるネットワークセキュリティ

273

13

章 

グラフ分析

グラフは、1つ以上のリンク（辺）で接続される1つ以上のノード（節点）からなる数学的構造であ

る。グラフを用いると、複雑になりがちな通信を効果的に表現することができる。グラフを用いる

と、ネットワークの全体的な接続関係を、パケットサイズやセッション長などの細部を抽象化して、

モデル化することができる。さらに、中心性などのグラフの属性を用いて、ネットワークの中の重要

なノードを特定することができる。また、多くの重要なプロトコル（特にSMTPとルーティング）は、

ネットワークをグラフとしてモデル化するアルゴリズムに依存している。

以下では、グラフの分析的特性に重点を置いて説明する。まずはグラフとは何かを説明し、グラ

フの主な属性（最短経路、中心性、クラスタ、クラスタ係数）を例を通じて示す。

13.1

 グラフの属性：グラフとは何か

グラフとは、一連のオブジェクトとその相互関係の数学的な表現である。グラフはケーニヒスベル

グの橋を渡る問題を解決するために1736年にレオンハルト・オイラー（Leonhard Euler）が考案し

たもので、それ以来、陰謀のコアとなるメンバーから英語で発音する音の頻度にいたるまであらゆる

ものをモデル化してきた。グラフは非常に強力で柔軟な表現が可能なツールで、その強力さの源は、

その非常に高い代替性にある。数学、工学、社会学の研究者は、さまざまなグラフ属性を構築もし

くは観測し、さまざまな挙動のモデル化に用いている。グラフを使う際の最初の課題は、どの属性

が必要になるか、どう ...