『ネットワーク科学の道具箱』＜スケールフリーネットワーク編＞

ネットワーク分析

ネットワーク科学の道具箱―つながりに隠れた現象をひもとく

ネットワーク科学の道具箱―つながりに隠れた現象をひもとく

かおす

ネットワーク分析の入門書。
スケールフリーネットワークの生成とクラスタリングのアルゴリズムについて解説がある。

  1. スケールフリーネットワーク

：再結合あり×要素増減なし

Step1:完全グラフを生成する
Step2:m個のノードをノードiの次数に比例する確率で選択する
Step3:m本のリンクを持つ新たなノードを1つネットワークに追加する。このとき、新たに付け加えられたｍ本のリンクはStep2で選ばれたm個のノードに結ばれる。
Step4:Step2とStep3を繰り返す。t時刻後にはネットワークはN=t+m[0]個のノードから構成される。

→Setp2を見ればわかるように、より大きい次数を持つノードがより高い確率でリンクを得る！＝優先的選択
→Step2がランダム（一様）だと、両対数をとっても直線にのらない。

：再結合なし×要素増減あり

Step1:N個のノードを用意する
Step2:各々のノードiに重みwiを割り当てる。重みの値は確率密度関数からランダムに選ばれる。
Step3:ノードiとノードjに対してwi+wj>=θ（閾値）　であればリンクで結ぶ。これをすべてのノードのペアに対して行う。

確率密度関数を指数分布f(w)=exp[-w]やパレート分布、コーシー分布などにした場合にも指数-2を与えることが知られている。

：再結合あり×要素増減なし
Step1:はじめにN個のノードをランダムにM本のリンクでつないでおく。=2M/N
Step2:それぞれのノードiに適応度βiを適応度分布から割り当てる。
Step3:リンクl[i,j]をランダムに選ぶ。
Step4:ノードmを(k[m]+1)^β[m]確率で選択する。
Step5:リンクl[i,j]とリンクl[i,m]をつなぎかえる。
Step6:Step3からStep5を次数分布に変化がなくなるまで行う。
→Step4でノードmが次数kが大きいほど選ばれやすく成る＝優先的選択！

  1. ネットワーク指標
    1. グラフの表現
      • 隣接リスト（pajekの*Adjust）：配列やハッシュのデータ構造で保持する。
      • 幅優先探索：目的ノードにぶつかるまで子ノードをひたすら展開する探索。探したところが見当違いかつ深すぎて見つかんないorzみたいなことにならず、浅いとこなら確実に見つけられる。but子ノードが多いと爆発する!
  • 幅優先探索の考え方
    • とにかく探す！グラフを木構造に展開する。
    • 戦略として、出発点からの次数が低いとこから同心円状に探していく。
    • あるノードにぶつかったら、そのノードにもっとも早くアクセスできる経路を記録する
    • 経路の記録の戦略として、そのノードにぶつかる時の元のノードをそのノードが保持するキューに（来た順に）記録する。
    • サーチの仕方（同心円上に広げていく方法）から、きた順番は出発点からの経路の次数の低さを示しているからこれでいい。
    • キューの順位が高いとこを逆にたどれば経路になる！！！

→最短経路がわかってうれしい

    • ついでに言うとキューに記録するときに出発点からの次数も一緒に記録しておくと、最短経路が複数あるときに調べやすい。

(defun bfs (node target)

  (do ((queue (list node)

              (append (cdr queue)

                      (get (car queue) 'subnodes)))

       (ls nil (if (get (car queue) target)

                   (cons (car queue) ls)

                   ls)))

      ((null queue) (reverse ls))))