Aritalab:Lecture/NetworkBiology/Erdos-Renyi Model - Revision history

Adm: /* ネットワークの進化 */

2017-08-03T02:13:52Z

‎ネットワークの進化

Adm: /* ネットワークの進化 */

2017-08-03T01:10:47Z

‎ネットワークの進化

Adm at 00:01, 2 August 2017

2017-08-02T00:01:48Z

Adm at 23:46, 1 August 2017

2017-08-01T23:46:24Z

Adm at 02:36, 6 August 2016

2016-08-06T02:36:07Z

Adm: /* Erdős–Rényiグラフ */

2016-08-06T02:34:52Z

‎Erdős–Rényiグラフ

Adm: /* 木、格子 */

2016-08-06T02:18:30Z

‎木、格子

Adm: /* 木、格子 */

2016-08-06T01:59:25Z

‎木、格子

Adm: /* 平均頂点間距離 */

2016-08-06T01:54:00Z

‎平均頂点間距離

Adm: /* クラスター係数 */

2016-08-06T01:51:26Z

‎クラスター係数

@@ Line 62: / Line 62: @@
 * ''c'' = log ''n''
 全体が連結になります。ある頂点が辺を全く持たない確率を考えると
-(1 - ''p'')<sup>''n'' - 1</sup> = { ( 1 - c /(''n'' - 1))<sup>(''n'' - 1)/c</sup> }<sup>''c''</sup> <= ''e''<sup>-''c''</sup>。したがって、そのような頂点がグラフ中にi一つでも存在してしまう確率の上限は ''ne''<sup>-''c''</sup> となります。これを 0 に収束させるには例えば ''c'' >= 2 log ''n'' で十分です。このとき孤立点は消滅しています。
+(1 - ''p'')<sup>''n'' - 1</sup> = { ( 1 - c /(''n'' - 1))<sup>(''n'' - 1)/c</sup> }<sup>''c''</sup> <= ''e''<sup>-''c''</sup>。したがって、そのような頂点がグラフ中に存在してしまう確率の上限は ''ne''<sup>-''c''</sup> となります。これを 0 に収束させるには例えば ''c'' >= 2 log ''n'' で十分です。このとき孤立点は消滅しています。
 ;相転移
 上でみたように、次数の平均値が 1 をこえると急に連結成分のサイズが大きくなり、 log ''n'' に達すると全体が連結になります。
 こうした点を、相転移点と呼びます。

@@ Line 62: / Line 62: @@
 * ''c'' = log ''n''
 全体が連結になります。ある頂点が辺を全く持たない確率を考えると
-(1 - ''p'')<sup>''n'' - 1</sup> = { ( 1 - c /(''n'' - 1))<sup>(''n'' - 1)/c</sup> }<sup>''c''</sup> <= ''e''<sup>-''c''</sup>。したがって、そのような頂点がグラフ中に全く存在しない場合の上限は ''ne''<sup>-''c''</sup> となります。これを 0 に収束させるには例えば ''c'' >= 2 log ''n'' で十分です。このとき孤立点は消滅しています。
+(1 - ''p'')<sup>''n'' - 1</sup> = { ( 1 - c /(''n'' - 1))<sup>(''n'' - 1)/c</sup> }<sup>''c''</sup> <= ''e''<sup>-''c''</sup>。したがって、そのような頂点がグラフ中にi一つでも存在してしまう確率の上限は ''ne''<sup>-''c''</sup> となります。これを 0 に収束させるには例えば ''c'' >= 2 log ''n'' で十分です。このとき孤立点は消滅しています。
 ;相転移
 上でみたように、次数の平均値が 1 をこえると急に連結成分のサイズが大きくなり、 log ''n'' に達すると全体が連結になります。
 こうした点を、相転移点と呼びます。

← Older revision		Revision as of 00:01, 2 August 2017
Line 1:		Line 1:
−	~~{{Lecture/Header}}~~
	__TOC__		__TOC__

@@ Line 1: / Line 1: @@
 {{Lecture/Header}}
-{| style="float:right"
+==学習事項==
-| __TOC__
+* Erdős–Rényiグラフは、無向のランダムグラフ、頂点の次数分布は二項分布になる。
-|}
+* ポアソン分布による近似とその必要性。
 ==歴史と参考図書==

