Aritalab:Lecture/NetworkBiology/Erdos-Renyi Model

From Metabolomics.JP
< Aritalab:Lecture | NetworkBiology(Difference between revisions)
Jump to: navigation, search
m (→‎格子)
m
Line 1: Line 1:
 
{{Lecture/Header}}
 
{{Lecture/Header}}
  
−
ここでは頂点がすべて連結した無向グラフを扱う。
+
ここでは頂点がすべて連結した無向グラフを扱います。
  
 
==歴史と参考図書==
 
==歴史と参考図書==
Line 10: Line 10:
  
 
==ネットワークの指標:<math>C</math>と<math>L</math>==
 
==ネットワークの指標:<math>C</math>と<math>L</math>==
−
ネットワーク全体についての尺度として、クラスター係数<math>C</math>と平均頂点間距離<math>L</math>を紹介する。
+
ネットワーク全体についての尺度として、クラスター係数 ''C'' と平均頂点間距離 ''L'' を紹介します。
  
−
===クラスター係数===
+
==クラスター係数==
−
クラスター係数は隣接する頂点間の辺の密度の平均値にあたる。
+
クラスター係数は隣接する頂点間の辺の密度の平均値にあたります。
−
まず各頂点 ''i'' におけるクラスター係数 <math>C_i</math> を以下のように定義する。
+
まず各頂点 ''i'' におけるクラスター係数 <math>C_i</math> を以下のように定義します。
−
辺の長さはすべて1とし <math>|e|=1</math>、頂点 ''i'' の次数を ''deg''(''i''), 隣接する頂点群を ''adj''(''i'') と書く。
+
 
 +
:辺の長さはすべて 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_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>
 
:<math>\textstyle C =\frac{1}{n} \sum^{n}_{i=1}C_i</math>
  
−
===平均頂点間距離===
+
クラスター係数が 0.2 や 0.3 になるネットワークは、比較的「密」だといえます。（これから実例をみていきます。）
−
平均頂点間距離はその字のごとく全頂点間の最短路の平均値にあたる。ここでは頂点<math>i, j</math>間の最短経路を<math>p_{ij}</math>と書く。各点に注目する場合は、距離<math>L</math>以内にある頂点数を数えることで求められる。
+
−
:<math>\textstyle L=\frac{1}{n} \sum_{i,j\in G}|p_{ij}|</math>
+
  
−
===様々なグラフにおける<math>C</math>と<math>L</math>===
+
==平均頂点間距離==
−
====完全グラフ====
+
ここでは頂点 ''i, j'' 間の最短経路を <math>p_{ij}</math> と書きます。平均頂点間距離の定義はその字のごとく全頂点間の最短路の平均値です。ネットワーク ''G'' の頂点数を ''n'' とすると頂点の組み合わせの数が ''n'' (''n'' - 1) / 2 あるので
−
全ての頂点間に辺を持つグラフは<math>C=L=1</math>。
+
  
−
====格子====
+
:<math>\textstyle L=\frac{2}{n(n-1)} \sum_{i,j\in G}|p_{ij}|</math>
−
格子状のネットワークでは頂点が一定間隔で配置されるため、道路網のような地理的制約をうけるつながりを表現するのに適しています。
+
 
−
平面の場合は三角格子、正方格子、六方格子などが考えられます。
+
となります。
 +
 
 +
上の定義だと、例えば無限の広がりを持つ数直線の ''L'' を求められません (無限個の最短路を計算しなくてはならない)。そういう場合は、ネットワーク上のある点に注目して ''L'' を計算できます。その点から距離 ''L'' 以内にある頂点数を数えることで ''L'' の値を求められます。（これから実例をみていきます。）
 +
 
 +
==様々なグラフにおける ''C'' と ''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 \\
 +
&= 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> となります。
 +
 
 +
===格子===
 +
