Rubyで生成したネットワークデータをd3.jsで可視化する

　学術分野としてはやや下火になっている分野ですが、私たちの友人ネットワークがどのように成長していくかをモデル化し、現実のソーシャルネットワークの形成過程を明らかにしようという研究があります。

　一般的に、「友達の友達とは友達になる可能性が高い」や「コミュニティがネットワーク形成に大きく関係している」などと言われていますが、本記事では、「友達の友達とは友達になる可能性が高い」という特性に着目したモデルである、CNN(Connecting Nearest Neighbor)モデルを使ってネットワークデータを作り、そのデータをd3.jsで可視化してみたいと思います。

CNNモデル

　CNN(Connecting Nearest Neighbor)モデルは、「友達の友達は友達」の関係に従ったネットワークモデルで、現実世界に存在するネットワークに共通する性質である「スケールフリー性」、「クラスター性」、「スモールワールド性」を満たすグラフを生成するアルゴリズムの一つとなっています。詳細アルゴリズムは、

(1) パラメータ $u(0 \le u \le 1)$ を設定する。
(2) 各ステップにおいて、以下のアルゴリズムを実行する。

(a) 確率 $u$ でネットワーク中に新しいノード $v_i$ を追加し、すでにネットワーク中に存在するノード $v_j(j \not= i)$ をランダムに選び、ノード $v_i$ との間にリンクを張る。さらに、ノード $v_j$ の隣接ノードすべてに、ノード $v_i$ との潜在的なリンク(ポテンシャルリンク)を設定する。

(b) 確率 $1 - u$ でランダムにポテンシャルリンクを選び、実際のリンクに変換する。