Mon, 29 May 2006
JUNGを使ったシミュレータを使って、バラバシ・アルバートの
スケールフリーシミュレータのクラスタ係数と平均頂点間距離を計算してみた。
ワッツ・ストロガッツのスモールワールドネットワークの結果と比較するために
頂点数と辺の数の合計が同じになるようにシミュレーションを行った。
結果がこのグラフで、赤色の点がスモールワールドネットワークのシミュレーションの
ノードを付け替える確率を変えながら行ったもので、黄色の点がバラバシ・アルバートの
シミュレーションの結果得られたネットワークである。
それぞれ頂点数100、辺の数1000の場合、
頂点数500、辺の数5000の場合、
頂点数600、辺の数12000の場合の
グラフである。
これを見ると、バラバシ・アルバートのスケールフリーネットワークは
クラスタ係数がかなり小さいので、スモールワールドネットワークになっているとは
言いがたいかもしれない。しかし、ワッツ・ストロガッツのモデルの系列の上に
ほぼ乗っているのは偶然だろうか？
もちろんグラフの構造の面では両者は大きく異なる。
（例えばラプラシアンの固有値を見ればワッツ・ストロガッツの一連のネットワークから
バラバシ・アルバートのネットワークが離れたところにあることがわかる）
ワッツ・ストロガッツのモデルは規則的なグラフに少しランダムな要因を
与えたもので、バラバシ・アルバートのモデルはランダムに成長する過程の中に
少しだけ規則性を与えたもの、だと考えると、規則性とランダム性の両方を
うまくバランスよく与えることで、性質のよいネットワークモデルが得られるのかも
しれない。
posted at 23:29 |
category: /ComplexNetwork |
固定リンク(バラバシ・アルバートのスケールフリーネットワークのクラスタ係数
)
Sun, 21 May 2006
JUNGを使ったシミュレータを使って、ワッツとストロガッツが行った数値実験を
追試してみた。ここでは、頂点の個数を500とし、各頂点から20本の辺が出ている
ネットワークで行った。
レギュラーネットワークから辺の付け替えをする確率を少しずつ
変えながら、クラスタ係数Ｃと平均頂点間距離Ｌを計算して
横軸を確率の対数で相対値をプロットしたグラフ。
ほぼ他の書物で触れられているような形が得られた。
posted at 23:18 |
category: /ComplexNetwork |
固定リンク(ワッツとストロガッツのシミュレーションの結果
)
現実の世界において
頂点の個数に比べて、頂点間の平均距離が近い（スモールワールド現象）
を説明するために考えられたモデル。完全グラフだったり、１つの頂点に
すべての頂点からの辺が集中した星型グラフなら平均距離が近いのは当たり前だが、
これは現実世界をうまく表現していない。
現実世界では辺の数（人間関係の場合友人の数）
はそれほど多くなく、局所的には緊密な関係を多く形成している。
そこで、緊密さを定義するクラスタ係数を用いて、
辺の数が少ない時に、クラスタ係数は高いのにもかかわらず、平均頂点間距離が
小さいネットワークをスモールワールドネットワークと言う。
posted at 23:03 |
category: /ComplexNetwork |
固定リンク(スモールワールドネットワーク
)
Sat, 06 May 2006
Pajek
を試してみました。
グラフをレイアウトするための方法がいろいろ実装されているのはよいです。
日本ではタンパク質のネットワークの研究をされている方や社会ネットワークを
研究されている方が使っているみたいです。
扱っているデータは拡張子が NET の
*Vertices 9
1 "1" 0.3034 0.7561
2 "2" 0.4565 0.6039
3 "3" 0.4887 0.8188
4 "4" 0.5687 0.4184
5 "5" 0.3574 0.4180
6 "6" 0.7347 0.2678
7 "7" 0.9589 0.3105
8 "8" 0.8833 0.1269
9 "9" 0.7034 0.0411
*Arcs
*Edges
1 2 1
1 3 1
2 3 1
2 4 1
2 5 1
4 5 1
4 6 1
6 7 1
6 8 1
6 9 1
7 8 1
8 9 1
と言った形式のファイル。これをpajekに読み込ませて使う。できることは
- 頂点をマウスでドラッグして位置変更
- 頂点、辺の大きさ、色、ラベルなどの表示のカスタマイズ
- Random / Erdos-Renyi / Scale-Free Network などの生成
- Path / Flow の計算
- Komada-Kawai Algorythm でのレイアウト
- Fruchterman Reingold でのレイアウト
- グラフの回転アニメーション
- PS / VRML / SVG / BMP 形式の Export
などなど。他にもたくさん。
扱っているグラフの履歴を残してくれているのはとてもよいです。
３Ｄレイアウトして回転させると楽しいです。
参考文献
posted at 13:26 |
category: /ComplexNetwork |
固定リンク(Pajek
)
私は
- ライブラリとして提供されている
- 可視化のための機能が豊富
- Java言語で実装されている
という理由で、JUNG を使っています。
自分でシミュレーションのロジック（乱数や簡単な力学系を使って）
を組みたい時は、可視化ツールではなくて、ライブラリの方が都合がいいんです。
もちろん可視化やシミュレータとしてなら、
単体のアプリケーションもいろいろあるみたいです。
時間ができたらそれぞれレビューもして見たいな。
INSNA
(International Network for Social Network Analysis)
という団体があって、そこで
Computer Programs for Social Network Analysis
をまとめています。
posted at 11:33 |
category: /ComplexNetwork |
固定リンク(ネットワークシミュレータいろいろ
)