格子状のネットワークでは頂点が一定間隔で配置されるため、道路網のような地理的制約をうけるつながりを表現するのに適しています。平面の場合は三角格子、正方格子、六方格子などが考えられます。ただし、クラスター係数を定義のまま適用すると、三角格子以外は隣接頂点どうしがつながらないために常に ''C'' = 0 になります。これでは面白くないので、格子の場合は最短距離が <math>a</math> 以下の点には全て辺を張るバリエーションを考えるのが一般的です。
  
 
ここでは、''d'' 次元空間において辺の長さが単位距離の格子を '''Z'''<sup>d</sup> と書きましょう。
 
ここでは、''d'' 次元空間において辺の長さが単位距離の格子を '''Z'''<sup>d</sup> と書きましょう。
−
:'''Z'''<sup>d</sup> において <math>deg(i) = 2d</math>
+
:'''Z'''<sup>d</sup> において ''deg''( ''i'' ) = 2 ''d''
  
−
クラスター係数を定義のまま適用すると、正方格子や六方格子は隣接頂点どうしがつながらないために常に0になります。これでは面白くないので、最短距離が <math>a</math> 以下の点には全て辺を張るバリエーションを考えてみましょう。
+
===='''Z'''<sup>1</sup>====
 +
一次元の格子とは、いわゆる数直線です。ある頂点から ''k'' の距離内にある頂点数 ''n'' = ''k'' + 1 で、これらの頂点への距離の平均値は ''L'' = ''k''/2 になります。したがって ''L'' &sim; ''n''/2 です。
 +
 
 +
===='''Z'''<sup>2</sup>====
 +
二次元の格子として、正方格子を考えます。ある頂点から ''k'' の距離内にある頂点数は
 +
''n'' = ''k''<sup>2</sup> + ( ''k'' + 1)<sup>2</sup>
 +
で与えられ、これらの頂点への距離の平均値が
 +
''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 44: Line 77:
 
--->
 
--->
  
−
====木====
 
−
簡単のため全頂点が同じ次数を持つ木を考える。中心の頂点<math>v_0</math>を根(root)と呼ぶ。木はその定義よりサイクルを持たないので<math>C=0</math>。また平均頂点間距離は、距離L以内にある頂点を数えることで求められる。
 
−
:<math>n = 1 + d + d(d-1) + ... + d(d-1)^L = 1 +d (1-(d-1)^{L+1})/(1-(d-1))</math>∝<math>(d-1)^{L+1}</math>
 
−
すなわち
 
−
:<math>\textstyle L=\propto \frac{\log n}{\log (d-1)} \propto \log n</math>
 
  
 
==Erdős–Rényiグラフ==
 
==Erdős–Rényiグラフ==
−
全ての頂点間に一定の確率<math>p</math>で独立に辺を作成してできるランダムグラフをErdős–Rényiグラフと呼ぶ。各頂点に注目してみると<math>n-1</math>点に対して確率<math>p</math>で辺を張るため、次数は二項分布
 
  
−
<math>{}_{n-1}\mbox{C}_k p^k(1-p)^{n-1-k}</math>
+
全ての頂点間に一定の確率 ''p'' で独立に辺を作成してできるランダムグラフをErdős–Rényiグラフと呼びます。各頂点に注目してみると　''n'' -1 点に対して確率 ''p'' で辺を張るため、その次数は二項分布
  
−
に従う。すなわち次数の平均は<math>c = (n-1)p</math>と書ける。
+
<sub>''n'' -1</sub><big>C</big><sub>k</sub> ''p'' <sup>''k''</sup> (1- ''p'') <sup>(''n'' -1) - ''k''</sup>
 +
 
 +
に従います。すなわち次数の平均は ( ''n'' -1) ''p'' となり、これを ''c'' と書きましょう。
  
 
===ネットワークの進化===
 
===ネットワークの進化===
−
次数の平均値<math>c</math>を変化させて生じるグラフ形状の違いを検証しよう。
+
次数の平均値 ''c'' を変化させて生じるグラフ形状の違いを検証します。
−
;<math>\textstyle c \le \frac{1}{n^2} </math>
+
−
辺の生成される確率が<math>pn(n-1)/2 = cn/2 \xrightarrow{n\rarr \infty} 0</math>になるため、辺を持たない。
+
  
