第4章 空間解析 2.ネットワーク分析 (3) ネットワーク構造分析

Presentation on theme: "第4章 空間解析 2.ネットワーク分析 (3) ネットワーク構造分析"— Presentation transcript:

1 第4章 空間解析 2.ネットワーク分析 (3) ネットワーク構造分析
第4章　空間解析 2.ネットワーク分析 (3) ネットワーク構造分析 久保田光一

2 ネットワーク構造分析の道具 グラフ・ネットワークの頂点の探索方法 グラフ・ネットワークの接続構造 深さ優先探索，DFS，スタックLIFO
幅優先探索，BFS，キューFIFO グラフ・ネットワークの接続構造 木，DAG 直径，連結性，連結成分 近接度，近接性 ・ネットワークの構造を調べるための基本的な道具として，ネットワークを表現するグラフ上の頂点を探索する方法がある． ・代表的な二つの探索方法として，深さ優先探索と幅優先探索がある． ・また，ネットワークの構造を表現する用語や指標の基本として，木，DAG,　連結性，連結成分，近接度，近接性がある．

3 グラフの探索の基本 グラフ中の頂点を一つ指定し，その頂点から辿れる頂点を適当な順番に辿る方法のひとつ 深さ優先探索，あるいは，縦型探索
Depth First Search (DFS) 幅優先探索，あるいは，横型探索 Breadth First Search (BFS) 混合タイプ，反復深化（iterative deepening)

4 深さ優先探索（DFS) 探索開始頂点 番号は探索順序を表す 1 2 8 3 6 9 4 5 7 10
・グラフの枝を，探索開始頂点からどんどん辿れるだけ辿る方法． ・訪問した頂点をマークしておき，何度も同じ頂点を訪問しないようにする． ・生き止まりになったら，最後に分岐したところに戻り，別の枝を辿る． 4 5 7 10

5 深さ優先探索（DFS) 探索開始頂点 番号は探索順序を表す 1 2 8 3 6 9 4 5 7 10
・グラフの枝を，探索開始頂点からどんどん辿れるだけ辿る方法． ・訪問した頂点をマークしておき，何度も同じ頂点を訪問しないようにする． ・生き止まりになったら，最後に分岐したところに戻り，別の枝を辿る． 4 5 7 10

6 深さ優先探索（DFS) 各頂点 u に探索済みかどうかを表す真偽値変数 u.flag を用意し，最初はそれを false にする．
探索開始頂点を u をスタック（LIFO）にプッシュ． while stack.empty() ≠ true do v = stack.pop() v.flag = true　 /* 頂点 v に関する処理 */ for all u such that 枝(v,u)が存在 if u.flag ≠ true do stack.push(u) ・Depth First Search の実際のプログラムには，スタックという構造を用いると，単純に記述できる． ・あるいは，いわゆるプログラムの再帰呼び出しを行っても同様である．

7 スタック（FILO, or, LIFO） FILO: First In Last Out 先に入れたものが後に出てくる抽象構造
二つの操作が可能 stack.push(x) : スタックに x を入れる stack.pop() : スタックから取り出す 山積みするようにしてものを出し入れする方法 ・プッシュは山に積む操作 ・ポップは山の一番上のものを取り出す操作 ・全部プッシュしてから，全部ポップすると，入れた順序と逆順になる． 3 2 1 1 2 3 stack

8 幅優先探索（BFS) 探索開始頂点 番号は探索順序を表す 1 2 3 4 5 6 7 8 9 10
・近い頂点から順に遠い頂点へと探索していく方法． ・探索のために到達するのに必要な枝の本数を1本ずつ増やしていくやり方 ・同じ頂点は2度以上探索しないようにマークするのはDFSと同じ 7 8 9 10

9 幅優先探索（BFS) 探索開始頂点 番号は探索順序を表す 1 2 3 4 5 6 7 8 9 10
・近い頂点から順に遠い頂点へと探索していく方法． ・探索のために到達するのに必要な枝の本数を1本ずつ増やしていくやり方 ・同じ頂点は2度以上探索しないようにマークするのはDFSと同じ 7 8 9 10

