【ネットワーク分析】 #1 グラフってなんぞや

最近真面目な投稿をしていないので、ネットワーク分析とかグラフ理論とかその周辺のアルゴリズムとかについてシリーズっぽくゆるゆると記述していこうと思います。
本シリーズでは、「ネットワークだぁ？グラフだぁ？全く知らないよ！」って方を対象に書いていくつもりです。

ネットワーク分析とは

ネットワーク分析とは、グラフ理論におけるグラフで表現したものに対する分析方法です。
対象となるデータは幅広く、SNSの繋がりとか感染症の伝搬だとか色々あります。

そもそもグラフとは

グラフ理論のグラフとかドヤ顔で言われてもわかんないですよね。いやそれが普通だと思います。
グラフとは、頂点(またはノード、V: Vertex)と辺(または枝、E: Edge)で表されるものと定義されています。
それらの集合を数学っぽく記述すると、


となります。これは、頂点N個と、枝M本の集合を表すという具合です。
頂点は、何か物(？)を示し、枝はその物々の繋がりを示します。
身近な例で言うと、高速道路の出入り口が頂点、高速道路そのものが枝だと考えたらわかりやすいかと思います。

図1: 簡単な例・首都高のサイトより 引用元: http://search.shutoko.jp/

有向グラフと無向グラフと次数

グラフと言っても2種類あります。有向グラフと無向グラフです。
何が違うのかといいますと、有向グラフは向き(方向)が指定されており、無向グラフは向きが指定されていません。
また、頂点に接続している枝の数のことを次数といいます。
有向グラフにおいては、出次数(でじすう)と入次数(いりじすう)の2つが存在します。

無向グラフ

無向グラフとは、簡単に言うと、頂点間を結ぶ枝向きが指定されていないグラフです。
データセットとかのサイトに行くと、undirectedと記述されているものがそれです。
簡単な図で示しますと、以下の図2です。

図2: 私が描いた無向グラフ

この図1では、

という枝があることが分かります。
次数ですが、から順に
3, 4, 3, 4, 2
となっており、最大次数は頂点とにおける4となります。

てか、図汚いですね。はてなフォトライフめ・・・。

有向グラフ

有向グラフとは、簡単に言うと、頂点間を結ぶ枝向きが指定されているグラフです。つまり、どこからどこに向かって、枝があるのか…というのが表現できます。
データセットとかのサイトに行くと、directedと記述されているものがそれです。
簡単な図で示しますと、以下の図3です。

図3: 私が頑張って描いた有向グラフ

このグラフですと、がモテモテですね。

出次数ですが、から順に
0, 4, 2, 2, 0
となります。
これは、点から出て行く枝の数を表します。わかりやすく言うと、何人に向けてラブレターを書いたかみたいな感じですね。

一方、入次数はから順に
3, 0, 1, 2, 2
となります。
これは、店に入ってくる枝の数を表します。わかりやすく言うと、何人からラブレターをもらったかという感じですね。

隣接行列

グラフには、その隣接関係を示す隣接行列というものがあります。
簡単に言うと、どことどこがつながっとんねんって話です。
行、列ともに頂点集合に対応しています。
ちなみに、蛇足ながら書くと領域計算量はです(頂点の数をnとした場合)。

無向グラフにおける隣接行列

図2の例を元に隣接行列を書くと、

となります。
無向グラフの場合、双方の向きを考慮しないため、行列は対称となります。

有向グラフにおける隣接行列

図3の例を元に隣接行列を書くと、

となります。
有向グラフの場合、向きを考慮し、それを隣接行列でも表現するため、行列は非対称となります。
行方向に攻め、列方向に受け、と考えると簡単だと思います。

今回のまとめ

簡単な事項について取り扱いました。
ループとか、重みとか、接続行列とか色々すっとばしていますが、今回はここまで…。