−
;<math>\textstyle c = 1/\sqrt{n}</math>
+
;''c'' << 1 / ''n''<sup>2</sup> のとき
−
辺があったとしても木にしかならない。
+
  
−
;<math>\textstyle c = const.</math>
+
生成される辺数の期待値は ''pn'' (''n'' -1) / 2 = ''cn''/ 2 になります。''n'' を無限大にしたとき、この値が 0 に近づくのでネットワークのサイズに対してほとんど辺を持たないことになります。
−
各頂点が定数本の辺を持ちはじめる。
+
−
*ちょうど<math>c=1</math>だと二部グラフのマッチング、<math>c=2</math>だと閉路の集合になる。
+
−
*各頂点が持つ辺の本数（の期待値）が<math>c</math>なので、<math>c < 1</math>のとき連結部分の大きさは高々<math>\log n</math>程度にしかならない。しかし<math>c > 1</math>の場合繋がっていく確率のほうが高く、その半径(diameter)を<math>k</math>とおくと<math>c^k=n</math>まで成長できる。このとき<math>k=\log n / \log c</math>。
+
−
*詳細な解析によると、臨界点にあたる<math>c = 1</math>では連結部分のサイズが<math>O(n^{2/3})</math>になることが知られている。
+
  
−
;<math>\textstyle c = \log n</math>
+
;''c'' = 1 / ''n'' のとき
−
全体が連結になる。ある頂点が辺を全く持たない確率は<math>\textstyle (1-p)^{n-1}=((1-\frac{c}{n-1})^{\frac{n-1}{c}})^{c} \leq e^{-c}</math>。したがって、そのような頂点がグラフ中に存在しない確率の上限は<math>ne^{-c}</math>となる。これを0に収束させるには例えば<math>c \geq 2 \log n</math>で十分である。このとき孤立点が消滅する。
+
上と同じ理由で、ネットワーク全体で辺が定数本だけ作られるネットワークになります。ほとんどの辺がばらばらに存在します。
  
−
===辺の数を固定するモデル===
+
;''c'' = const.
−
辺の数を正確に<math>N</math>本とする場合を考えよう。<math>n</math>頂点からランダムに2つを選び、その間に辺を作成するプロセスを正確に<math>N</math>回繰り返す。(ランダムに頂点を選ぶ回数は<math>m = 2N</math>。)これは次数の期待値が<math>p=2N/n(n-1)</math>のERグラフにおいて、ちょうど辺数が<math>N</math>となった場合に相当する。
+
各頂点が一定数の辺を持つことを意味します。　ちょうど ''c'' = 1 だと二部グラフのマッチングです。''c'' = 2 だと閉路の集合になります。
  
−
===ネットワークの特徴===
+
各頂点が持つ辺の本数（の期待値）が ''c'' なので、''c'' < 1 のときは連結部分の大きさが高々　log ''n'' 程度にしかなりません。しかし　''c'' > 1 としたとたん、繋がっていく確率のほうが高くなります。その半径 (diameter) を ''k'' とおくと ''c''<sup>k</sup> = ''n'' まで成長できるので ''k'' = log ''n'' / log ''c'' です。
 +
 
 +
詳細な解析によると、臨界点にあたる ''c'' = 1 では連結部分のサイズが ''O'' (''n'' <sup>2/3</sup>) になることが知られています。
 +
 
 +
;''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'' で十分です。このとき孤立点が消滅します。
 +
 
 +
====辺の数を固定したい場合====
 +
ERモデルにおいて、辺の数を正確に ''N'' 本とする場合を考えます。''n'' 頂点からランダムに2つを選び、その間に辺を作成するプロセスを正確に ''N'' 回繰り返します。(ランダムに頂点を選ぶ回数は ''m'' = 2 ''N''。)これは次数の期待値が ''p'' = 2 ''N'' / ''n''(''n'' -1) のERグラフにおいて、たまたま辺数が ''N'' となった場合に相当します。
 +
 
 +
===ERモデルの特徴===
 
