Subscribed unsubscribe Subscribe Subscribe

Python, web, Algorithm 技術的なメモ

技術的なメモを書いていきます.pythonistaを目指しています.

Small World GraphとDijkstra

Small World GraphとDijkstra

Think Complexityアルゴリズム複雑系について勉強しています. 今回は,自分の勉強を兼ねてThinkComplexity(chap4)で勉強した

について簡単にまとめを行いたいと思います. Think Complexity は無料で読む事もできます!

Small World Graph

社会学者であるStanley Milgram は権威に対する服従についてのMilgramの実験やスモールワールド現象 についての実験で有名な人です.スモールワールドの実験は 任意の人を選び,目標人物に平均して何人を経由する事で 手紙を渡せるかを検証した実験です.成功した例はわずかでしたが, その中での平均は6人だったそうです.詳しくはこちらをご覧下さい.

その後,Duncan WattsとSteven Strogatzが このスモールワールド現象について説明した論文を発表しました. 彼らはランダムグラフと正則グラフに着目し,2つの特徴を定式化しました. それは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. DijkstraDijkstraアルゴリズムを紹介します.

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