| Sun | Mon | Tue | Wed | Thu | Fri | Sat |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 21 | 22 | 23 | 24 | 25 | 26 | 27 |
| 28 | 29 | 30 | 31 |
Copyright © 1998-2006 TOKUNAGA Ken-ichi iam[at mark]tokunagakenichi[dot]net
あなたはこのサイトの11011111001101110111人目の訪問者です(ただし2進数)。
JUNG に PageRank を計算するクラスがついている。それによると、 推移確率行列と定数行列（すべての成分が定数＝1/頂点数）を内分した行列 の最大固有値の固有ベクトルを求めているみたい。すべての成分が定数の行列と いうのは、マルコフ過程の推移確率行列だと思うと、 すべての頂点に同確率で移りうるということだから、 辺をたどらずに別の頂点にジャンプする場合を考慮したものといえる。
(1-alpha)*推移確率行列+alpha*定数行列という形で、 alpha の値は0.1から0.2までぐらいが適当。
こうすると、
JUNGを使ったシミュレータを使って、バラバシ・アルバートの スケールフリーシミュレータのクラスタ係数と平均頂点間距離を計算してみた。 ワッツ・ストロガッツのスモールワールドネットワークの結果と比較するために 頂点数と辺の数の合計が同じになるようにシミュレーションを行った。
結果がこのグラフで、赤色の点がスモールワールドネットワークのシミュレーションの ノードを付け替える確率を変えながら行ったもので、黄色の点がバラバシ・アルバートの シミュレーションの結果得られたネットワークである。 それぞれ頂点数100、辺の数1000の場合、 頂点数500、辺の数5000の場合、 頂点数600、辺の数12000の場合の グラフである。
これを見ると、バラバシ・アルバートのスケールフリーネットワークは クラスタ係数がかなり小さいので、スモールワールドネットワークになっているとは 言いがたいかもしれない。しかし、ワッツ・ストロガッツのモデルの系列の上に ほぼ乗っているのは偶然だろうか？ もちろんグラフの構造の面では両者は大きく異なる。 （例えばラプラシアンの固有値を見ればワッツ・ストロガッツの一連のネットワークから バラバシ・アルバートのネットワークが離れたところにあることがわかる）
ワッツ・ストロガッツのモデルは規則的なグラフに少しランダムな要因を 与えたもので、バラバシ・アルバートのモデルはランダムに成長する過程の中に 少しだけ規則性を与えたもの、だと考えると、規則性とランダム性の両方を うまくバランスよく与えることで、性質のよいネットワークモデルが得られるのかも しれない。
JUNGを使ったシミュレータを使って、ワッツとストロガッツが行った数値実験を 追試してみた。ここでは、頂点の個数を500とし、各頂点から20本の辺が出ている ネットワークで行った。
現実の世界において 頂点の個数に比べて、頂点間の平均距離が近い（スモールワールド現象） を説明するために考えられたモデル。完全グラフだったり、１つの頂点に すべての頂点からの辺が集中した星型グラフなら平均距離が近いのは当たり前だが、 これは現実世界をうまく表現していない。
現実世界では辺の数（人間関係の場合友人の数） はそれほど多くなく、局所的には緊密な関係を多く形成している。 そこで、緊密さを定義するクラスタ係数を用いて、 辺の数が少ない時に、クラスタ係数は高いのにもかかわらず、平均頂点間距離が 小さいネットワークをスモールワールドネットワークと言う。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に読み込ませて使う。できることは
私は
という理由で、JUNG を使っています。
自分でシミュレーションのロジック（乱数や簡単な力学系を使って）
を組みたい時は、可視化ツールではなくて、ライブラリの方が都合がいいんです。
もちろん可視化やシミュレータとしてなら、
単体のアプリケーションもいろいろあるみたいです。
時間ができたらそれぞれレビューもして見たいな。
INSNA (International Network for Social Network Analysis) という団体があって、そこで Computer Programs for Social Network Analysis をまとめています。
スモールワールドネットワーク、スケールフリーネットワークなどに代表される近年話題の複雑ネットワークに関する情報、読書記録、アイディア、自作プログラムなどについてまとめておこうと思います。
厳密な複雑ネットワークの定義があるというわけではなく、インターネット、人間関係、ニューラルネット、たんぱく質の化学反応系などの、「複雑な」ネットワークについての総称であると考えたらよさそうだ。
ネットワークを分析する手段として、多くの場合、いわゆる数学で言うところのグラフ理論で扱う「グラフ」（ノード、頂点、点などと呼ばれるものを、辺、エッジ、リンクなどと呼ばれるもので結んだ関係を表す）を用いる。
グラフ理論の応用として通常考えられるのは、ネットワーク構造がすでに与えられているものとして、最短経路問題や彩色問題などグラフの上での定義された問題を解くことに重点を置かれているのに対し、複雑ネットワークの立場では、平均ノード間距離や、次数分布などネットワーク構造そのものの性質、またある性質を持つネットワークがどのように作られるかという生成過程に重点が置かれているようだ。
スケールフリーネットワークとは、次数分布がベキ則に従うものをいう。
次数分布とは、それぞれのノードに対していくつのリンクがでているか（次数） を調べて、次数kを持つようなノードの個数の（相対）度数分布p(k)のことである。 それがベキ関数に比例
p(k) ∝ k-γ
するときにベキ則に従う、という。