;クラスター係数
 
;クラスター係数
−
:辺が張られる確率は全て独立なので<math>C(p)=p \simeq c /n</math>。これは<math>K_3</math>や<math>K_4</math>をあまり含まないことを意味している。
+
 
 +
辺が張られる確率は全て独立なので ''C'' ( ''p'' ) = ''p'' &sim; ''c'' / ''n'' です。これは、完全グラフをほとんど含まないことを意味しています。
 +
 
 
;平均頂点間距離
 
;平均頂点間距離
−
:各頂点が持つ辺の期待値を<math>c = (n-1)p</math>として<math>L(p) \geq \log n / \log c = O(\log n)</math>。
+
 
 +
各頂点が持つ辺の期待値を ''c'' = ( ''n'' -1) ''p'' とします。
 +
: ''L''( ''p'' ) >= log ''n'' / log ''c'' = ''O''(log ''n'' )
 +
 
 
;連結性
 
;連結性
−
:Erdős–Rényiグラフ全体が連結であるためには次数が<math>O(\log n)</math>以上必要。
+
ERグラフ全体が連結であるためには、次数が ''O''(log ''n'' ) 以上必要です。

Revision as of 06:05, 12 May 2011

Wiki Top Up one level レポートの書き方 Arita Laboratory

Contents

ここでは頂点がすべて連結した無向グラフを扱います。

歴史と参考図書

  • Erdős P, Rényi A. "On Random Graphs. I.". Publicationes Mathematicae 6:290–297, 1959
  • Erdős P, Rényi A. "The Evolution of Random Graphs". Publ. Math. Inst. Hung. Acad. Sci 5:17–61, 1960
  • Bollobás B. Random Graphs (2nd ed.), Cambridge University Press, 2001
  • Durrett R. Random Graph Dynamics, Cambridge University Press, 2004

ネットワークの指標:CとL

ネットワーク全体についての尺度として、クラスター係数 C と平均頂点間距離 L を紹介します。

クラスター係数

クラスター係数は隣接する頂点間の辺の密度の平均値にあたります。 まず各頂点 i におけるクラスター係数 C_i を以下のように定義します。

辺の長さはすべて 1 とし (|e| = 1)、頂点 i の次数を deg ( i ), 隣接する頂点群を adj ( i ) と書く。
\textstyle C_i=\frac{2}{deg(i)(deg(i)-1)} \sum_{j,k \in adj(i)} |e_{jk}|

グラフ全体のクラスター係数はその平均値です。

\textstyle C =\frac{1}{n} \sum^{n}_{i=1}C_i

クラスター係数が 0.2 や 0.3 になるネットワークは、比較的「密」だといえます。（これから実例をみていきます。）

平均頂点間距離

ここでは頂点 i, j 間の最短経路を p_{ij} と書きます。平均頂点間距離の定義はその字のごとく全頂点間の最短路の平均値です。ネットワーク G の頂点数を n とすると頂点の組み合わせの数が n (n - 1) / 2 あるので

\textstyle L=\frac{2}{n(n-1)} \sum_{i,j\in G}|p_{ij}|

となります。

上の定義だと、例えば無限の広がりを持つ数直線の L を求められません (無限個の最短路を計算しなくてはならない)。そういう場合は、ネットワーク上のある点に注目して L を計算できます。その点から距離 L 以内にある頂点数を数えることで L の値を求められます。（これから実例をみていきます。）

様々なグラフにおける C と L

完全グラフ

全ての頂点間に辺を持つグラフを、完全グラフ (complete graph) といいます。完全グラフでは、 C = L = 1 になります。

木

簡単のため全頂点が同じ次数を持つ木を考えましょう。中心の頂点 v0 を根 (root) と呼びます。木はその定義よりサイクルを持たないので C = 0 です。また平均頂点間距離は、距離 L 以内にある頂点を数えることで求められます。

\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) \\ &\propto (d-1)^{L+1} \end{align}

この関係から（大雑把ですが） \textstyle L=\propto \frac{\log n}{\log (d-1)} \propto \log n となります。

