Sun, 25 Dec 2005
ちょっとだけ改造しました。
- 頂点数ははじめから固定（100個）。
- 初期状態はWSのレギュラーグラフ（ただしリンクは向きつきでそれぞれのノードから3本出る）。
- 1ステップごとに、乱数でリンクをひとつ選択して、その終点を別のノードに付け替える。
- 付け替えるノードを選ぶ確率は、そのノードの次数（入ってくるリンクの個数）に比例する。
- ただし自分自身およびすでにリンクのあるノードは除く。
- Java Web Start で動きます。
- initialize ボタンで最初に頂点100個のレギュラーグラフを作る。
- change edge ボタンでリンクの付け替えを50ステップ行う。
- 次数分布は赤で表示する。
Scale Free Simulator 2005/12/25版 です。
今回のポイントはリンクに向きをつけたことです。リンクの付け替えは常に始点を固定して、
終点を変えます。
一回ずつリンクの付け替えをするのはかったるいので、一挙に50回ずつやります。
最初の何回かで少しリンクが集中したノードは、「雪だるま式」にリンクが増えます。
そうなってしまったあとで、リンクが集中していないノードにリンクを増やすのはなかなか
難しそうです。
何回かやっていると次数分布はベキ分布になりそうだが、このシミュレーションでは
シミュレーションの回数を無限に飛ばした時の極限は、
あるひとつのノードにすべてのリンクが集中する状態となるので、
安定性を議論する場合は工夫しないといけません。どうしよう？？？
posted at 22:18 |
category: /Math/GraphTheory |
固定リンク(スケールフリーネットワークシミュレータ（２）)
Sat, 24 Dec 2005
BAシミュレータを少し改造して、以下のようなシミュレーションをしてみることにします。
- 頂点数ははじめから固定。
- 初期状態はWSのレギュラーグラフ。
- 1ステップごとに、乱数でリンクをひとつ選択して、その片方を別のノードに付け替える。
- 付け替えるノードを選ぶ確率は、そのノードの次数に比例する。
- ただし自分自身およびすでにリンクのあるノードは除く。
- Java Web Start で動きます。
- initialize ボタンで最初に頂点100個のレギュラーグラフを作る。
- change edge ボタンでリンクの付け替えを1ステップ行う。
- 次数分布は赤で表示する。
Scale Free Simulator 2005/12/23版 です。
この場合、一度次数が0になったノードは二度とリンクが付くことがありません。
さて、問題は
- シミュレーションを繰り返した時に次数分布は安定するか。
- 安定した場合にその分布はベキ分布になるか。
です。ノードのペアの空間において、リンクがあるかないかの2状態でイジング模型のように
考えることができないだろうか。リンクの付け替えが起こる確率を制御するものとして、
温度のようなものが導入できないだろうか？ネットワークの大域的性質のなかを表す
量の中で、相転移を起こしているものはないだろうか？
posted at 00:07 |
category: /Math/GraphTheory |
固定リンク(スケールフリーネットワークシミュレータ（１）)
Fri, 23 Dec 2005
恥ずかしいことに、大きなミスをしていました。新しい頂点を追加する時の
確率の計算（一番肝心なところ！）が間違っていました。直しました。
次数分布がちゃんとベキ分布になっているはず。
Barabasi Albert Simulator 2005/12/24 JUNG 版 です。
使い方は前と同じです。
- Java Web Start で動きます。
- 頂点の個数は制限なし。
- initialize ボタンで最初に頂点５個の完全グラフを作る。
- Add Vertex ボタンでリンクを３個持つ頂点を追加する。
- 次数分布を赤で表示する。
古いバージョンのものは消します。
posted at 22:28 |
category: /Math/GraphTheory |
固定リンク(バラバシ＆アルバートのスケールフリーネットワークシミュレータ（３）)
高校数学などでよく出てくる問題をシミュレーションするために。
n個の配列をシャッフルして先頭からk個を取り出してもいいんだけど、
無駄が多いかな。1回めはn個の中からひとつ取り出し、2回目はそれを除いた
n-1個の中からひとつ取り出し・・・・ということをk回繰り返してもいいんだけど。
ここで挙げるのは乱数の生成が1回で済む方法。
public int[] generate(int n,int k){
int result[] = new int[k];
double p = Math.random();
int on = k;
int off = n-k;
for(int i=0;i<n;i++){
p *= (on+off);
if(p < on){
result[k-on] = i;
p /= on;
on--;
}else{
p -= on;
p /= off;
off--;
}
}
return result;
}
こんなんでどうでしょう。
posted at 20:15 |
category: /Java/algorithm |
固定リンク(n個の中からk個を取り出す乱数
)
Indoor Laser GPS
というのがあるらしい。要するに、GPSと同じ仕組みで室内での位置計測を行うものらしい。
まあ、それなら G(Global) じゃなくて L(Local) だろうとか突っ込みたくなるが、
従来の磁気によるものや画像処理によるものと比べてどうなのだろうか。
ダウンサイズして GPS 技術の移転による効率性を狙うというのは
間違っていない方向だと思う。
すでにロボットなどにも応用されているみたい。
posted at 13:04 |
category: /VR |
固定リンク(Indoor Laser GPS
)
Mon, 12 Dec 2005
バラバシ＆アルバートの
スケールフリーネットワークシミュレータをJUNGで作り直してみました。
Barabasi Albert Simulator 2005/12/12 JUNG 版 です。
- Java Web Start で動きます。
- 頂点の個数は制限なし。
- initialize ボタンで最初に頂点５個の完全グラフを作る。
- Add Vertex ボタンでリンクを３個持つ頂点を追加する。
- 次数分布を赤で表示する。
とにかく頂点をどんどん追加しよう。次数分布がベキ関数になっていくのがわかる。
posted at 00:22 |
category: /Math/GraphTheory |
固定リンク(バラバシ＆アルバートのスケールフリーネットワークシミュレータ（２）)
Sun, 11 Dec 2005