Aritalab:Lecture/NetworkBiology/Barabasi-Albert Model

From Metabolomics.JP
< Aritalab:Lecture | NetworkBiology(Difference between revisions)
Jump to: navigation, search
m (→‎Scale-free性)
m
Line 46: Line 46:
 
この過程は優先的選択(preferential attachment)と呼ばれ、一般に''rich gets richer''メカニズムなどともいわれます。
 
この過程は優先的選択(preferential attachment)と呼ばれ、一般に''rich gets richer''メカニズムなどともいわれます。
  
−
==べき則のパラメータ<math>\gamma</math>について==
+
==べき則のパラメータ<math>\lambda</math> (ラムダ) について==
−
BAモデルから<math>\gamma = 3 </math>を簡単に導出できます。
+
BAモデルから<math>\lambda = 3 </math>を簡単に導出できます。
 
初期条件として時刻 0 に 1 頂点の場合、<math>t</math>時間後には頂点数<math>t+1</math>、辺数 <math>mt</math> です。
 
初期条件として時刻 0 に 1 頂点の場合、<math>t</math>時間後には頂点数<math>t+1</math>、辺数 <math>mt</math> です。
 
頂点 ''i'' の次数 <math>k_i</math> は時間が経つと単調増加します。ここで、次数を <math>k_i(t)</math> という連続関数として考えてみます。頂点 ''i'' の次数は単位時間あたり次数 <math>k_i</math> に比例して増加するので
 
頂点 ''i'' の次数 <math>k_i</math> は時間が経つと単調増加します。ここで、次数を <math>k_i(t)</math> という連続関数として考えてみます。頂点 ''i'' の次数は単位時間あたり次数 <math>k_i</math> に比例して増加するので
Line 86: Line 86:
  
 
==何がべき分布を作るのか==
 
==何がべき分布を作るのか==
−
バラバシ－アルバートモデルについて言われる批判のひとつに、自然界においてはべき則のパラメータ&gamma;の多くが2から3の間をとるのに&gamma;=3のときしか説明できないというものがあります。これはどちらかというと的を外した意見です。
+
バラバシ－アルバートモデルについて言われる批判のひとつに、自然界においてはべき則のパラメータ&lambda;の多くが2から3の間をとるのに&lambda;=3のときしか説明できないというものがあります。これはどちらかというと的を外した意見です。
  
−
べき則のパラメータが定数になる理由のエッセンスは、優先的選択において次数の時間変化を規定する微分方程式が <math>\textstyle \frac{dy}{dx} = \frac{y}{2x}</math> つまり <math>y/x</math> の形をとることです。この方程式を解くと<math>y=cx^{1/2}</math>という答えが得られ（<math>c</math>は適当な定数）、この係数1/2が<math>\gamma=-3</math>を作り出します。だから異なる<math>\gamma</math>の値を作り出すには<math>y/2x</math>における比の2を他にずらせばよいのです。
+
べき則のパラメータが定数になる理由のエッセンスは、優先的選択において次数の時間変化を規定する微分方程式が <math>\textstyle \frac{dy}{dx} = \frac{y}{2x}</math> つまり <math>y/x</math> の形をとることです。この方程式を解くと<math>y=cx^{1/2}</math>という答えが得られ（<math>c</math>は適当な定数）、この係数1/2が<math>\lambda=-3</math>を作り出します。だから異なる<math>\lambda</math>の値を作り出すには<math>y/2x</math>における比の2を他にずらせばよいのです。
  
 
<center>
 
<center>
 
<math>\frac{\partial k_i}{\partial t} = \frac{k_i}{pt}</math>
 
<math>\frac{\partial k_i}{\partial t} = \frac{k_i}{pt}</math>
 
</center>
 
</center>
−
という近似を何らかの形で導出できれば、<math>\gamma=p+1</math>になります。
+
という近似を何らかの形で導出できれば、<math>\lambda=p+1</math>になります。
  
 
<!----
 
<!----
 
==適応度モデル==
 
