Aritalab:Lecture/NetworkBiology/Watts-Strogatz Model
From Metabolomics.JP
< Aritalab:Lecture | NetworkBiology(Difference between revisions)
m |
m |
||
| Line 1: | Line 1: | ||
=歴史と参考図書= | =歴史と参考図書= | ||
* Watts DJ, Strogatz SH. "Collective dynamics of 'small-world' networks.". Nature 393 (6684):409–10, 1998. [http://www.ncbi.nlm.nih.gov/sites/entrez?db=pubmed&uid=9623998&cmd=showdetailview&indexed=google doi:10.1038/30918] | * Watts DJ, Strogatz SH. "Collective dynamics of 'small-world' networks.". Nature 393 (6684):409–10, 1998. [http://www.ncbi.nlm.nih.gov/sites/entrez?db=pubmed&uid=9623998&cmd=showdetailview&indexed=google doi:10.1038/30918] | ||
| + | * Durrett R. "Random Graph Dynamics" Cambridge University Press, 2004. | ||
=Watts-Strogatz Model= | =Watts-Strogatz Model= | ||
| Line 18: | Line 19: | ||
==一般の場合== | ==一般の場合== | ||
| + | ;平均頂点間距離 | ||
| + | 導出は面倒だが以下の近似が知られている。<math>\textstyle L(p)=\frac{n}{k}\frac{\log(2 pkn)}{4 pkn}</math> | ||
| + | |||
| + | ;クラスター係数 | ||
| + | 簡単な近似では、<math>K_3</math>をなす3頂点間の辺が張りなおしを防げばよいので | ||
| + | <math>L(p) = L(0)(1-p)^3</math>。 | ||
Revision as of 12:53, 8 May 2009
Contents |
歴史と参考図書
- Watts DJ, Strogatz SH. "Collective dynamics of 'small-world' networks.". Nature 393 (6684):409–10, 1998. doi:10.1038/30918
- Durrett R. "Random Graph Dynamics" Cambridge University Press, 2004.
Watts-Strogatz Model
各頂点が
個の隣接点に接続した環状の格子グラフにおいて（総辺数は
）、確率
で辺を張り直したものをWatts-Strogatzモデルという。辺を張りなおすモデルは解析が難しいので、環状の格子グラフにポアソン過程として
本の辺を追加するモデルがよく使われる。
のとき
- クラスター係数
簡単のため左右の隣接点に同じ本数リンクを張ると仮定し、
とする。注目する点を原点とした
のxy座標系を考えたとき、
に対応する座標点は三角形
を形成せず、残りは形成する。その割合を考えると
。
- 平均頂点間距離
1ステップで
点スキップでき、環状格子で一番離れている点は
なので、
。
のとき
ランダムグラフと思えばよい。
- クラスター係数
辺を張りかえるとき、
頂点の中から隣接点を選べばよいので
。
- 平均頂点間距離
辺をランダムに張りかえるので
。
一般の場合
- 平均頂点間距離
導出は面倒だが以下の近似が知られている。
- クラスター係数
簡単な近似では、をなす3頂点間の辺が張りなおしを防げばよいので
。
