Small World GraphとDijkstra
Small World GraphとDijkstra
今Think Complexity
chap4)で勉強した
について簡単にまとめを行いたいと思います． Think Complexity は無料で読む事もできます！
Small World Graph
社会学者であるStanley Milgram は権威に対する服従についてのMilgramの実験やスモールワールド現象 についての実験で有名な人です．スモールワールドの実験は 任意の人を選び，目標人物に平均して何人を経由する事で 手紙を渡せるかを検証した実験です．成功した例はわずかでしたが， その中での平均は6人だったそうです．詳しくはこちらをご覧下さい．
その後，Duncan WattsとSteven Strogatzが
このスモールワールド現象について説明した論文を発表しました．
彼らはランダムグラフと正則グラフに着目し，２つの特徴を定式化しました．
それはclustering coefficient: C(p) (クラスタリング係数)とaverage path length: L(p)(平均パス距離)です．
clusteringは簡単に言うと共通の知人を持つaとbが直接の 知人である確立を表しています．
path lengthは各ノードと全てのノードとの最短パスの距離を平均したものです．
詳しい定義はこちらで一番最初に出てくるpdfをご覧下さい．
Small worldというグラフ構造はノードがクラスタ状
に集まっている
（ノード間に張られているエッジの密度が高いノードの集まり）
にも関わらず，ノード間のパス
が短いという特徴をもつグラフです．つまり，クラスタリング係数Cが
大きく，パスの距離Lが小さい状態のことを言います．
スモールワールドグラフの実装は非常に簡単です．n個のノードがあり
次数がkである時に，ノードをリング状につなぎます（正則グラフ）．
その後，各々のノードの各々のエッジを確立pでランダムに再接続(rewire)します．
この確立p が~0.01の付近でスモールグラフになります．
スモールグラフは次数kのリング状の正則グラフを作成(add_regular_edges)したあとに，
再接続(rewire)することで作成できます．以下が実装例となります．
Dijkstra
続いて，semaphore(セマフォ)やダイクストラのアルゴリズムで有名な オランダのコンピュータサイエンティストEdsger W. Dijkstraの Dijkstraのアルゴリズムを紹介します．
Dijkstraのアルゴリズムは任意のノード間の最短パスを 効率的に求めるアルゴリズムです．一般的にはエッジに重みがあるグラフを 考えますが，今回はエッジの重みを考慮しない簡易化したものを考えます．
簡易化したDijkstraのアルゴリズムはBFSと殆ど同じで， 訪問した時にマークする代わりに距離のラベルを与えます．
アルゴリズムは以下のようになります．
- step1 ソースノードに距離0を与え，wokrlistに追加します．他のノード には無限の距離を与えます．
- step2 wokrlistからノードを削除し距離dに代入します．続いて，そのノードが隣接する隣接ノードを探します．それらのノードに距離d+1を代入しworklistに追加します．
- step3 worklistが空なら終了し，それ以外はstep2に戻ります．
ここでは，エッジの重みがない場合（全て均等）としているので，距離に
1を足しています．本来なら重みを足します．
以下に，上で紹介した簡易化したdijkstraの実装例， clustering coefficient:C(p)，average path length:L(p)の 実装例を示します．
まとめ
今回は，Small World Graphの説明・実装例， dijkstraのアルゴリズムの説明・実装例とクラスタリング係数と 平均パス距離の実装を紹介しました．
スモールワールドグラフはクラスタリングがある場所 （ノードが人間であればコミュニティ）と他のコミュニティを つなぐ部分を理解する助けになり，ビジネスにも活用出来ると思います． 例えば，そこに集中して広告することで複数の コミュニティに効果的に広告出来る事が考えられます． スモールワールドはビジネスへの応用が期待出来るなと感じる事ができました．
reference