==適応度モデル==
−
各頂点<math>i</math>が「適応度」<math>\eta_i</math>を持ち、優先的選択の確率を<math>\textstyle p = \eta_i k_i/\sum_j \eta_jk_j</math>で表すバリエーション(Bianconi G and Barabasi AL 2001)。BAモデルのパラメータ<math>\gamma=-3</math>は<math>k_i(t) = f(t)</math>と表現した際の<math>t</math>の係数<math>1/2</math>より導出される。適応度を導入して<math>\partial k_i/\partial t</math>の比を<math>k_i/2t</math>からずらすことができればよい。そこで<math>\eta_i</math>を適当に近似することで(例えば<math>2k_i/3t</math>をつくる)、<math>\gamma=-3</math>以外を導出できる。
+
各頂点<math>i</math>が「適応度」<math>\eta_i</math>を持ち、優先的選択の確率を<math>\textstyle p = \eta_i k_i/\sum_j \eta_jk_j</math>で表すバリエーション(Bianconi G and Barabasi AL 2001)。BAモデルのパラメータ<math>\lambda=-3</math>は<math>k_i(t) = f(t)</math>と表現した際の<math>t</math>の係数<math>1/2</math>より導出される。適応度を導入して<math>\partial k_i/\partial t</math>の比を<math>k_i/2t</math>からずらすことができればよい。そこで<math>\eta_i</math>を適当に近似することで(例えば<math>2k_i/3t</math>をつくる)、<math>\lambda=-3</math>以外を導出できる。
  
 
==頂点非活性化モデル==
 
==頂点非活性化モデル==
 
頂点を一つ追加するたびに現存する頂点のいずれか一つをランダムに非活性化し、いったん非活性になると辺を受け取らなくなるバリエーション (Klemm K and Eguiluz VM 2002)を考えよう。（活性状態の頂点は常に一定数である点に注意。）次数<math>k</math>で生き残る頂点の割合を<math>1-P(k)</math>で表現すると、十分大きい<math>t\simeq \infty</math>の定常状態において<math>p^{\infty}(k+1) = (1-P(k)) p^{\infty}(k)</math>が成立する。ここで<math>k</math>を連続値に読み替えると
 
頂点を一つ追加するたびに現存する頂点のいずれか一つをランダムに非活性化し、いったん非活性になると辺を受け取らなくなるバリエーション (Klemm K and Eguiluz VM 2002)を考えよう。（活性状態の頂点は常に一定数である点に注意。）次数<math>k</math>で生き残る頂点の割合を<math>1-P(k)</math>で表現すると、十分大きい<math>t\simeq \infty</math>の定常状態において<math>p^{\infty}(k+1) = (1-P(k)) p^{\infty}(k)</math>が成立する。ここで<math>k</math>を連続値に読み替えると
−
<math>\textstyle p^{\infty}(k+1) -p^{\infty}(k)= \frac{\partial p^{\infty}(k)}{\partial k} = -P(k) p^{\infty}(k)　</math>を導ける。ここで<math>P(k)</math>の式として、非活性化する頂点は次数の逆数に比例する優先的選択に従うと仮定する。つまり次数が大きい頂点ほど生き残りやすいという名目で<math>P(k)=c/k</math>にすると、パラメータ<math>c</math>を適当に調節することで容易に<math>\gamma=3</math>以外を作り出せる。
+
<math>\textstyle p^{\infty}(k+1) -p^{\infty}(k)= \frac{\partial p^{\infty}(k)}{\partial k} = -P(k) p^{\infty}(k)　</math>を導ける。ここで<math>P(k)</math>の式として、非活性化する頂点は次数の逆数に比例する優先的選択に従うと仮定する。つまり次数が大きい頂点ほど生き残りやすいという名目で<math>P(k)=c/k</math>にすると、パラメータ<math>c</math>を適当に調節することで容易に<math>\lambda=3</math>以外を作り出せる。
  
  

Revision as of 09:36, 7 December 2012

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

Contents

スケールフリー性