← Older revision		Revision as of 02:36, 6 August 2016
Line 68:		Line 68:
	上でみたように、次数の平均値が 1 をこえると急に連結成分のサイズが大きくなり、 log ''n'' に達すると全体が連結になります。		上でみたように、次数の平均値が 1 をこえると急に連結成分のサイズが大きくなり、 log ''n'' に達すると全体が連結になります。
	こうした点を、相転移点と呼びます。		こうした点を、相転移点と呼びます。
−
−
−	~~==ネットワークの指標==~~
−	~~ネットワーク全体についての尺度として、クラスター係数 ''C'' と平均頂点間距離 ''L'' を紹介します。~~
−
−	~~===クラスター係数===~~
−
−	クラスター係数は隣接する頂点間の辺の密度の平均値にあたります。まず各頂点 ''i'' におけるクラスター係数 <math>C_i</math> を以下のように定義します。辺の長さはすべて 1 とし <math>(\|e\| = 1)</math>、頂点 ''i'' の次数を ''deg'' (''i'' ), 隣接する頂点群を ''adj'' (''i'' ) とします。
−
−	~~:<math>\textstyle C_i=\frac{2}{deg(i)(deg(i)-1)} \sum_{j,k \in adj(i)} \|e_{jk}\|</math>~~
−
−	~~グラフ全体のクラスター係数はその平均値です。~~
−
−	~~:<math>\textstyle C =\frac{1}{n} \sum^{n}_{i=1}C_i</math>~~
−
−	~~クラスター係数が 0.2 や 0.3 になるネットワークは、比較的「密」といえます。~~
−
−	~~===平均頂点間距離===~~
−	ここでは頂点 ''i, j'' 間の最短経路を <math>p_{ij}</math> と書きます。平均頂点間距離の定義はその字のごとく全頂点間の最短路の平均値です。ネットワーク ''G'' の頂点数を ''n'' とすると頂点の組み合わせの数が ''n'' (''n'' - 1) / 2 あるので
−
−	~~:<math>\textstyle L=\frac{2}{n(n-1)} \sum_{i,j\in G}\|p_{ij}\|</math>~~
−
−	~~となります。~~
−
−	上の定義だと、例えば無限の広がりを持つ場合の平均距離を求められません (無限個の最短路を計算しなくてはならない)。そういう場合は、ネットワーク上のある点に注目して ''L'' を計算する場合があります。その点から距離 ''L'' 以内にある頂点数を数える手法です。
−
−	~~==様々なグラフにおける指標の値 ==~~
−
−	~~===完全グラフ===~~
−	~~全ての頂点間に辺を持つグラフを、完全グラフ (complete graph) といいます。完全グラフでは、 ''C'' = ''L'' = 1 になります。~~
−
−	~~===木、格子===~~
−	簡単のため全頂点が同じ次数を持つ木を考えましょう。中心の頂点 ''v''<sub>0</sub> を根 (root) と呼びます。木はその定義よりサイクルを持たないので ''C'' = 0 です。また平均頂点間距離は、距離 ''L'' 以内にある頂点を数えることで求められます。
−
−	~~<math>~~
−	~~\begin{align}~~
−	~~n &= 1 + d + d(d-1) + ... + d(d-1)^L \\~~
−	~~&=\textstyle 1 +\frac{d (1-(d-1)^{L+1})}{(1-(d-1))} = 1 + \frac{d}{d-2}((d-1)^{L+1} -1) \\~~
−	~~&\propto (d-1)^{L+1}~~
−	~~\end{align}~~
−	~~</math>~~
−
−	~~この関係から（大雑把ですが） <math>\textstyle L=\propto \frac{\log n}{\log (d-1)}</math> となります。~~
−
−	格子状のネットワークでは頂点が一定間隔で配置されるため、道路網のような地理的制約をうけるつながりを表現するのに適しています。平面の場合は三角格子、正方格子、六方格子などが考えられます。ただし、クラスター係数を定義のまま適用すると、三角格子以外は隣接頂点どうしがつながらないために常に ''C'' = 0 になります。これでは面白くないので、格子の場合は最短距離が <math>a</math> 以下の点には全て辺を張るバリエーションを考えるのが一般的です。ここでは、''d'' 次元空間において辺の長さが単位距離の格子を '''Z'''<sup>d</sup> と書きましょう。 ( '''Z'''<sup>d</sup> において ''deg''( ''i'' ) = 2 ''d'' )
−
−	;'''Z'''<sup>1</sup> : いわゆる数直線です。ある頂点から ''k'' の距離内にある頂点は、その数 ''n'' = ''2k'' + 1 です。これらの頂点の平均距離は ''L'' = ''k'' になります。したがって ''L'' &sim; ''n''/2 です。
−
−	;'''Z'''<sup>2</sup> : 二次元の格子として、正方格子を考えます。ある頂点から ''k'' の距離内にある頂点の数は ''n'' = ''k''<sup>2</sup> + ( ''k'' + 1)<sup>2</sup> です。これらの頂点の平均距離は ''L'' = ''k'' / 2 です。''n'' の式を ''k'' について解くと <math>\textstyle k = \frac{\sqrt{(2n -1)} - 1}{2} \sim \frac{\sqrt{2n}}{2} </math> となるため <math>\textstyle L \sim \frac{\sqrt{2n}}{4}</math> です。
−
−	~~<!---~~
−	~~:例. '''Z''''<sup>d</sup>のクラスター係数は<math>\textstyle C=\frac{3(a-1)}{2(2a-1)}</math>、平均頂点間距離は<math>\textstyle L=\sqrt[d]{n}/a</math>~~
−	~~--->~~
−
−	~~===Erdős–Rényiグラフ===~~
−
−	~~各頂点が持つ辺の期待値（定数）を c とします。これは c = n p を満たします。~~
−
−	~~クラスター係数 ... 辺が張られる確率は全て独立なので p です。n が大きくなると 0 に近づきます。~~
−
−	平均頂点間距離 ... 各頂点が持つ辺の期待値を c とします。次数 c の木構造 L ステップでグラフ全体がカバーできると考えます。 c<sup>L</sup> = n から、L = log n / log c になります。
−
−	~~連結性 ... ERグラフ全体が連結であるためには、グラフ進化の考察から次数は O(log n) 以上必要です。~~

