Watts Storogatz Simulator を作ってみました。Java Web Start で起動します。
- ノードの個数(N)は100
- 初期レギュラーネットワークを作るときの、つながっている隣人の距離(k)は1から5までの中から選ぶ
- リセットボタンを押すと、リンクが描かれて（実際はノードの影になって見えない）、全ノード間の平均距離を計算する。
- ノード間のリンクの付替をする確率(p)を入力してランダマイズボタンを押すと、実際にリンクの付替が起こって、全ノード間の平均距離を計算し直す。
リンクの付替をするアルゴリズムは Watts らのやり方とは少し違う（実装上の理由）。ここでは全てのリンクを順に調べて、確率pでリンクをつけかえる。このときリンクの片方のノードは固定して、もう一方のノードを別のノードに付け替える。どちらのノードを固定するか、別のノードをどう選ぶかは、乱数で決める。ランダマイズは何度でも実行できる。リセットボタンをもう一度押すと、レギュラーネットワークに戻る。
距離の計算は孤立ノードが存在すると、距離無限大になってしまうが、リンクの個数の100倍で距離の計算を打ち切っているので、実際はその値になっている。行列計算には
Matrix Toolkits for Java (MTJ) を使った。
- スモールワールド以外のシミュレーションもしたい
- 全ノード間距離以外の指標（スペクトル、PageRank など）も計算したい
- ノードの個数が10000位でも動くように効率化
など、気が向けばやるかも。スペクトルの計算は MTJ についているから実はもうできているんだけど、可視化するのが面倒・・・・・。
posted at 14:00 |
category: /Math/GraphTheory |
固定リンク(ワッツ＆ストロガッツのスモールワールドシミュレータ)
グラフ理論の復習。
無向重みなしグラフ（隣接行列が対称で、成分が0または1）を考える。
隣接行列 A の (i,j) 成分は i 番目の頂点から j 番目の頂点への辺があるか
ないかを表している。このとき、行列 A の n 乗の (i,j) 成分は
i 番目の頂点から j 番目の頂点へ n ステップで到達することのできる
場合の数を表している。
これを利用して、A の n 乗の (i,j) 成分がはじめて 0 でない数になる
n を求めると、i 番目の頂点から j 番目の頂点への距離となる。
普通距離はこの様にして計算されるが、有限の距離を持つかの判定が
この方法でできるわけではないので、適当なところで打ち切る
必要がある。その意味で正確な計算方法ではないが、他のよい方法は
知らない。
posted at 09:00 |
category: /Math/GraphTheory |
固定リンク(頂点の間の距離)