もともと桁 (scale) に依存しない (free) 性質を意味し、昔から物理学の世界で知られていたものです。日本語ではべき則と呼ばれます。ただし、ネットワークについては1999年から言われはじめました。ネットワークの頂点に接続する辺の数を次数といい、全頂点のなかで次数 k の頂点の占める割合を p(k) と書きます。ネットワークがスケールフリーであるとは次数の分布がべき則に従うことを意味し、式で書くとp(k) \propto k^{-\lambda}になります。

この定義は1999年の論文 Barabási A-L, Albert R "Emergence of Scaling in Random Networks" Science 286(5439):509-512 をきっかけに広まりました。

自然界にはべき則が普通にみられ、以下の例がよく知られています。（この表におけるL, Cの意味はリンク解析の項を参照。）

Network (size) λ L C
インターネット (1.5 x 105) λin=2.1, λout=2.7</math> 3.1 0.11 Barabasi and Albert (1999)
部分的インターネット (3000-6000) 2.16 3.7 0.18-0.3 Faloutous et al. (1999)
映画俳優の共演関係 (2.2 x 105) 2.3 3.7 0.79 Watts and Strogatz (1998)
PubMedデータベースの共著関係 (1.5 x 106)  ? 4.6 0.066 Newman (2000, 2001)

しかし、べき則やそれを生み出すメカニズムの解析は最新の話題ではありません。科学界ではおよそ50年周期で話題になってきました。べき則を示す有名な例として、ジップの法則、パレートの法則などがあります。

  • 20世紀初頭
    • Pareto, V. (1896, 1897) Cours d’economie politique. Reprinted as a volume of Oeuvres Complètes (Droz, Geneva, 1896, 1965). Pareto, V. Cours d’Economique Politique (Macmillan, Paris,　1897) 所得の分布がべき則に従うことを示す
    • Yule, G. (1924) A mathematical theory of evolution, based on the conclusion of Dr. J.C. Willis. F.R.S. Phil. Trans. R. Soc. Lond Ser. B 213, 21–87 優先的選択のメカニズムを示す
  • 20世紀半ば
    • Zipf, G.K. (1949) Human Behavior and the Principle of Least Effort, Addison-Wesley 単語の頻度分布がべき則に従うことを示す
    • Simon, H.A. (1955) On a class of skew distribution functions. Biometrika 42, 425–440 乗算過程が漸近的にべき則に従うことを示す
  • 21世紀初頭
    • Barabási A-L, Albert R (1999) これまでの研究をネットワークの言葉に置き換える

またべき則に近い形である対数正規分布とべき則の関係についても多くの研究がなされました。

  • 乗算過程による対数正規分布の一般性
    • Kapteyn, J.C. (1903) Skew frequency curves in biology and statistics in Astronomical Laboratory, Noordhoff, Groningen
    • Gibrat, R. (1931) Les Inegalites Economiques, Libraire du Recueil Sirey, Paris
  • 乗算過程がべき則を生むメカニズム
    • Kesten, H. (1973) Random difference equations and renewal theory for products of random matrices. Acta Mathematica CXXXI, 207–248
    • Reed, W.J. and Hughes, B.D. (2002) From gene families and genera to incomes and internet file sizes: why power-laws are so common in nature. Phys. Rev. E 66, 067103

Barabási-Albert Model