@@ Line 124: / Line 124: @@
 ===Erdős–Rényiグラフ===
-クラスター係数 ... 辺が張られる確率は全て独立なので ''C'' ( ''p'' ) = ''p'' &sim; ''c'' / ''n'' です。これは、完全グラフをほとんど含まないことを意味しています。
+各頂点が持つ辺の期待値（定数）を c とします。これは c = n p を満たします。
-平均頂点間距離 ... 各頂点が持つ辺の期待値を ''c'' = ( ''n'' -1) ''p'' とします。
+クラスター係数 ... 辺が張られる確率は全て独立なので p です。n が大きくなると 0 に近づきます。
-: ''L''( ''p'' ) >= log ''n'' / log ''c'' = ''O''(log ''n'' )
-連結性 ... ERグラフ全体が連結であるためには、次数が ''O''(log ''n'' ) 以上必要です。
+平均頂点間距離 ... 各頂点が持つ辺の期待値を c とします。次数 c の木構造 L ステップでグラフ全体がカバーできると考えます。 c<sup>L</sup> = n から、L = log n / log c になります。

@@ Line 114: / Line 114: @@
 格子状のネットワークでは頂点が一定間隔で配置されるため、道路網のような地理的制約をうけるつながりを表現するのに適しています。平面の場合は三角格子、正方格子、六方格子などが考えられます。ただし、クラスター係数を定義のまま適用すると、三角格子以外は隣接頂点どうしがつながらないために常に ''C'' = 0 になります。これでは面白くないので、格子の場合は最短距離が <math>a</math> 以下の点には全て辺を張るバリエーションを考えるのが一般的です。ここでは、''d'' 次元空間において辺の長さが単位距離の格子を '''Z'''<sup>d</sup> と書きましょう。 ( '''Z'''<sup>d</sup> において ''deg''( ''i'' ) = 2 ''d'' )