10 幅優先探索 各頂点 u に探索済みかどうかを表す真偽値変数 u.flag を用意し，最初はそれを false にする．
探索開始頂点を u をキュー（FIFO）にプッシュ. while queue.empty() ≠ true do v = queue.pop() v.flag = true /* 頂点 v に関する処理 */ for all u such that 枝(v,u)が存在 if u.flag ≠ true do queue.push(u) ・Breadth　First　Search　の実際のプログラム例． ・キューという構造を用いると単純に記述できる．

11 キュー（FIFO） FIFO: First In First Out 先に入れたものが先に出てくる抽象構造 二つの操作が可能
queue.push(x) : キューに x を入れる queue.pop() : キューから取り出す パイプにものを入れて，押し出す方法 ・push はパイプに押し込む操作 ・pop はパイプの反対側から取り出す操作 ・push した順に　pop　操作で取り出すことができる． queue 3 2 1 3 2 1

12 グラフの構造(木，DAG) 木（き），Tree DAG (Directed Acyclic Graph) 無閉路有向グラフ
グラフの n 個の頂点を繋げるn-1本の枝からなるグラフ DAG (Directed Acyclic Graph)　無閉路有向グラフ 有向グラフであって，閉路が無いもの

13 グラフの構造（道，有向道） 道（無向グラフ，有向グラフ） 有向道（有向グラフ）
頂点 v0 (始点）から，枝を辿って頂点 vq （終点）に至る頂点と枝の系列． q+1個の頂点　v0, v1, …, vq と q 個の枝　e1, e2, …, eq の系列として　(v0, e1, v1, e2, v2, …, eq, vq)　と表すとき，ek={vk-1, vk} ，ek=(vk-1,vk), または，ek={vk, vk-1} , ek=(vk, vk-1) となるもの 有向道（有向グラフ） 頂点 v0（始点）から，有向枝を辿って頂点 vq （終点）に至る頂点と枝の系列. q+1個の頂点　v0, v1, …, vq と q 個の枝　e1, e2, …, eq の系列として　(v0, e1, v1, e2, v2, …, eq, vq)　と表すとき，ek=(vk-1, vk) となるもの 枝の向き無視 ・有向グラフの場合，単に道というと，枝の向きを無視したものとなる． ・枝の向きを揃える場合には，有向道を考える． 枝の向き重要

14 グラフの構造（連結性） 連結性（無向グラフ，有向グラフ） 連結グラフ 非連結グラフ
グラフGのどの二つの頂点に対しても，一方を始点，他方を終点とする道が存在するとき，グラフG　を連結グラフという． 連結でないグラフを非連結グラフという． 連結グラフ 非連結グラフ

15 グラフの構造（２連結性） 2連結性（無向グラフ） ２連結グラフ ２連結グラフではない
任意の2個の頂点を選び，その2個の頂点を結ぶ2本の有向道（同じ頂点を経由しないもの）が存在するとき，そのグラフは2連結性があるという ２連結グラフ ２連結グラフではない

16 グラフの構造（連結成分） 連結成分 全体で1個の連結成分 2個の連結成分
連結性を満たす頂点の集合で元のグラフを分割したとき，各部分集合を連結成分という 全体で1個の連結成分 2個の連結成分

17 グラフの構造（近接度） ネットワーク上の頂点を固定し，その頂点が他の頂点にどの程度近いのかという近さを表す指標として，近接度がある
2頂点間の最短距離を　d(u,v) と記す．頂点 u の近接度は，u から u 以外の全ての頂点への最短経路の値の総和で定義される． ウォーシャル・フロイド法で d(u,v) を計算すればよい． ・グラフの頂点がほかの頂点にどの程度近いのかということを示す指標として，近接度というものが知られている． ・頂点　u の近接度は，頂点 u と他の頂点　v との最短距離の総和として定義される． ・これは，ワーシャルフロイド法で計算した任意の2点間の最短距離を表す行列（2次元配列）の結果から直ちに計算できる． ・最初の最短路の例について，各頂点の近接度を計算すると，このようになる． ・ほかにも構造を表す指標はいろいろとある． 池 新 御 秋 東 近接性 池袋 6 11 13 15 45 新宿 17 19 57 御茶ノ水 2 4 32 秋葉原 34 東京 40