グラフ理論における基礎と基本用語

5.2.1 グラフの構成とその分類

グラフは，点集合Vと辺集合Eの組としてG = (V, E)と表現される．辺(edge)はVの 中の2点を結ぶ線分として表され，向きがある場合とない場合がある．前者を有向グラ フ(directed graph)と呼び，後者を無向グラフ(undirected graph)と呼ぶ．同一の2点間に複 数の辺がある場合，これらは多重辺(multiple edges)あるいは並列辺(parallel edges)と呼び，

多重辺が存在する場合を特に多重グラフ(multiple graph)と呼ぶ．逆に，多重辺が存在し ないグラフは単純グラフ(simple graph)と呼ぶ．また，点(node)や辺(edge)には重みやコス トと呼ばれる数値が割り当てられることもあり，このようなノードやエッジに重みを持 たせたグラフを重み付きグラフ(weighted graph)と呼ぶ³⁵⁾．重みを持たせないグラフは，

エッジがあるかないか，つまり0か1かで表現するため，バイナリグラフ(binary graph) と呼ばれる．図5.2にグラフの例を示す．

本研究では，エッジにトラクトグラフィで描出された線維の本数を重みとして表現し，

指方性を持たせていないので，undirected weighted graphを扱っていることになる．

図5.2 グラフの種類

36

5.2.2 グラフの行列表現

グラフの行列表現には大きく分けて隣接行列(adjacency matrix)と接続行列(incidence

matrix)の2種類がある．隣接行列は2つのノード間が隣接しているか否かを表現し，ノ

ードの数をn個とすると，n×n行列で表される．一方，接続行列は各ノードとそこにエ ッジが接続しているかを表現し，ノードの数をn，エッジの数をeとすると，n×e行列 で表される．グラフの行列表現の例を図5.3に示す．

ネットワークトポロジー(ネットワークの接続をグラフ理論的観点から見た時のグラ フ構造，いわゆる図5.2のようなグラフ構造図)の性質は，一般的に隣接行列で表現され る．本研究では，前述に加え，5.2.1節で述べたようにundirected weighted graphを用いて いるため，図 5.3(e)のような行列で表現される．なお，ノード自身へのエッジはないと するため，対角成分は全て0であるとする．

図5.3 グラフの行列表現の例

37

5.2.3 グラフ理論とスモールワールドネットワークモデル

グラフ理論は18世紀にEulerが創始した学問であるが，グラフの解析的な取り扱いを 大きく進歩させたのは，ErdősとRényiである．彼らは，1959年に“ランダムグラフ(random

graph)”(Erdős–Rényi model: ERモデル)というネットワークモデルを考案し，グラフ理論

が構造化されたグラフを扱うのに対して，確率を用いてグラフの構造化するということ にスポットライトを当てた．ランダムグラフは，同じノード，同じエッジ数で乱数を用 いて，ノードを他のノードへランダムにつなぐというルールで構成されるグラフである．

それ以降，グラフ理論の分野では目立った進展はなかったが，1998年にWattsとStrogatz は多数の蛍の点滅やコオロギの鳴き声が同調する現象を究明する中で，“Watts-Strogatz

model(WSモデル)”というスモールワールドモデルを考案し³⁶⁾，同様の性質が現実世界

の様々なネットワークにも共通して存在することを発見し，現実世界の様々な現象を説 明 す る 新 た な パ ラ ダ イ ム と し て 注 目 を 集 め た ． こ の 性 質 は ス モ ー ル ワ ー ル ド 性

(small-world)といい，任意の2つのノードが，中間にわずかな数のノードを介するだけで

接続されるという性質である ³⁷⁾．簡単な例を挙げると，「世間は狭い」と言われるよう に，一見赤の他人に見えても，実際は中間に少数の人を介するだけでつながっていると いうことである．

スモールワールドモデルは，現実世界のネットワークに近い性質を持つネットワーク モデルを極めて単純なアルゴリズムで生成するもので，インターネットや食物連鎖，論 文の被引用関係，さらには脳内のネットワークにおいても適応が可能となった³⁶⁾．スモ ールワールドモデルでは，①全てのノードを近隣のn個のノードと格子状にエッジでつ なぎ規則的な格子グラフを仮定し，②それらのエッジを確率pでランダムにつなぎかえ るというアルゴリズムでグラフを生成する．p = 0のとき，元の規則的なグラフ(regular

network)となり，p = 1 のとき，全てのエッジがランダムにつなぎかえられたグラフ

(random network)となる．そして0 < p < 1のときでは，regular networkとrandom network を併せ持つ構造，いわゆるスモールワールド性を持つネットワークが生成され，このよ うなネットワークをsmall-world networkと呼ぶ³⁸⁾．

規則的なグラフ(p = 0)のとき，ネットワーク全体のクラスター係数(隣接する任意のノ ード間が実際に連絡している割合の平均)は高くなり，平均経路長(任意のノードから任 意のノードへ至るステップ数の平均)は長くなる．ランダムグラフ(p = 1)のとき，ネット ワーク全体のクラスター係数は低くなり，平均経路長は短くなる．そして，スモールワ ールド性を持つネットワーク(0 < p < 1)のときでは，規則的なグラフに見られる高いクラ スター係数とランダムグラフに見られた短い平均経路長を併せ持つ．スモールワールド モデルで構築されるグラフの例とそれらのネットワークにおけるクラスター係数C(p)と 平均経路長L(p)の特徴を図5.4に示す³⁶⁾．

38

図5.4 スモールワールドモデルで構築されるグラフ例とそれらのネットワークにお けるクラスター係数C(p)と平均経路長L(p)の特徴(参考文献[36]より改変引用)