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 |
固定リンク(バラバシ＆アルバートのスケールフリーネットワークシミュレータ（３）)
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
Wed, 30 Nov 2005
JUNG という Java のグラフ理論のためのフレームワークがあります。
可視化だけでなく計算のための機能も豊富。これを使わない手はありません。
というわけで、スモールワールドシミュレータをJUNGを使って書き換えてみました。
まだ距離の平均値しか求めていませんが、ノードはバネでつながっているように
動き、ノードは階数に比例した半径の円で表すことにしています。
Watts Storogatz Simulator JUNG利用 2005/11/30 版 です。
JUNG は内部で
Apache Jakarta commons-collections、
the CERN Colt scientific library、
Xerces を利用しています。
posted at 23:00 |
category: /Math/GraphTheory |
固定リンク(ワッツ＆ストロガッツのスモールワールドシミュレータ（５）
)
Sat, 05 Nov 2005
スモールワールドシミュレータの条件を変えてバラバシ＆アルバートの
スケールフリーネットワークシミュレータを作ってみました。
Barabasi Albert Simulator 2005/11/05 版 です。
- Java Web Start で動きます。
- 頂点の個数は１００個まで計算します。
- m0 で最初に完全グラフを作る頂点の個数を指定します。ボタンを押すと初期状態の完全グラフを作ります。
- 頂点を追加する時につなぐ辺の個数mを指定します。
- ボタンを押すと、反時計回りの点から順に辺を追加していきます。追加するごとに、最大固有値とクラスター度を計算します。
- 次数分布を赤で、固有値の分布を青で表示する。スケールはそれぞれの最大値と最小値で毎回リスケールしている。
- 頂点の個数が１００個に達したら終了します。平均距離を計算します。
増田直紀、今野紀雄著「複雑ネットワークの科学」を参考にしました。
それによると次数分布は理論上はインデックスが-3のベキ分布になるという。
posted at 23:00 |
category: /Math/GraphTheory |
固定リンク(バラバシ＆アルバートのスケールフリーネットワークシミュレータ（２）)
Thu, 03 Nov 2005
隣接行列Aが与えられている時、クラスター度の計算は次のようにする。
Aのn乗の対角成分は、各頂点からnステップ後に元の位置に戻ってくる
パスの場合の数であるから、n=3として右回りと左回りの重複のため
2で割れば、各頂点を含む三角形の個数が求められる。それを利用して、
各頂点から出ているリンクの組の場合の数で割り、各頂点のクラスター生成確率
をもとめ、それを全体で平均を取る。ただし、各頂点から出ているリンクが1本
以下のときは、その頂点のクラスター生成確率は0とした。
（平均に勘定しない方がいいのかな？）
4角形の場合のクラスター度は簡単ではない。なぜなら4ステップで元の位置に戻ってくる
パスとして、abcba や abaca のように途中の点が重複している場合（4角形が
退化している場合）があるからである。一般のn角形の場合を実装しようかと思ったが、
興味があるのはn=3の時がほとんどなので、それで決めうち。
posted at 23:55 |
category: /Math/GraphTheory |
固定リンク(クラスター度の計算
)
クラスター度を計算してみました。また、頂点から出ているリンクの個数の分布を
グラフにプロットしてみました。
Watts Storogatz Simulator 2005/11/03 版 です。
- クラスター度を計算するようにした。
- リンクの個数の分布を赤色でプロットしてみた。
posted at 23:47 |
category: /Math/GraphTheory |
固定リンク(ワッツ＆ストロガッツのスモールワールドシミュレータ（４）)
Sun, 30 Oct 2005
Journal of Social Structure に
Eigen Analysis of Networks
というレビューがありました。これで NEGOPY というソフトウェアの存在を知って探して
みたんだけど、動かなかった・・・・・。
posted at 19:17 |
category: /Math/GraphTheory |
固定リンク(Eigen Analysis of Networks
)