Barabási, Albertがネットワークの成長モデルとして提唱したのは以下の過程です。(正確には初期条件が異なるが本質は同じ。）

  1. 時間ステップ 0 における 1 頂点からスタートする。
  2. 単位時間毎に頂点を1つずつ追加し、既に存在する頂点とm本の辺でつなぐ。
    新しい辺はそれぞれ確率\textstyle p_i = k_i / \sum_j k_j (ここでk_iは頂点iの次数) で接続先を決定する。

この過程は優先的選択(preferential attachment)と呼ばれ、一般にrich gets richerメカニズムなどともいわれます。

べき則のパラメータ\lambda (ラムダ) について

BAモデルから\lambda = 3 を簡単に導出できます。 初期条件として時刻 0 に 1 頂点の場合、t時間後には頂点数t+1、辺数 mt です。 頂点 i の次数 k_i は時間が経つと単調増加します。ここで、次数を k_i(t) という連続関数として考えてみます。頂点 i の次数は単位時間あたり次数 k_i に比例して増加するので

\frac{\partial k_i}{\partial t} = m \frac{k_i}{\sum_j k_j} = \frac{k_i}{2t}

これを解くと \textstyle k_i(t) = m(t/t_i)^{1/2}、 ただし t_i は頂点 i が追加された時間で k_i(t_i)=m となる値です（初期条件）。 これを式変形すれば、頂点の次数がある値 x になる時間は t=t_i(x/m)^2\, であることがわかります。

頂点の次数分布 p(k) を求めるために、まず頂点の次数が k より大きくなる割合（累積分布関数）を求めます。次数が k より大きくなるような頂点全体の割合は、時刻 t(m/k)^2\, より前に追加された頂点全体の割合に等しくなります。

\mbox{Pr}[k_i(t) > k] = \mbox{Pr}[t_i < t(\frac{m}{k})^2] = (\frac{m}{k})^2

左の等号は、頂点 i が追加された時間 t_i が、時刻 t に対して (m/k)^2\, よりも早ければ（小さければ）、次数が k を超えることを示しています。 頂点が常に一定量ずつ追加されることを考えると、全体サイズを1とするなら、その割合は単純に (m/k)^2\, としてよいことがわかります。

次数分布 \mbox{Pr}[k_i(t) = k]\, は \mbox{Pr}[k_i(t) > k] - \mbox{Pr}[k_i(t) > k+1]\, と書けるので、その差はkを変数と考えて \textstyle - \frac{d}{d k}\mbox{Pr}[k_i(t) > k] になります。 実際にkで微分すると\mbox{Pr}[k_i(t) = k] = \frac{2m^2}{k^3}。すなわち辺の次数はk^{-3}に比例します。

優先的選択でない場合

新しい辺が結びつく先が次数に比例する値ではなく、一様分布に従うと仮定してみます。頂点 i は頂点数に正比例して辺を得る確率が減っていきます。

\frac{\partial k_i}{\partial t} = m/(n-1) = m/t

これを解くと k_i(t) = m \log t + const. です。 初期条件として 頂点 i　が追加された時間 t_i に辺の数が m であること k_i(t_i) = m をいれると k_i(t) = m\Big(\log(\frac{t}{t_i})+1\Big)。頂点 i の次数が k になる時間は k_i \exp(k/m -1) であることがわかります。 こちらも累積分布関数を計算してみましょう。

\mbox{Pr}[k_i(t) > k] = \mbox{Pr}\Big[t_i < t\Big(\frac{1}{\exp(k/m - 1)}\Big)\Big] = ee^{-k/m}

これを上のセクションと同様に微分することで\mbox{Pr}[k_i(t)=k] = \frac{e}{m}e^{-k/m}、すなわち辺の次数は指数的に減少することになります。

何がべき分布を作るのか

バラバシ－アルバートモデルについて言われる批判のひとつに、自然界においてはべき則のパラメータλの多くが2から3の間をとるのにλ=3のときしか説明できないというものがあります。これはどちらかというと的を外した意見です。

べき則のパラメータが定数になる理由のエッセンスは、優先的選択において次数の時間変化を規定する微分方程式が \textstyle \frac{dy}{dx} = \frac{y}{2x} つまり y/x の形をとることです。この方程式を解くとy=cx^{1/2}という答えが得られ（cは適当な定数）、この係数1/2が\lambda=-3を作り出します。だから異なる\lambdaの値を作り出すにはy/2xにおける比の2を他にずらせばよいのです。

\frac{\partial k_i}{\partial t} = \frac{k_i}{pt}

という近似を何らかの形で導出できれば、\lambda=p+1になります。


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

Variants
Actions
Navigation
metabolites
Toolbox