Aritalab:Lecture/NetworkBiology/Watts-Strogatz Model
From Metabolomics.JP
< Aritalab:Lecture | NetworkBiology(Difference between revisions)
(Draft:Small World moved to Draft:Erdős–Rényi) |
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-Strogatz Model= | ||
+ | 各頂点が<math>k</math>個の隣接点に接続した環状の格子グラフにおいて、確率<math>p</math>で辺を張り直したものをWatts-Strogatzモデルという。 | ||
+ | |||
+ | ==<math>p=0</math>のとき== | ||
+ | ;クラスター係数 | ||
+ | 簡単のため左右の隣接点に同じ本数リンクを張ると仮定し、<math>k = 2i</math>とする。注目する点を原点とした<math>-i \leq x, y < \leq i</math>のxy座標系を考えたとき、<math>|x - y| > i</math>に対応する座標点は三角形<math>K_3</math>を形成せず、残りは形成する。その割合を考えると<math>C(0) = 3/4</math>。 | ||
+ | ;平均頂点間距離 | ||
+ | 1ステップで<math>k/2</math>点スキップでき、環状格子で一番離れている点は<math>n/2</math>なので、<math>L(0) \leq n / k</math>。 | ||
+ | ==<math>p=1</math>のとき== |
Revision as of 11:35, 8 May 2009
Contents |
歴史と参考図書
- Watts DJ, Strogatz SH. "Collective dynamics of 'small-world' networks.". Nature 393 (6684):409–10, 1998. doi:10.1038/30918
Watts-Strogatz Model
各頂点が個の隣接点に接続した環状の格子グラフにおいて、確率で辺を張り直したものをWatts-Strogatzモデルという。
のとき
- クラスター係数
簡単のため左右の隣接点に同じ本数リンクを張ると仮定し、とする。注目する点を原点としたのxy座標系を考えたとき、に対応する座標点は三角形を形成せず、残りは形成する。その割合を考えると。
- 平均頂点間距離
1ステップで点スキップでき、環状格子で一番離れている点はなので、。