-;'''Z'''<sup>1</sup> : いわゆる数直線です。ある頂点から ''k'' の距離内にある頂点数 ''n'' = ''2k'' + 1 で、これらの頂点への距離の平均値は ''L'' = ''k'' になります。したがって ''L'' &sim; ''n''/2 です。
+;'''Z'''<sup>1</sup> : いわゆる数直線です。ある頂点から ''k'' の距離内にある頂点は、その数 ''n'' = ''2k'' + 1 です。これらの頂点の平均距離は ''L'' = ''k'' になります。したがって ''L'' &sim; ''n''/2 です。
-;'''Z'''<sup>2</sup> : 二次元の格子として、正方格子を考えます。ある頂点から ''k'' の距離内にある頂点数は ''n'' = ''k''<sup>2</sup> + ( ''k'' + 1)<sup>2</sup>
+;'''Z'''<sup>2</sup> : 二次元の格子として、正方格子を考えます。ある頂点から ''k'' の距離内にある頂点の数は ''n'' = ''k''<sup>2</sup> + ( ''k'' + 1)<sup>2</sup> です。これらの頂点の平均距離は ''L'' = ''k'' / 2 です。''n'' の式を ''k'' について解くと <math>\textstyle k = \frac{\sqrt{(2n -1)} - 1}{2} \sim \frac{\sqrt{2n}}{2} </math> となるため <math>\textstyle L \sim \frac{\sqrt{2n}}{4}</math> です。
-で与えられ、これらの頂点への距離の平均値が
 ''L'' = ''k'' / 2
 です。''n'' の式を ''k'' について解くと
-''k'' = {(2 ''n'' -1)<sup>1/2</sup> - 1} &sim; (2 ''n'')<sup>1/2</sup>
-となるため
-''L'' &sim; (''n'' / 2) <sup>1/2</sup>
 です。
 <!---

@@ Line 105: / Line 105: @@
 \begin{align}
 n &= 1 + d + d(d-1) + ... + d(d-1)^L \\
-&= 1 +\frac{d (1-(d-1)^{L+1})}{(1-(d-1))} = 1 + \frac{d}{d-2}((d-1)^{L+1} -1) \\
+&=\textstyle 1 +\frac{d (1-(d-1)^{L+1})}{(1-(d-1))} = 1 + \frac{d}{d-2}((d-1)^{L+1} -1) \\
 &\propto (d-1)^{L+1}
 \end{align}
 </math>
-この関係から（大雑把ですが） <math>\textstyle L=\propto \frac{\log n}{\log (d-1)} \propto \log n</math> となります。
+この関係から（大雑把ですが） <math>\textstyle L=\propto \frac{\log n}{\log (d-1)}</math> となります。
 格子状のネットワークでは頂点が一定間隔で配置されるため、道路網のような地理的制約をうけるつながりを表現するのに適しています。平面の場合は三角格子、正方格子、六方格子などが考えられます。ただし、クラスター係数を定義のまま適用すると、三角格子以外は隣接頂点どうしがつながらないために常に ''C'' = 0 になります。これでは面白くないので、格子の場合は最短距離が <math>a</math> 以下の点には全て辺を張るバリエーションを考えるのが一般的です。ここでは、''d'' 次元空間において辺の長さが単位距離の格子を '''Z'''<sup>d</sup> と書きましょう。 ( '''Z'''<sup>d</sup> において ''deg''( ''i'' ) = 2 ''d'' )

@@ Line 92: / Line 92: @@
 となります。
-上の定義だと、例えば無限の広がりを持つ数直線の ''L'' を求められません (無限個の最短路を計算しなくてはならない)。そういう場合は、ネットワーク上のある点に注目して ''L'' を計算できます。その点から距離 ''L'' 以内にある頂点数を数えることで ''L'' の値を求められます。（これから実例をみていきます。）
+上の定義だと、例えば無限の広がりを持つ場合の平均距離を求められません (無限個の最短路を計算しなくてはならない)。そういう場合は、ネットワーク上のある点に注目して ''L'' を計算する場合があります。その点から距離 ''L'' 以内にある頂点数を数える手法です。
 ==様々なグラフにおける指標の値 ==

@@ Line 83: / Line 83: @@
 :<math>\textstyle C =\frac{1}{n} \sum^{n}_{i=1}C_i</math>
-クラスター係数が 0.2 や 0.3 になるネットワークは、比較的「密」だといえます。（これから実例をみていきます。）
+クラスター係数が 0.2 や 0.3 になるネットワークは、比較的「密」といえます。
 ===平均頂点間距離===