格子

格子状のネットワークでは頂点が一定間隔で配置されるため、道路網のような地理的制約をうけるつながりを表現するのに適しています。平面の場合は三角格子、正方格子、六方格子などが考えられます。ただし、クラスター係数を定義のまま適用すると、三角格子以外は隣接頂点どうしがつながらないために常に C = 0 になります。これでは面白くないので、格子の場合は最短距離が a 以下の点には全て辺を張るバリエーションを考えるのが一般的です。

ここでは、d 次元空間において辺の長さが単位距離の格子を Zd と書きましょう。

Zd において deg( i ) = 2 d

Z1

一次元の格子とは、いわゆる数直線です。ある頂点から k の距離内にある頂点数 n = k + 1 で、これらの頂点への距離の平均値は L = k/2 になります。したがって L ∼ n/2 です。

Z2

二次元の格子として、正方格子を考えます。ある頂点から k の距離内にある頂点数は n = k2 + ( k + 1)2 で与えられ、これらの頂点への距離の平均値が L = k / 2 です。n の式を k について解くと k = {(2 n -1)1/2 - 1} ∼ (2 n)1/2 となるため L ∼ (n / 2) 1/2 です。


Erdős–Rényiグラフ

全ての頂点間に一定の確率 p で独立に辺を作成してできるランダムグラフをErdős–Rényiグラフと呼びます。各頂点に注目してみると　n -1 点に対して確率 p で辺を張るため、その次数は二項分布

n -1Ck p k (1- p) (n -1) - k

に従います。すなわち次数の平均は ( n -1) p となり、これを c と書きましょう。

ネットワークの進化

次数の平均値 c を変化させて生じるグラフ形状の違いを検証します。

c << 1 / n2 のとき

生成される辺数の期待値は pn (n -1) / 2 = cn/ 2 になります。n を無限大にしたとき、この値が 0 に近づくのでネットワークのサイズに対してほとんど辺を持たないことになります。

c = 1 / n のとき

上と同じ理由で、ネットワーク全体で辺が定数本だけ作られるネットワークになります。ほとんどの辺がばらばらに存在します。

c = const.

各頂点が一定数の辺を持つことを意味します。　ちょうど c = 1 だと二部グラフのマッチングです。c = 2 だと閉路の集合になります。

各頂点が持つ辺の本数（の期待値）が c なので、c < 1 のときは連結部分の大きさが高々　log n 程度にしかなりません。しかし　c > 1 としたとたん、繋がっていく確率のほうが高くなります。その半径 (diameter) を k とおくと ck = n まで成長できるので k = log n / log c です。

詳細な解析によると、臨界点にあたる c = 1 では連結部分のサイズが O (n 2/3) になることが知られています。

c = log n

全体が連結になります。

ある頂点が辺を全く持たない確率を考えます。 (1 - p)n-1 = { ( 1 - c /(n - 1))(n - 1)/c }c <= e-c。したがって、そのような頂点がグラフ中に存在しない確率の上限は ne-c となります。これを 0 に収束させるには例えば c >= 2 log n で十分です。このとき孤立点が消滅します。

辺の数を固定したい場合

ERモデルにおいて、辺の数を正確に N 本とする場合を考えます。n 頂点からランダムに2つを選び、その間に辺を作成するプロセスを正確に N 回繰り返します。(ランダムに頂点を選ぶ回数は m = 2 N。)これは次数の期待値が p = 2 N / n(n -1) のERグラフにおいて、たまたま辺数が N となった場合に相当します。

ERモデルの特徴

クラスター係数

辺が張られる確率は全て独立なので C ( p ) = p ∼ c / n です。これは、完全グラフをほとんど含まないことを意味しています。

平均頂点間距離

各頂点が持つ辺の期待値を c = ( n -1) p とします。

L( p ) >= log n / log c = O(log n )
連結性

ERグラフ全体が連結であるためには、次数が O(log n ) 以上必要です。

Retrieved from "http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/NetworkBiology/Erdos-Renyi_Model&oldid=255038"
Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox