読者です 読者をやめる 読者になる 読者になる

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でランダムにポテンシャルリンクを選び、実際のリンクに変換する。

のようになっています。


ネットワークデータの準備

 まず、CNNモデルを使って、ノードとリンクのデータを生成します。パラメータPの値と繰り返し回数については適宜変更してください。ただしこの後、d3.jsで可視化する際の描画負荷を考えると、繰り返しはmaxで500くらいにした方がいいです。

ruby cnn.rb > network.json

を実行すると、CNNモデルによって生成されたネットワークデータのjsonファイルができます。


d3.jsで可視化

 ネットワークを可視化するにはgephiやcytoscapeなどのツールがありますが、今回はd3.jsを使って可視化してみたいと思います。
コードはすごく単純で、d3.jsのサイトにあるサンプルを基にしました。


結果

 パラメータPの違いによって、下図のように、ノード数は多いけど次数(各ノードから出ているリンクの数)は小さいグラフや、ノード数は少ないけど次数が大きいグラフが描けるのではないかと思います。


f:id:hongo35:20130808161602p:plain

 CNNモデルはすごく単純なモデルなので、もっといろいろなモデルを組み合わせたネットワークや、TwitterFacebookなどの実際のネットワークを可視化してみたいなーなんて思ったり(そのときはd3.jsじゃなくてgephiとかじゃないと無理かと...)。