「ほっ」と。キャンペーン

一人抄読会

syodokukai.exblog.jp
ブログトップ

<   2014年 06月 ( 8 )   > この月の画像一覧

Points of significanceコラム 2:統計における推定と検定(1)

Points of significance: Significance, P values and t-tests.

Krzywinski M, Altman N.

Nat Methods. 2013 Nov;10(11):1041-2.

Points of significanceの第2回では、まず(1)母集団概念と統計的推測の時制についてまとめ、(2)母集団からこれから観測するデータを「予言」する方法について触れた後、(3)観測したデータからもとの母集団を「推測」する統計的推定を4段階で理解する。最後に(4) Nature Methods総説にある仮説棄却による統計的検定の例を見る。

1. 母集団概念と統計的推測の「時制」
(1) 母集団と統計的推定

統計学では、抽象的な概念である「母集団」(無限母集団)というものを想定している。母集団は、具体的に見たり数えたりできない架空の存在である。何らかの「もの」ではなく、思弁的に想定している「自然現象」という「こと」と考えてよいだろう。これを観測して得たデータが「標本」である。自然現象を観測すると、そのたびに全く同じ値が得られることはないが、これはもとの自然現象がランダムな散らばりを持っていると考える。自然現象はある確率分布の関数で表されるため、一つの「真の値」というようなものは決して知ることはできず、その値は観測から推測するしかない。母集団としての自然現象の数値は、「観測の外」とか「観測値に匹敵するもの」というような語源をもつ「パラメーター」と呼ばれ、母数と訳される。母集団の確率分布はよく正規分布と考えられ、その母平均μ、母標準偏差σなどが母数である。観測データすなわち標本とは、母集団の確率分布に従って生起する数値であると考える。以下では、標本を加工して「統計量」(検定統計量、注1)という数値を作り、統計量の分布を考えることによって母数をある範囲で推測する。これが統計的推定(statistical inference)である。

注1:統計学で扱う数量のうち、平均や標準偏差など標本データを要約した量は「基本統計量(basic statistics)」と呼ぶ。検定に用いるためにこれらから計算した量のことを「検定統計量(test statistics)」と呼び、以下では検定統計量のことを単に「統計量」と記載することにする。

(2) 統計学における「時制」
統計学は、未来に向かって「予言する」のと、過去を向いて「推定する」という大きく分けて2つの時間的方向がある。これに関しては『完全独習 統計学入門』(小島寛之著、ダイヤモンド社)に詳しく、ここでも「95%予言的中区間」という分かりやすい用語を引用させていただいた。
95%予言的中区間:「これから観測するデータ」を95%の確率で「予言する」ときの用語。ある現象の本質がすでに分かっていて、将来の観測でそこからどのような結果が得られるかを95%の確率で予測する。「未来に向かって」の用語である。
95%信頼区間:「すでに起きて確定していること」だが、まだ自分が知らないことを推論するときの用語。「過去に向かって」の用語ととれるが、実際にはわれわれの観測を要約して、それを用いてある現象の本質を理解したいというときに用いる。

以下の2では「将来の観測結果を95%予言的中区間で予言する」、3では「ある現象を95%信頼区間で区間推定する」という順でまとめる。以下の議論の進め方も『完全独習 統計学入門』(小島寛之著)を参考にさせていただいている。

2. 母集団が分かっているとき、これから観測するデータを予言する
(1) 1個の観測データを予言する (統計量zと標準正規分布を用いる)

母集団を表す正規分布の中で、平均0、標準偏差(SD)1のものを標準正規分布という。標準正規分布では、-2以上~+2以下の範囲(平均±2SDの間)にデータの95.44%が含まれる。95%を含む範囲は約-1.96以上~約+1.96以下(平均±1.96SDの間) である。

平均μ標準偏差σが分かっている正規分布母集団から、1回だけ観測したときのデータx (1個だけ取り出した標本x)がどのような数値か、95%の予言的中区間で(未来のことを)予言したい。以下、分かっている値を青字これから知りたい未知の値を赤字で表す。

ここで、観測データxから母平均µを引いて母標準偏差σで割った統計量zを考える。

統計量z


である。xは正規母集団から取り出したので、その分布は正規分布に従っている。zは上の式から標準正規分布上の数値であることが分かる。そのため、zは95%の確率で、

-1.96≦≦+1.96


の区間に含まれる。この式を変形すると、xの95%予言的中区間は、

µ-1.96µ+1.96


と計算できる。

(2) n個の観測データの平均を予言する (統計量Uと標準正規分布を用いる)
同じく平均μ標準偏差σが分かっている正規母集団から、n個の観測値を得る(標本サイズnの標本をこれから取り出す)。このとき、これから取り出す標本の標本平均¯xがどのような値か95%の確率で予言したい。

標本を何回も取り出すと、そのたびにできる標本平均¯xによって分布(標本分布)ができる。この標本分布は、平均µ標準偏差σ/√nの正規分布になることが分かっている(Points of significance (1) 参照)。ここで¯xから平均µを引いて標準偏差σ/√nで割ることにより、標準正規分布に従う統計量ができる。これを、


統計量U




とする。Uは95%の確率で、

-1.96+1.96


の区間に含まれる。この式を変形すると¯xの95%予言的中区間は、

µ-1.96µ+1.96


と計算できる。
上記の統計量zとUは似ているが、zは1個の観測データxに関する統計量で、Uはn個の観測データからなる標本の平均¯xに関する統計量である。

3. 観測したデータから、未知の母集団について推定する
次に、観測したデータを用いて、未知の現象について推定する方法を述べる。これは、今持っている標本を用いて、すでに存在している母集団について推定するという(過去に向かっての)流れであり、以下のような5段階で順に考える。既知の観測データから統計量を作り、その統計量の分布を用いて、今度は未知の母集団について推論する。以後も分かっている値を青字これから知りたい値を赤字で示す。

第0段階:未知の母集団について本当に何もわかっていないとすると、母集団が「正規分布に従っているかどうか」も不明なはずである。しかし以下では母集団が正規分布であることを前提に考えることにする。それ以外の場合は、中心極限定理を用いた大標本の推定かノンパラメトリック手法を用いるが、これは別の回で考える。

第1段階: 正規母集団であり、母分散が分かっているとき、母平均を区間推定する。
ここで、「母集団については正規母集団であるという以外分かっていない」と言っているの、「母分散は分かっている」というのは、不自然な前提である。しかし、まずはこのような段取りで考えていくことが必要なため、この段階を踏むことにする。

第2段階: 正規母集団であり、母平均が分かっているとき、母分散を区間推定する。
これから知りたい母集団について、あらかじめ「母平均が分かっている」というのも不自然だが、先のためにこの段階も理解する。

第3段階: 正規母集団であり、母平均が分かっていないとき、母分散を区間推定する。
ここから先の段階では、母集団は正規母集団であるということ以外は分かっていない。まずこの段階では母分散を推定する。最終目標としては母分散より母平均の方が知りたいが、順番上この段階を踏むことにする。

第4段階:正規母集団であり、母分散が分かっていないとき、母平均を区間推定する。
いよいよ最終的な段階であり、母集団について正規母集団であるという以外何も分かっていないところから母平均を推定する。

【第1段階:あらかじめ母分散が分かっている正規母集団から、標本サイズn、標本平均¯xの標本を取り出した。このとき、まだ分かっていない母平均µを95%の信頼区間で区間推定する】
→統計量Uと標準正規分布を用いる

ここでは、前項でも出てきた標本平均の分布を考えると、標本平均¯xは平均µ(母平均と同じ)、標準偏差σ/√nの正規分布に従う。前項と同じように

統計量U


を計算すると、Uは標準正規分布に従うから、95%の信頼区間で、

-1.96+1.96


に含まれる。この式を知りたいμについて変形すると、

-1.96+1.96


となり、母平均μが95%信頼区間で区間推定できることになる。(これは「未来の」予言ではないから「95%の確率で予言的中する区間」と言わず、「95%信頼区間での区間推定」と呼ぶことに注意)。


【第2段階:あらかじめ母平均µが分かっている正規母集団から、標本サイズn (x1、x2・・・、xn)、標本平均¯xの標本を取り出した。このとき、まだ分かっていない母分散σ2を95%の信頼区間で区間推定する】
→統計量Vと自由度nのカイ二乗分布を用いる

カイ二乗分布について:
標本サイズn (x1、x2・・・、xn)のとき、これらの観測データをすべて二乗して合計した、を考える。このとき、観測の機会ごとに(標本の取り方によって)Vはまちまちの値を取るので、Vはある分布に従う統計量となる。この時の観測データ数nを自由度と呼ぶと(例えば3個ずつ観測データを取っていれば自由度3)、Vは「自由度nのカイ二乗分布(chi-square distribution)」(図1)に従っている。
d0194774_22452858.png
図1:カイ二乗分布の図。
自由度nによってグラフの形が違う。

さて、母標準偏差σの推定に戻る。まず各観測データからそれぞれの統計量zを計算すると、

z1z2、・・・、zn


となり、zは標準正規分布に従っている。そこで、zを標準正規分布から取り出した数値、新しい標本と考える。これらの標本を二乗して合計すると、その統計量Vは自由度nのカイ二乗分布に従うはずである。

統計量V・・・    

22+・・・+2


青字は分かっている数値なので、この式は

V=


というようにまとめられる。最後に、カイ二乗分布するVが95%の頻度で含まれる区間を考えるが、図2のようにVがa以上なら97.5%を含み、b以上なら2.5%を含むという値a、bがカイ二乗分布の数値表から分かる。Vは95%の頻度でこの間にあると言えるので、

ab


この式をσ2について変形すれば母分散σ2を95%の信頼区間で区間推定できる。
d0194774_219291.gif
図2 カイ二乗分布するxの値は、95%の頻度でaとb(黒で塗った外側の面積がそれぞれ2.5%である)の間に含まれる。aとbは自由度nによって値が異なるが、これらはカイ二乗分布の数値表によって分かる。

次項(2)に続く。

d0194774_22475144.png
休憩コーナー:カイ二乗分布のぬいぐるみ発見!!
( http://nausicaadistribution.blogspot.jp/より)

[PR]
by md345797 | 2014-06-28 01:40

Points of significanceコラム2:統計における推定と検定 (2)

前項(1)からの続き

【第3段階:母平均µが分かっていない正規母集団から、標本サイズn (x1、x2・・・、xn)、標本平均¯xの標本を取り出した。このとき、まだ分かっていない母分散σ2を95%の信頼区間で区間推定する】
→統計量Wと自由度(n-1)のカイ二乗分布を用いる

まずここでの標本の分散を考える。標本分散s2は定義上、(各観測値-標本平均)の二乗を合計して標本サイズnで割ったものなので、

標本分散s2


ここで、

統計量W


というものを考える。これらの式を比較すると、s2とWは分子が同じで

n×s2σ2×W


すなわち、

W


であり、Wは標本分散s2に比例する統計量である。そして、この統計量Wは、自由度(n-1)のカイ二乗分布に従うことが証明されている(証明は省略)。

標本(標本サイズn、標本平均¯x)から標本分散s2を計算して、それをn/σ2倍すると統計量Wができる。Wは自由度n-1でカイ二乗分布し、Wが95%の頻度で含まれる区間a’-b’はカイ二乗分布の数値表から分かるため、

a’b’


この式をσ2について変形すれば、母平均µを用いずに母分散σ2が95%の信頼区間で区間推定できる。


【第4段階:正規母集団で母標準偏差σが分からない場合、標本サイズn、標本平均¯xの標本を取り出し、分かっていない母平均µを95%の信頼区間で区間推定する】
→統計量Tと自由度(n-1)のt分布を用いる

今までの方法から考えて、「求めたい母平均µを含み、標本から計算でき、しかもそれが従う分布が分かっている統計量」を作る必要がある。そうすればその分布を用いて95%信頼区間でµが区間推定できる。

この統計量を作ったのがウィリアム・ゴセット(1876-1937, ペンネームStudent、注2)であった。ゴセットは、

統計量T= (sは標本の標準偏差)


を作った(注3)。そして、この統計量Tが「自由度n-1のt分布」に従うことを発見した。
d0194774_23371531.png
図3: t分布 (自由度=1、2、5)と標準正規分布

「Studentのt分布」と呼ばれるこの分布は0を中心として正規分布によく似た形をとるが、正規分布に比べると頂上が低く裾野が広い形をしている(図3)。nが非常に大きい値をとる大標本であればt分布は正規分布で近似できるが、nが小さい小標本の場合は独自の分布になる。t分布を用いることにより、標本サイズが小さい場合でも正確にµが区間推定できるようになった(注4)。

Tを95%の確率で予言できる区間は、t分布上で-αから+αの間というように分かるので、


となり、これにより母平均µが95%信頼区間で区間推定できる。

注2:ギネスビール社の醸造技術者であったゴセットは、ギネス社の職務外の研究として秘密裡に論文を書き匿名で発表した。その際「自分は、先生である統計学者カール・ピアソンのstudent(生徒)である」という意味を込めて「Student」というペンネームを用いたようである。(『推測統計のはなし』蓑谷千鳳彦著、東京図書より)

注3:多くの本やWikipediaの記載では、この式の√n-1の部分が√nになっている。一方、『完全独習 統計学入門』(小島寛之著)や『入門 統計学-検定から多変量解析・実験計画法まで-』(栗原伸一著、オーム社)では√n-1であり、本稿もこれに従っている。多くの本では、標本標準偏差として通常の「標本の標準偏差s」の代わりに、母分散を偏りが出ないよう推定するために自由度で調整した標準偏差「不偏標準偏差」を用いているためこの違いがある。標本標準偏差不偏標準偏差との関係は以下通りである(詳しい説明は省略)。

不偏標準偏差 x 標本標準偏差(s)


多くの本では、標本標準偏差sを√n/(n-1)倍した不偏標準偏差のことを単に「標本標準偏差」と表記しているために、統計量Tの式

統計量T=


で√n-1が√nとなっているので注意が必要である。本によって記号がまちまちであることも理解を面倒にしており、「不偏標準偏差をσ ̂、標本標準偏差をs」とちゃんと区別して書いてある本、「前者を小文字のs、後者を大文字のS」と分けている本、不偏標準偏差の意味で「標本標準偏差s」という用語を用いている本などいろいろである。それぞれsが何を意味しているかはっきりさせて、その上で√n-1か√nかを読者が理解している必要があるだろう。

注4:ゴセット以前には、母集団で母標準偏差σが分からない場合に、

統計量


という統計量を作って、これが正規分布に従うということにして母平均µを区間推定していた。本当は、

(=統計量U)


が正規分布に従うのだが、母標準偏差σが分かっていないので標本標準偏差sで代用してよいことにしていた。これではnが非常に大きいときは誤差が少ないが、nが小さいときには結果に無視できないずれが生じていた。

そこでゴセットが考案した統計量Tは、

T=


というものであった。これは、

U=、 W=


であることから、

T(σが消える)


となり、母標準偏差σが分かっていない場合でも母平均µの区間推定ができる。これは母集団について何もわかっていなくても、母平均が区間推定できる画期的な方法であった。


d0194774_22533886.png

休憩コーナー(2): 正規分布(左)とt-分布(右)のぬいぐるみも発見!
形から言うと、左の方がt-分布っぽいが・・・。(http://nausicaadistribution.blogspot.jp/より)

次項(3)に続く。

[PR]
by md345797 | 2014-06-28 01:26

Points of significanceコラム2:統計における推定と検定 (3)

前項(2)からの続き

4. Nature Methods総説(Krzywinski M, Altman N. 2013 Nov)
最後に、Nature Methods総説にある有意性と統計的検定の例を確認する。

(1) 1回の観測値が有意かどうかの検定
ある蛋白の発現量が10であるとき(これは過去の繰り返しの実験から明らかになっているとする)、今回の実験では発現量12と観測された。観測値12は妥当なものだろうか?

図4aで、ある現象の数値として分かっている値(Reference、ここでは10)は母集団平均に当たるのでµ
、観測値(observed、ここでは12)は標本データに当たるのでxとしてある。

観測値xはランダムなばらつきを示すので、取りうるすべての値の母集団から取り出した一つの標本であると考える。無数に観測を繰り返したときの観測値とその度数の関係を表したグラフは図4bのような正規分布になると思われる(正規分布と考えられない場合については別の回で述べる)。今回の観測値x=12は実際のところ、ありえないような外れ値である。それを示すため、まず、帰無仮説H0「今回の観測値は図4bのようなμを平均とするような母集団から得られたものである」を立て、最終的にこれを棄却するという方法を取る。帰無仮説H0を表した母集団(図4b)を帰無分布と呼ぶ。

このとき、x=12以上に外れた観測値が出る確率は、網掛けの部分の面積で計算される部分である。これがP値である。P値の大小によって今回の観測値の妥当性を判断する。ここでP値が小さい(通常P=0.05)ということは、帰無仮説の下でほとんどありえないことが起こったと考える。この帰無仮説H0の下でほとんどありえないことが起きているとすると、おおもとの状況(H0)自体が間違っているのだろうと棄却する。そこで、その対立仮説H1「今回観測された標本は、平均がµではない母集団から得られたものである」が有意に支持されることになる。
(なお厳密に言えば、このような対立仮説H1は「よく用いられる対立仮説」に過ぎず、他の対立仮説もいろいろ考えられる。だからこの対立仮説H1が「必ず正しい」とは限らない。)
d0194774_120204.jpg

図4 1個の観測値の有意性の判断

なお、P値は「帰無仮説の下でほとんどありえないことが起こった」確率であって、「帰無仮説が正しい確率である」ということではないので注意(注5)。この点はしばしば誤って解釈される。また、P値は統計的に有意であることを表すが、単に「統計的に」であって、それ以上の意味付けはできないことにも注意が必要である(注6)。

注5:これは「訴追者の誤謬」(prosecutor's fallacy)と同じ原理で間違っている。訴追者の誤謬についてはここでは述べないが『リスク・リテラシーが身につく統計的思考法―初歩からベイズ推定まで』(ゲルト・ギーゲレンツァー著、吉田 利子訳、ハヤカワ文庫NF)に詳しい解説がある。

注6:統計的有意性が示されても、それ以上の価値判断は加えられないことに注意する。さらにはその観測値自体にも何か「意味がある」とすら言えない。特に「統計的に有意差がある」とつい「一方が優れている」などと価値判断しがちだが、それは厳に慎むべき態度である。有意性(significance)という言葉は「重要な」とか「意味がある」という内容も含むため、significantly differentという言葉は誤解を招きやすいのかもしれない。統計的に有意な結果が「何を意味するか」は、統計学以外の根拠に基づいて決定されるべきなのである。なお、有意水準がp=0.05というのは単なる慣習的な線引きなので、0.049なら有意で0.051なら有意でないなどと判断するのはおかしい。差があるか否かはP=0.05という数字で区切るのではなく、そこでもやはり統計学以外の判断が必要であろう。
この注6の部分は、『涙なしの統計学』(D. ロウントリー著、加納悟訳、新世社) の記載を参考にさせていただいた。

(2) n個の観測値の平均が有意かどうかの検定
次に、1つのデータだけでなくさらに4つのデータを観測したとする。そうすると、n=5の標本を取ったことになる(図5a)。このときの標本平均は¯x=10.85、標本標準偏差s=0.96であった。この標本標準偏差s=0.96は母集団の標準偏差σと同じ考えてよいと仮定する(この仮定が成り立たない場合については別の回で述べる)。 ここで標本平均¯xの分布は正規分布であり、その平均はµ、標準偏差はs/√nである(図5b)。(注7)
d0194774_1164361.jpg

図5 n個の観測値の有意性の判断

注7:Nature Methodsの総説にはこう書いてあるが、正しくは前項(2)の注4のように標本分布の標準偏差はσ/√nである。ここではs=σと仮定しているのでこれでよいことにしている。また、これも前項(2)の注3のようにここでのsは単なる標本の標準偏差のことだから、

不偏標準偏差 x 標本標準偏差s


で不偏標準偏差を計算して、

統計量T=


とするべきだろう。これらのことは、この総説では省略されてしまっている

上記のTが取りうる値のt-分布から、図5cのような¯xの分布が分かる。1つの観測データのときと同じく、P値が求められ、これにより5個の観測データの平均が有意かどうかが判断できる。

(3) t-検定を用いた有意性の判断
上の例でn個のデータを観測したときに、

統計量t


はデータ数nを自由度とした図6aのようなt-分布に従う(注8)。

注8:このNature Methodsの総説にはこう書いてあるものの、正しくは上の注7の統計量Tの式が正しい。この総説ではsを不偏標準偏差としているのだろうが、混同しやすい記載である。
d0194774_1141037.jpg

図6 t-分布とそのP値

ここで、nが大きければ統計量tの値のP値も正規分布に近いが、nが小さい小標本の場合は同じtでもP値は非常に小さくなり、有意性を無視できないくらい過大評価してしまう。そのため、小標本の場合は正規分布ではなくt-分布で考える必要がある。例として、n=5の場合t=1.98であるP値はP=0.119であるはずなのに、正規分布で考えていると、P=0.048と有意であることになってしまう。
[PR]
by md345797 | 2014-06-28 01:23

複雑ネットワークの理論(6):ヒトの疾患と疾患遺伝子のネットワーク “Diseasome”

The human disease network.

Goh KI, Cusick ME, Valle D, Childs B, Vidal M, Barabási AL.

Proc Natl Acad Sci U S A. 2007 May 22;104(21):8685-90

【まとめ】
ヒトの疾患と疾患遺伝子のデータベースであるOMIMを基に、ヒト疾患ネットワーク(HDN)疾患遺伝子ネットワーク(DGN)を作成した。さらにこれらの2つのネットワークを連結させることにより、「疾患と疾患遺伝子の関連」の全体像である"diseasome"を作成した。また、DGNには機能的モジュールがあることを示した。最後に、疾患遺伝子がコードする蛋白は他の蛋白との相互作用が特に多いのか、すなわちネットワーク上でハブを形成しているかを検討した。その結果、ヒト疾患遺伝子のうち生存に必須な(マウスで欠損すると致死になる)遺伝子がコードする蛋白だけがハブを形成しており(中心的であり)、非必須の遺伝子はハブにはなっていなかった(末梢的であった)。ただし、体細胞変異によって疾患が起きる遺伝子(多くのがん遺伝子)はハブを形成する傾向があった。このようなネットワークに基づく検討は、疾患と疾患遺伝子の関連に関する新たなプラットフォームを我々に与えてくれるものである。

【論文内容】
疾患遺伝子(遺伝子に占める疾患の座位)は、従来からのさまざまな遺伝学的方法、最近のポジショナルクローニング法、ゲノムワイド関連解析などによって明らかにされてきた。さらには、蛋白-蛋白相互作用マップ蛋白-蛋白相互作用マップ(interactome)ヒト代謝ネットワークを基にして、疾患遺伝子の詳細なマップも作られている。さらに、ネットワーク手法を用いて疾患と蛋白-蛋白相互作用の関連を解明しようとする試みもある。そもそも疾患と疾患遺伝子の関連は、「単一の疾患遺伝子が単一の疾患と関連している」というようなものではない。異なる複数の遺伝子変異が同じ疾患につながることがあり、例えばZellweger症候群はペルオキシソーム生合成に関する少なくとも11遺伝子のいずれに変異が起きても出現する。また、1つの遺伝子の中の別の変異が異なる疾患形質を惹き起こすこともあり、例えばTP53の変異は11の異なるがん関連異常に関与している。そこで本研究は、「単一遺伝子-単一疾患」的アプローチではなく、現時点で知られるすべての遺伝的疾患(disease phoenome)と疾患遺伝子のセット(disease genome)とをネットワークとして連結することによって、疾患と疾患遺伝子の組み合わせの全体像、すなわち“diseasome”を把握することを目標とした。

Diseasomeの構築
まず、今までに知られたすべての遺伝的疾患のグループとすべての疾患遺伝子のグループを結びつけた2部グラフを作成した(図1a中央) (2部グラフ(bipartite graph)とは、グラフ理論において2つのグループに含まれる頂点どうしが連結しているグラフであり、これらの頂点は同じグループ内では連結していないものを指す)。左の疾患が右の疾患遺伝子の変異と関連があることが示されているとき、それら2つの頂点を枝で連結した。これらの疾患、疾患遺伝子、それらの関連は、ヒトの疾患遺伝子とその形質についてのデータベースであるOnline Mendelian Inheritance in Man(OMIM)から得たものである(2005年12月の時点で、1,284種の疾患と1,777種の疾患遺伝子が登録されていた)。OMIMに含まれる内容は、当初は単一疾患につながる単一疾患遺伝子が主だったが、最近は共通の疾患に関連する遺伝子変異や同じ遺伝子変異に伴う複数の疾患が多く登録されている。このような登録にはいくつもバイアスがあるだろうし、このデータベース自体、当然完成したものではない。しかしOMIMは現時点で知られる遺伝的疾患と疾患遺伝子についての最も完全なデータベースである。なお当研究では、ここに含まれる全疾患を22の疾患クラスに分類して以下の作業を行った。
d0194774_12462785.jpg

図1 “Diseasome”の作成
中央:ヒトの疾患ネットワーク(左のHuman Disease Networkに基づくDisease phenome)と疾患遺伝子ネットワーク(右のDisease Gene Networkに基づくDisease genome)に含まれるそれぞれの頂点を枝で結んだ2部グラフ(DISEASOME)。頂点の○は疾患、□は疾患遺伝子を表し、ある疾患遺伝子が疾患に関連しているときに枝で連結している。○の大きさは、その疾患に関与する遺伝子の数を表す。
左:ヒトの疾患のネットワーク(Human Disease Netwotk)で、以後HDNと呼ぶ。左図の2頂点間の枝は、それらに関与している同じ疾患遺伝子があることを示す。また枝の太さは2頂点の疾患に関与する共通する疾患遺伝子の数を表す。例えば、乳がんと前立腺癌は両方に共通して関連する遺伝子が3つあるので、枝の幅も他の3倍になっている。
右:疾患遺伝子のネットワーク(Disease Gene Networkで、以後DGNと呼ぶ。2頂点間の枝は2つの疾患遺伝子が同じ疾患に関連していることを表す。枝の太さは2つの疾患遺伝子が共通して関連する疾患の数を表している。このdiseaseomeは縮小版だが、完全なものはSupporting Information(SI)の図13を参照。
d0194774_1248951.jpg

図2 ヒト疾患ネットワーク (HDN)と疾患遺伝子ネットワーク (DGN)
(a) HDNでは各頂点が一つ一つの疾患を表し、2頂点間の枝は、それらの2つの疾患に共通する疾患遺伝子があることを表す(詳しくは下記参照)。ここでは、関連する疾患遺伝子が10個より多い疾患のみ疾患名を書きそれ以外は省略しているが、完全な図はSupporting Information(SI)の図13を参照。
(b) DGNでは、各頂点が疾患遺伝子であり、2つの遺伝子が共通して同じ疾患に関連しているときに枝で連結してある(詳しくは下記参照)。


HDNの特性
HDN(図2a)では各頂点が一つ一つの疾患を表し、頂点の色は22の疾患クラスを、頂点の大きさはその疾患に関連する疾患遺伝子の数を表す。2頂点間の枝は、それらの2つの疾患に共通する疾患遺伝子があることを表す。枝の幅は共通する疾患遺伝子の数を、枝の色は同じクラスの疾患どうしならその色、別のクラスの疾患どうしなら灰色としている。

もし疾患がそれぞれ特有の遺伝的原因を持ち、共通する疾患遺伝子が少なければ、HDNの多くの頂点が連結していないか、またはごく少数の疾患ごとの小さいクラスターを形成するだろう。しかし実際のHDNでは、頂点(疾患)は多くの枝(共通の疾患遺伝子の存在を示す)で連結されている。OMINに含まれる1,284種の疾患のうち、867種は少なくとも1本の枝を持ち、516種が多数の枝を持つハブを形成していた。疾患に関連する疾患遺伝子の数s (頂点の大きさで表示)は疾患によって大きく異なり、広い分布を示していた(SI 図6a)。大多数の疾患はsが少ないが、いくつかの疾患はsが非常に大きく、例えば難聴はs=41、白血病はs=37、大腸がんはs=34というようにかなり多くの疾患遺伝子と関連していた。また、各頂点の枝の数kも広い分布を示しており(SI 図6b)、大多数の疾患はごく少数の疾患にしか関連していないが、いくつかの疾患は例えば大腸がんはk=50、乳がんはk=30という多数の疾患に関連していた。

HDNは明らかなクラスターを形成し、これらは22の疾患クラスに対応するものであった。最も大きいがんのクラスターには密な相互連結が見られ、これは多くの共通した疾患遺伝子(TP53、KRAS、ERBB2、NF1など)との関連を介して互いに連結しているためと考えられた。がんのクラスターにはがんになりやすいいくつかの疾患(Fanconi貧血、毛細血管拡張性運動失調症 Ataxia Telangiectasiaなど)も含まれている。その一方で、代謝性疾患の多くはがんのように大きなクラスターを形成しておらず、小さい連結した頂点群を形成していた。がんでは異なる疾患遺伝子の変異が同じ疾患につながること(遺伝子座異質性)が多いが、代謝性疾患はそのようなことが少ないためと考えられる。

DGNの特性
DGN(図2b)では各頂点が疾患遺伝子であり、2つの遺伝子が共通して同じ疾患に関連しているときに枝で連結してある。頂点の大きさは、その疾患遺伝子が関連している疾患の数を表す。疾患遺伝子が1つのクラスの疾患に関連していれば頂点はそのクラスの色にしてあるが、1つのクラスより多い疾患に関連していれば灰色にしてある。5つ以上の疾患に関与している遺伝子や本文で言及している遺伝子について、遺伝子名を付記している。DGNでは、OMIMに含まれる1,777疾患遺伝子のうち1,377遺伝子が共通して同じ疾患に関連していることを表す枝を持ち、903遺伝子(特にTP53PAX6)は多数の枝を持つハブを形成していた。

HDNとDGNにおけるクラスター形成
HDN(疾患)とDGN(疾患遺伝子)のグラフの枝の数は同じままで、それぞれの連結をランダムにシャッフルしたグラフ(ランダムコントロール)も作成した。その結果、ランダムにつなぎかえた疾患ネットワークにおける連結した頂点の集まりの平均サイズ(頂点数643±16)は、実際のHDNにおける平均サイズ(516)より有意に大きかった(SI図6c)。同様に、ランダムにつなぎかえた疾患遺伝子ネットワークにおける連結した頂点の集まりの平均サイズ(頂点数1,087±20)は、実際のDGNにおけるサイズ(903)より有意に大きかった(いずれもP<10^-4、SI図6cとe)。これらの結果は、HDNもDGNも実際のネットワークはランダムコントロールに比べ、クラスター形成が大きいことを示している。また、実際の疾患(または疾患遺伝子)は、同じクラスの疾患(または疾患遺伝子)により連結しやすい。例えば、実際のHDNでは同じクラスの疾患の間に812の枝があり、これは同じクラスの疾患をランダムに連結させた場合の枝の数107±10に比べ8倍も多かった。

DGNにおけるモジュール形成
ある疾患に関連する複数の疾患遺伝子の蛋白産物は、同じ細胞内パスウェイや分子複合体などの同一の機能的モジュールに属していることが多い(実例として分かっている疾患はほとんどないのだが、Fanconi貧血はDNA修復という機能的モジュールに含まれる蛋白をコードする遺伝子の変異による)。実際の疾患遺伝子にモジュール形成があるかを検討するため、まず疾患遺伝子の相互作用(すなわちDGN)と既報の蛋白-蛋白相互作用マッピング(interactome)の結果を重ねてみた。その結果、DGNと蛋白相互作用マップの間で290の相互作用が重なっていた。これはランダムコントロールで予想される相互作用数(平均30程度)の10倍と大きいものであった(P<10^-6)(図3a)。
d0194774_12522545.gif

図3:DGNのモジュール形成
a :疾患遺伝子の蛋白産物間に見られる相互作用(赤矢印↓)は、ランダムコントロール(青)で予想される相互作用の数の分布に比べ非常に多い。
b:共通の疾患に関連する疾患遺伝子は組織均質性(赤)が高い(同じ遺伝子数のランダムコントロール(青)を比較のために示している)。
c:同じ疾患に対応する2つの疾患遺伝子ペアの発現プロファイルの相関係数(赤)のPCCの分布は、コントロール(青)に比べて高い方にシフトしている (P<10^-6)。
d:同じ疾患に関連するすべての遺伝子の発現プロファイル間の平均PCCは、コントロールに比べ、高値にシフトしている(P<10^-6)。


同じ疾患に関連する疾患遺伝子は、共通の機能的な特徴、すなわち共通の遺伝子オントロジー(Gene Ontology; GO)を共有していると思われる。実際、同一疾患においてGOの均質性はランダムコントロールに比べて大きかった(SI図8)。

疾患遺伝子の蛋白産物が共通の機能的モジュールに含まれるとき、同じ組織内に発現する傾向が強いはずである。実際、疾患の組織均質性係数という指標(マイクロアレイデータにある36組織の10,594遺伝子のデータセットの中で、特定の組織に発現している共通の疾患に属する遺伝子の最大の割合)を考えると(図3b)、疾患の68%が組織均質性を持っており、これはランダムコントロールで予想される51%に比べ有意に大きかった(P<10^-5)。

共通の機能的モジュールに含まれる疾患遺伝子は共発現する傾向があると思われる。図3cに示すように、同じ疾患に関連する2つの遺伝子の共発現プロファイルの相関係数(Pearson correlation coefficients, PCC)の分布は、ランダムコントロールのPCCに比べ高値にシフトしていた(P < 10^−6)。また図3dに示すように、全体の疾患に関与する2つの遺伝子ペアのPCCの平均もランダムコントロールに比べ高値にシフトしていた。図4dではPCCが約0.75を明らかなピークとする小さい分布の山を伴っていた。このピークは平均PCCが大きい約33疾患によるもので、Heinz体貧血(PCC=0.935)、Bethlem筋症(PCC=0.835)、球状赤血球症(PCC=0.656)などを含んでいた。

以上より、共通の疾患に関連する疾患遺伝子は、それらの蛋白産物が互いに相互作用し、同じ組織に共通して発現し、共発現のレベルが高く、同じGO用語に含まれる傾向がある。すなわち、疾患遺伝子にはモジュール構造が認められると考えられる。

疾患遺伝子のうち一部の「必須遺伝子」だけがネットワークの中心となっている
ヒトの疾患遺伝子がコードする蛋白は、他の蛋白との相互作用が特に多い、すなわちネットワーク上でハブを形成するものだろうか?この問題は、がんにおける蛋白-蛋白相互作用ネットワーク(interactome)において検討されてきたが、ヒト疾患全体においてはまだ明らかになっていない。図4aでは、疾患遺伝子はinteractomeの中でハブとなる蛋白をコードしている傾向があることを示している。疾患遺伝子がコードする蛋白は他の疾患関連でない蛋白に比べると、他の蛋白との相互作用が32%大きい、すなわちネットワーク内では頂点としての枝の数〈k〉が多かった。また、枝の数〈k〉の多い蛋白は少ない蛋白に比べると、疾患に関連する遺伝子によってコードされている傾向があった(P=1.6x10^-17)。
d0194774_12541357.jpg

図4 「必須遺伝子」(出生に必須で欠損すると致死になる遺伝子)のトポロジーにおける機能的役割
a:遺伝子がコードする蛋白が他の蛋白と相互作用する数(枝の数)〈k〉と、その中で疾患遺伝子が占める割合f。これによると、枝が多いすなわちハブであることと疾患遺伝子であることは相関があると「一見」思われる。
b:ヒト遺伝子のうち「必須遺伝子」(これが欠損すると致死、マウスで検討された遺伝子のヒトにおけるホモログ)と疾患遺伝子の重なりをベン図で表している。疾患遺伝子のうち、重なっている部分は「必須」である疾患遺伝子、緑の部分は「非必須疾患遺伝子」。
c:枝の数〈k〉の多い蛋白は少ない蛋白に比べると「必須遺伝子」によってコードされている傾向がある。
d:しかし、枝の数〈k〉と「非必須疾患遺伝子」のあいだには相関がない。すなわち、疾患遺伝子であっても、「必須遺伝子」でなければそれがコードする蛋白がハブを形成する傾向はない。
e:他の蛋白との共発現〈ρ〉が多いと、その蛋白が「必須遺伝子」によってコードされている傾向が強いが、
f:「非必須疾患遺伝子」によってコードされている傾向は多くない。
g:蛋白が発現している組織の数nTが多いと、その蛋白が「必須遺伝子」によってコードされている傾向が強いが、
h:「非必須疾患遺伝子」によってコードされている傾向は多くない。


ところがこの検討では、本当に重要な蛋白は発生に必須であり、もしその蛋白に変化があれば妊娠第一期に自然流産(または出生後すぐの死亡)を起こしてしまうという重要なことを無視しているのである。この問題は、マウスにおいて欠損すると胚性致死(または出生後致死)を示す遺伝子のヒトにおける相同な遺伝子(オルソログ)を調べることで乗り越えられる(マウスの致死性遺伝子はMouse Genome Informaticsに基づく)。この検討により、そのようにマウスで欠損させると致死になる遺伝子のヒトにおけるオルソログは1,267遺伝子あり、そのうち398遺伝子がヒト疾患関連遺伝子に含まれるものであった。ここでは、この1,267遺伝子を「必須遺伝子(essential gene=出生してくるのに必須という意味)」と呼び、OMIMにあった1,777の疾患遺伝子全体から「必須遺伝子」に含まれる398遺伝子を除いた1,379遺伝子を「非必須疾患遺伝子(non-essential disease gene)」と呼ぶことにする(図4bのベン図参照)。

疾患遺伝子のうち、「必須遺伝子」(図4bの重なり部分)と「非必須遺伝子」(図4bの緑色部分)はヒトのinteractomeにおいて非常に異なる役割を示していることが分かった。まず、疾患遺伝子のうちの「必須遺伝子」がコードする蛋白は、すべての疾患遺伝子がコードする蛋白に比べると、ハブを形成する傾向があった(図4c、P=1.3x10^-17)。そうすると、図4aで見られた「疾患遺伝子がコードする蛋白はハブを形成する」という傾向は、単に疾患遺伝子の22%(1,267遺伝子中396遺伝子)が「必須遺伝子でもある」ということによって起きているのか?驚いたことに、疾患遺伝子の多く(78%)を占める「非必須」遺伝子がコードする蛋白は全くハブを形成していなかった(図4d:非必須疾患遺伝子がコードする蛋白の枝の数〈k〉と、その蛋白が疾患遺伝子によってコードされているということの間に相関はない)。したがって、図4aに見られた疾患遺伝子がコードする蛋白がハブを形成するという傾向は、疾患遺伝子の中の少数の「必須遺伝子」によるものであった。

また、遺伝子発現パターンの同調(シンクロナイズ)について検討した。細胞の円滑な機能発揮のためには、いくつもの機能的モジュール活性を協調させて維持する必要がある。そのため、重要な遺伝子の発現パターンは同調していると考えられる。疾患遺伝子のうち「必須遺伝子」である遺伝子の発現パターンも多くの他の遺伝子の発現と同調しているだろう。このことを検討するため、平均遺伝子共発現係数〈ρ〉という測定値を考えた。これは、正常ヒト組織マイクロアレイの結果から、「必須遺伝子」(または「非必須疾患遺伝子」)iと細胞内の他のすべての遺伝子との間のPCCijを求め、合計して平均したもの〈ρ〉i=Σj PCCijである。予想どおり、他の遺伝子との高い平均共発現係数〈ρ〉を示す遺伝子は、低い〈ρ〉やマイナスの〈ρ〉を示す遺伝子よりも「必須遺伝子」であることが多かった(図4e、P=1.7x10^-4)。しかし、「非必須疾患遺伝子」は逆の傾向を示し、発現パターンが他の遺伝子と逆相関を示すか相関がない遺伝子と関連していた。図4fに示すように、発現が高度に同調した遺伝子(〈ρ〉 > 0.2)の中で「非必須疾患遺伝子」が占める割合は少なかった (P = 2.6 × 10^−8)。このように、「必須遺伝子」の発現は他の遺伝子の発現と同調しているが、「非必須疾患遺伝子」の発現は、他のすべての遺伝子の発現パターンから大きく外れているという傾向が見られた。

最後に、すべての組織で常に発現しているハウスキーピング遺伝子が疾患遺伝子になっている傾向があるかを検討した。図4gに見るように、遺伝子が発現している多くの組織が多いほど、その遺伝子が「必須遺伝子」である傾向があった(P=2.8x10^-16)。「非必須疾患遺伝子」においては図4hのようにその逆であり、少ない組織に発現している傾向が見られた(P=1.4x10^-6)。ハウスキーピング遺伝子のうちたった9.9%しか疾患遺伝子ではなく、これは非ハウスキーピング遺伝子の13.5%が疾患遺伝子ということに比べて有意に少ない(P=3.6x10^-6)。それに対し、マウスのハウスキーピング遺伝子の59.8%は「必須遺伝子」であり、これは非ハウスキーピング遺伝子で40.5%が「必須遺伝子」であったのに対し有意に多いP<10^-4)。
以上より、「非必須疾患遺伝子」はハブに関係しておらず、他の遺伝子の発現との同調が少なく、発現している組織も少ないという傾向が認められる。すなわち、「非必須疾患遺伝子」の多くはトポロジーにおいては機能的に「末梢を占めている」と言える。そしてそれとは対照的に、「必須遺伝子」はハブとなる蛋白をコードしていて、他の残りの遺伝子と強く同調して発現する。また、多くの組織で発現し、ハウスキーピング遺伝子の中で多くの比率を占めている。「必須遺伝子」はトポロジーにおいて機能的に「中心的」であると言える。

多くの疾患遺伝子が「末梢性」しか示さないという結果は意外であったが、これは進化の過程を考えに入れるとうまく説明できるだろう。もしトポロジカルに「中心的」な遺伝子に変異が起きると、それは広く発現しているため、正常の発生や生理的機能に強い障害を与え、その個体は発生早期に致死となってしまい集団からは除かれる。そのため、このような「中心的」な遺伝子の変異ではなく、生殖年齢まで生存できる変異だけが集団内で維持されるわけである。したがって、トポロジカルに「末梢にある」疾患関連の変異の方が生存のチャンスは大きくなる。

疾患遺伝子の変異が(遺伝的なものでなく)体細胞突然変異であれば、上記のような選択圧は受けないだろう。本当にそうかどうかを検討するため、Cancer Genome Censusに登録されているがんを起こす体細胞変異の特徴を検討した。その結果、がんで体細胞変異を起こしていたがん遺伝子はハブをコードしており、他の遺伝子と高い共発現を示し、ハウスキーピング遺伝子の中の多くの割合を占めていた(SI図10)。すなわち、体細胞変異を起こすがん遺伝子はトポロジカルに「中心的」であり、これは「多くのがん遺伝子は細胞の発生と成長に重要な役割を果たす」という我々の理解(例えばp53が細胞の生存や死に重要であるなどの知見)に合致するものである。
[PR]
by md345797 | 2014-06-16 12:57

複雑ネットワークの理論(5): 代謝ネットワークはスケールフリーかつモジュール性を持つ階層的ネットワーク

Hierarchical organization of modularity in metabolic networks.

Ravasz E, Somera AL, Mongru DA, Oltvai ZN, Barabási AL.

Science. 2002 Aug 30;297(5586):1551-5.

【論文内容】
ネットワークにおけるモジュール

モジュールは、システムの構成因子がある区別される領域にまとまって機能するものである。ネットワークはいくつかのモジュールに分けられることがあり、特に社会的なネットワークではモジュールはコミュニティと呼ばれる。このコミュニティの検出方法についてはさまざまな方法が考えられている。なお、ネットワークのモジュールは、単なるクラスター(頂点が三角形を作る構造)とは違うことに注意する。

スケールフリー性とモジュール性
生物における代謝ネットワークはスケールフリー・ネットワークであると考えられ、多数の反応に関わるハブとなる基質が少数存在するトポロジーを示している。このような従来のスケールフリー・ネットワーク(図1A)ではその定義上、分けて考えられるようなモジュールは存在しない。しかし、現実の代謝ネットワークでは生化学的にまとまって分けて考えられるような機能的モジュールが存在している。また、代謝ネットワークは、クラスター係数が高いネットワークであり、モジュールの存在を示唆するものである。したがって、いくつかのモジュールどうしが連結しているネットワーク(図1B)が想定できる。しかし逆に、このような明らかなモジュール性を持っていると頂点がほぼ同数の枝を持つようになり、ハブが出現せずスケールフリーにならなくなってしまう。
d0194774_21165818.jpg

図1:複雑ネットワークの3種類のモデル。いずれも左にシェーマ、右に256個の頂点を持つ典型的なネットワークの形態を示す。
A: スケールフリー・ネットワーク。新しい頂点は、もともと多くの枝を持つ頂点に連結するため、非常に多くの枝を持つ頂点(ハブ)ができる。モジュール性は少ない。B: モジュールが相互に連結したネットワーク。どの頂点もほぼ同じ数の枝を持ち、ハブは存在しない。C: 階層的ネットワーク。なお、図1C左側のグラフには元論文の間違いがある(後述赤字の注2参照)



代謝ネットワークは高い平均クラスター係数を持つ
では、実際の代謝ネットワークの性質はスケールフリーなのか、モジュール性なのか。この問題を検討するため、まず実際の43種類の生物の代謝ネットワークの平均クラスター係数を計算した。

◇クラスター係数とは:
ある頂点が作りうる範囲でどのくらいクラスター(その頂点を含む三角形の構造)を作っているかの割合である。図2A左の赤の頂点に連結している青の頂点の間がすべて直接連結されているときは、赤の頂点のクラスター係数をC=1(すべてクラスター化している)。右のように赤の頂点に連結している青の頂点どうしが直接連結していないときをC=0(クラスター構造はない。赤の頂点を介して連結しているだけ)とする。真ん中のように、青の頂点の間に実際ある枝(3本)を連結しうる枝の数(6本)で割ったものC=1/2が赤の頂点のクラスター係数になる。

一般的には、頂点iが枝をki本持つ、すなわちki個の頂点に隣接するとする。そうすると、それらのki個の頂点から2つ選んで連結してできうる枝の総数はki(ki-1)/2本である。ここで実際にはki個の頂点がn本の枝で連結されているとすると、頂点iを含むクラスター(頂点iを含む三角形)がn個あることになり、頂点iのクラスター係数Ciをn/[ ki(ki-1)/2]で定義する。頂点iのCiは、頂点iが作りうるクラスターのうち、どのくらいの割合で実際のクラスターができているかを表す。全部の頂点のクラスター係数の平均値を平均クラスター係数とする(注1)。平均クラスター係数は、ネットワーク全体でどのくらいクラスターが形成されているか、すなわち「ネットワークのモジュール化」の指標になる。

注1:グラフ理論では、上記の「頂点のクラスター係数Ci」を「クラスター度」といい、ネットワークの全部の頂点のクラスター度の平均のことを「クラスター係数」ということがあるので注意。

ここで、43種類の生物の代謝ネットワークにおける、頂点数Nと平均クラスター係数C(N)の関係を図2Bに示した。紫は古細菌、緑は細菌、青は真核生物を表し、頂点数Nのスケールフリー・ネットワークの平均クラスター係数にを白い◇で示した。同じNのスケールフリー・ネットワークと比べると、生物の代謝ネットワークは平均クラスター係数C(N)が大きい。したがって、現実の代謝ネットワークは、理論的なスケールフリー・ネットワークより高いモジュール性を持っていることが分かる。また、スケールフリー・ネットワークはその頂点数Nが大きくなるとN^-0.75にしたがって平均クラスター係数C(N)は小さくなる(頂点が増えるとクラスターを形成しにくくなる)が、生物の代謝ネットワークでは、その生物における頂点数(代謝産物の数)に関わらず平均クラスター係数C(N)は一定であった(モジュール化の程度はどの生物の代謝ネットワークも同じ)。
d0194774_2103799.jpg

図2 代謝ネットワークにおける階層的モジュール性
A: ある頂点(赤●)のクラスター係数Cの説明。左のように連結している頂点(青●)の間がすべて直接連結されているときはC=1(すべてクラスター化している)。右のように連結している頂点の間で直接連結していないときはC=0(クラスター化なし)。真ん中は、青●の間に実際ある枝(3本)を連結しうる枝の数(6本)で割ってC=1/2である。
B: 43種類の生物の代謝ネットワークの頂点数Nと平均クラスター係数C(N)の関係。古細菌(紫)、細菌(緑)、真核生物(青)のすべてでNの数に関わらず平均クラスター係数は同じ。頂点数と枝数が上記の生物と同じでフリースケール・ネットワークの場合のC(N)を◇、理論的な値を線で示したが、実際の生物でのC(N)はそれらより常に高い。
C-E: 古細菌A. aeolicus、細菌E. coli、真核生物S. cerevisiaeの代謝ネットワークの頂点における枝の数kとクラスター係数C(k)の関係は、いずれもベキ法則C(k)~k~^-1に従うという特徴がある。Fは43種類の生物全体での平均(小さい表示は合計)したものを表す。同じ頂点数・枝数の単なるフリースケール・ネットワークでは◇のようになり、ベキ法則には従わない。


「階層的ネットワーク」の提唱

生物の代謝ネットワークは、前に見たようにスケールフリー・ネットワークであると同時に、その頂点数に関係しない高い平均クラスター係数を持つモジュール性を示すことが分かった。しかし、この2つは明らかに矛盾することであり、これらの条件を満たす、代謝ネットワークの新しいモデルが必要になった。これが階層的モデル(hierarchical model)と呼ぶものである(図1c)。

例としてN個の頂点、ここでは4個の頂点がすべて互いに連結した小さい連結グラフをまず作る。これを1つのモジュールと考え、この周りに(N-1)つ、ここでは3つの同じものを複製し、それら複製グラフで外側にある3個の頂点を古いグラフの真ん中の頂点とそれぞれ連結する。これにより新しく4+4x3=16個の頂点を持つ連結グラフができたことになる。次に、この16個の頂点を1つのモジュールと考えて、周りに3つ同じものを複製し、外側の頂点をまた古いグラフの真ん中の頂点と連結する。これを繰り返すと頂点の数は4倍ずつ増加する(注2)。

注2: 図1Cの左図は、上記の説明では連結がないはずの周囲の3つの連結グラフの中心どうしが連結しており、元論文の間違いではないか?正しい図が『複雑ネットワーク 基礎から応用まで』(増田直紀、今野紀雄・近代科学社)の「図6.11ラヴァスの階層的モデル」に掲載されていたため、以下に引用させていただいた。
d0194774_2111384.jpg

これは、スケールフリー・ネットワークであり(ハブがあり、新しい頂点が選択的にハブに連結する)、かつモジュール構造を持つネットワークになる。スケールフリー性のベキ指数はγ=1+(ln 4)/(ln 3)=2.26、クラスター係数は頂点数に関わらずC≃0.6となり、いずれも実際の代謝ネットワークに近い。また、このネットワークは繰り返し4倍になっていくことから、階層的である。このような階層では、頂点がk本の枝を持つとき、頂点のクラスター係数はベキ法則C(k)~k^-1に従って減少することが分かっている(Drogovtsev, 2002)。

実際、43種の生物の代謝ネットワークのC(k)が、上のような1/k法則に従うかを検討した。図2C-Fに示すようにC(k)~k^-1であり、これらの代謝ネットワークは階層的ネットワークの特徴を示すことが示された。このように階層的ネットワークは、スケールフリー性のあるトポロジー、頂点数によらない高いクラスター係数、C(k)がベキ法則に従うという性質を併せ持っている。

ネットワークの中にあるモジュールを発見する
ここから、E. coliのネットワークをグラフ理論に基づいて検討することとした。先にネットワークのトポロジカル・オーバーラップ行列O_T(i, j)を求めることにより、モジュールを発見する方法について述べる。

◇トポロジカル・オーバーラップとは:
頂点iと頂点jがあるとき、トポロジカル・オーバーラップO_T(I, j)とは、「iとjのどちらも連結している頂点の数」を「iとjの枝の本数の少ない方」で割ったもの。この数が多い方と、頂点iと頂点jが同じモジュールにある度合いが高いと言える(図3A)。

頂点iとjの間でトポロジカル・オーバーラップが1というのはiとjがすべて同じ頂点に連結していることを表し、0はiとjが共通の頂点に連結していないことを表す。2つの頂点からの連結が共通の頂点を通じてオーバーラップしているかどうかということである。高度に連結したモジュールに含まれる頂点は、隣接する頂点とトポロジカル・オーバーラップが大きい。代謝ネットワークにおいては2つの基質のトポロジカル・オーバーラップが大きいほど、同じモジュールに属する可能性が高いと言える。そのため、この2頂点を行列表示したトポロジカル・オーバーラップ行列はモジュールの発見に有用である。
d0194774_19364968.jpg

図3:トポロジカル・オーバーラップを求めることによりモジュールを発見する
A. 小さいネットワークの例を示す。2つの頂点iとjにおいて、トポロジカル・オーバーラップは次のように定義される。
d0194774_3575750.gif

ここで、J_n(i, j)はiとjが連結している頂点の数を表す(もしiとjの間に直接連結があれば1を加える)。[min (ki, kj)]は頂点iの枝の数kiと頂点jの枝の数kjのうち小さい方を表す。すべての枝の上の赤字は連結された2頂点のトポロジカル・オーバーラップを表し、頂点の横にあるカッコはその頂点のクラスター係数を表している。なお、原論文の図ではCのクラスター係数が(3)となっておりミスプリントであったので、引用の際(1/3)に改変した。

B: Aで示したネットワークのトポロジカル・オーバーラップ行列。行と列は階層的クラスタリングアルゴリズム(Eisen MB, et al. PNAS, 1998)を用いて頂点を並べ替え、連結のオーバーラップが大きい頂点どうしを近くに配置するようにした。色は、頂点間のオーバーラップの度合いを表示したもの。これにより、赤~茶色にかけてのモジュールが3個あることが分かる。
また、上と右につけた樹状図は3つのモジュールを表しており、EFGとHIJKは、ABCよりもトポロジー的にお互い近いことを表す。なお、図3Aの頂点ABCDの赤色とHIJKの青色が図3Bでは原論文のミスで逆になっているので注意。


実際の代謝ネットワークにおけるモジュールの同定
図4Aは、E. coliの代謝ネットワークのトポロジーを、図3Bと同様のトポロジカル・オーバーラップ行列で表したものである。これによると、強固に相互連結したモジュール(行列の赤色の部分)がいくつも形成されているのが分かる。これを拡大して見るとサイズが大きく相互連結が少ない入れ子になった(nested=フラクタルのように拡大しても自己相似形がある)モジュールの階層が認められた。

ここで明らかになったネットワークにおけるモジュールと、代謝産物の生化学的特性との間の関係を視覚化するために、行列の上と右に代謝産物の階層木(hierarchical tree)を表示した。これらは生化学的分類を用いて色分けしている。その結果、小分子の種類ごと(代謝パスウェイごと)にだいたい同じ木の枝に分布しており、これを圧縮して三次元表示した図4Bでは代謝ネットワークの区切られた領域に対応して分布していた。以上よりE. coli代謝ネットワークにおいて、今回階層的モデルから得られたトポロジカルな構成は、実際の代謝産物の生化学的分類と強い相関があることが分かる。
d0194774_2144257.jpg

図4:E. coliの代謝ネットワークにおけるモジュールの同定
A:E. coliの代謝ネットワークに対応するトポロジカル・オーバーラップ行列(中央)、モジュール間の関係を表す階層木(行列の上と右)。階層木の色は行列の下にあるように、炭水化物(青)、核酸代謝(赤)、蛋白・アミノ酸代謝(緑)、脂質代謝(水色)、芳香族代謝(濃いピンク)、モノカルボニル化合物代謝(黄色)、コエンザイム代謝(薄いオレンジ色)で色分けしている。
B:代謝ネットワークの3次元構成。各頂点の色はAで示した通り。薄い青で囲んだ部分はピリミジン代謝に関わるモジュール。
C:ピリミジン代謝のモジュールを拡大し階層木にしたもの。全体が3段階のモジュールの入れ子構造になっており、1段階目を水色、2段階目を薄いオレンジ色で表している。
D:ピリミジン代謝モジュールとその周囲の代謝産物のグラフ。赤はCで示されたピリミジン代謝のモジュールに含まれる代謝産物。緑はピリミジン代謝パスウェイにあるが、非分岐点や分岐の経路の終末点にあたるためCには表示されていない代謝産物。青と黒はピリミジン代謝から他の代謝経路に連結する代謝産物で、黒は他の代謝経路の枝に属する主要な代謝産物、青は分岐しない代謝産物。矢印は反応方向、番号はその反応を触媒する酵素を表す。


上記のようにグラフ理論を用いて、実際の生化学的パスウェイにおけるモジュールを見出しうるかを、ピリミジン代謝パスウェイに絞って検討することにした。代謝ネットワークを階層的ネットワークと考えると、ピリミジン代謝は図4Bの薄い青色で囲んだ領域にトポロジカルに限定され、図4Cに示すような4つのモジュールから構成されていた(4つのモジュールもさらに小さいモジュールからなるという、入れ子構造になっている)。また、実際の代謝経路は図4Dのグラフで示したものである。ここから、赤い四角で囲まれた代謝産物によって構成されたモジュールを発見するのが上記の方法である。

なお、階層的ネットワークにおけるモジュールの境界は直観的に分かる生化学に基づく境界と常に一致するとは限らない。例えば、L-glutamineからのuridine 5’-monophosphate (UMP)の合成は直線的な生化学反応のモジュールに含まれるが、UMPからのuridine 5’-diphosphateの合成はモジュールの境界を越えていた。このようにまだ明らかなモジュールとして分からないところもあり、代謝ネットワークにおけるモジュールの理解のためには、さらなる実験的および理論的解析が必要なのだろう。

まとめと今後の展望
以上のように代謝ネットワークの構造は、階層的ネットワークモデルとつなぎ目なく埋め込まれたモジュールによって表されることが明らかになった。代謝ネットワークは、従来の直観的に分かるようなモジュール性(図1B)、すなわちいくつかの隔離したモジュールが少ない枝を介して連結しているモデルではなく、小さいモジュールがグループを形成して大きなモジュールを形成し、それが集まってさらに大きなモジュールになるというモデルで表される。この構造は図4Aにある階層的木によっても視覚的に理解でき、逆向きに代謝ネットワークをいくつかの大きい統合のゆるいモジュールに分け、それをさらに小さい統合の強いサブモジュールに分けていくことが可能になる。

なお、上記の階層的ネットワークとモジュール性によるネットワークの理解は、代謝ネットワークのみならず、他の細胞内ネットワーク(遺伝子ネットワーク、蛋白相互作用ネットワーク)や社会的ネットワーク(WWW、インターネットのネットワーク)にも応用可能だろう。また、生態系は複数のレベルで進化が同時に起きる現象があるが、これも生態系ネットワークのモジュール性で説明可能かもしれない。ある局所的な変化が起きると高度に統合された小さいモジュールがまず変化し、それがゆるく統合した大きいモジュールにゆっくり影響を与えることによるのだろう(そもそもモジュールとは、局所的な構成要素の変化が起きても、その変化が他の構成要素に及ぼす影響が最小限ですむように、小規模のグループを構成していることでもある)。また、階層的トポロジーはすでにあるモジュールをコピーしたり再利用したりして創発する(図1C)。そのため、ネットワークに最初にモジュールが現れるメカニズムやその後に階層的およびスケールフリーのトポロジーが同時に出現する進化的メカニズムの理解が、今後のネットワーク理論の重要な課題となるだろう。
[PR]
by md345797 | 2014-06-10 21:07

複雑ネットワークの理論(4) 細胞内代謝パスウェイはスケールフリー・ネットワークである

The large-scale organization of metabolic networks.

Jeong H, Tombor B, Albert R, Oltvai ZN, Barabási AL.

Nature. 2000 Oct 5;407(6804):651-4.

【まとめ】
43種類の生物(古細菌、細菌、真核生物)の細胞内代謝ネットワークを、酵素反応の基質を「頂点」、反応を「枝」で表したネットワークと考えたところ、これらの代謝ネットワークは、生物種によらずスケールフリー・ネットワークの特徴を示したことを報告する。これにより、細胞の代謝ネットワークが示す頑健でエラー耐性があるという特徴は、それがスケールフリー・ネットワークであることに基づくと考えられる。

【論文内容】
生命現象の過程に見られる頑健性(robustness)は、蛋白、DNA、RNA、小分子などといった構成要素の動的な相互作用による。この相互作用は極めて複雑なネットワークであるが、それを複雑系(complex system)としてとらえることが可能になりつつある。複雑系は以前より、古典的なランダムネットワーク理論(Erdös–Rényiモデル)で考えられてきた。これは、構成要素を頂点とし、それらがある確率pをもってランダムに連結されたグラフである。このネットワークは図1aのようなものであるが、その結合性は図1bで表されるような均一なポアソン分布となる。すなわち、頂点から出る枝の数kは平均値〈k〉をピークとして、その確率分布P(k)は指数関数的に減少する。

一方、World-Wide Webやインターネットなどが示す現実のネットワーク(図1c)は、このようなランダムな構造ではなく、P(k)がベキ法則(power-law)で減少するスケールフリー・ネットワークである。スケールフリー・ネットワークは、非常に多い数の枝を持つ少数の頂点(ハブ)と枝の数が少ない大多数の頂点からなるという、極めて不均一なトポロジーを示すネットワークである。これは、少しずつ頂点が加わっていくというネットワークの「成長」と、新しい頂点がハブに優先的に結合するという「優先的選択」によって形成されることが分かっている。
d0194774_17205150.jpg

図1 2種類のネットワーク構造の特徴
a, 指数関数的(Exponential)ネットワーク。ランダムネットワーク、Erdös–Rényi モデルとも呼ばれる。b, ネットワークの頂点がk本の枝を持つ確率はP(k)は平均値〈k〉をピークに指数関数的に減少する。そのため、枝の数が極端に大きい頂点は存在しない。c, フリースケール(Scale-free)ネットワーク。「ハブ」と呼ばれる、枝の数が極端に大きい頂点(灰色の●)が少数存在する。d, スケールフリー・ネットワークでは、P(k)はピークを持たず、ベキ法則に従って減少する。P(k) ≈ K^-γであり、これは両対数グラフで傾きが-γの直線で表される。e, E. coliの代謝反応の一部をグラフ理論で表示したもの。このグラフにおいて頂点(四角で囲まれた部分)は酵素反応における基質である。いくつかの基質(educt)が複合体を作り、酵素によって反応を起こし、産物(products)となる。productはさらなる酵素反応のeductになっている。酵素反応はこれらの頂点を結ぶ枝であり、その反応をつかさどる酵素はEC番号で表示されている。


細胞ネットワークの大規模構造を理解する手始めとして、43種の生物の主要代謝ネットワークのトポロジー特性を検討した。ここでは、代謝パスウェイとゲノムの統合データベースであるWIT databaseを用いた。代謝ネットワークにおける反応は、図1eのようなグラフで表した。ここでは酵素反応の基質が頂点で、酵素反応が枝、代謝をつかさどる酵素がEC番号で表示されている。さまざまな代謝ネットワークをこのようなグラフで表すことにより、グラフ理論と統計学を用いてそのトポロジー特性を検討したり定量化したりすることが可能になる。

代謝ネットワークは、ランダムで均質な指数関数的モデルと、非均質なスケールフリーモデルのどちらで表されるのだろうか?結果は図2に示すように、酵素の基質(頂点)がk個の酵素反応(枝の本数がk本)である確率はベキ法則P(k) ≈ K^-γに従っていた(図2のa、b、cはそれぞれ古細菌、細菌、真核生物の代表例、dは43種すべての平均)。すなわち、代謝ネットワークはスケールフリー・ネットワークであった。頂点あたりの枝の数kは、頂点に入ってくる枝と出ていく枝でそれぞれk_inとk_outと表わされ、それぞれのベキ指数γ_inとγ_outはいずれも2.2であった。
d0194774_1718994.jpg

図2 さまざまな生物の代謝ネットワークの結合性分布
a: 古細菌(Archaeoglobus fulgidus)、b: 細菌(E. coli)、c: 真核生物(C. elegans)。代謝における酵素反応の基質を頂点とし、酵素反応を枝としたとき、頂点あたりの枝の数kと、その枝数をもつ確率P(k)の関係を両対数グラフで表したもの。Inは頂点に入ってくる枝、Outは頂点から出ていく枝についてkの確率分布を表している。a、b、cのいずれも、両対数グラフでマイナスの傾きを持つ直線で表されるため、P(k)がベキ法則に従っていることが分かる。dは、検討した43生物のすべての結合性分布の平均を表す。


多くの複雑ネットワークでは、2つの頂点は比較的短い距離(=少数の枝の数)で連結されている。このようなネットワークをスモールワールドであるという。図3aはE. coliの代謝ネットワークがスモールワールドであることを表すヒストグラムである。図3aの横軸は、E. coli代謝ネットワークの2頂点間の距離(2つの頂点が最短でいくつの枝で連結されているか、lはpathway length)、縦軸は任意の頂点間の距離の頻度Π(l)を示す。これによると頂点間の距離は3であることが最も多く、代謝ネットワークはスモールワールドであることが分かる。

また、2頂点の最短距離を全部の頂点間で平均したもの(グラフ理論における平均距離)を、ここではネットワークの直径(diameter)と呼ぶ。直径が小さい方が、ネットワーク内の伝達が速いことになる。単純な細菌(例えばMycoplasma genitalium)に比べるとより複雑な細菌(E. coli)は酵素や基質が多い(頂点や枝が多い)のだから、代謝ネットワークの直径は大きくなるように思われる。ところが図3bに示したように、43種類の生物すべてで代謝ネットワークの直径は同じであった(大体3程度)。この結果は予想外であったが、生物が複雑になり頂点数が増加しても、その分連結も増加するのであれば、2頂点間の経路は増大せず、ネットワークの直径は一定になりうる(頂点数が増えてもその分経路も増えれば、頂点から頂点への行きやすさは全体的にあまり変わらないということ)。実際、図3cとdで見るように、生物が複雑になって酵素反応の基質の種類(頂点の数 N)が増加すると、基質あたりの反応数(頂点あたりの枝の数 L/N)が増加していることが分かる。なお、cは入ってくる枝、dは出ていく枝であり、赤が古細菌、緑が細菌、青が真核生物での結果を示している。
d0194774_17163969.jpg

図3 生物種によらず、代謝ネットワークの直径は一定である
a, E. coliの代謝ネットワークで、代謝産物を頂点としたときの2頂点間の距離(最短経路、pathway lengthのl)のヒストグラム。縦軸のΠ(l)は、任意の2つの頂点がlの距離を取る頻度を表す。これによると頂点間の距離は3であることが最も多く、代謝ネットワークはスモールワールドであることが分かる。 b, 43種類の生物の代謝ネットワークの平均距離 (直径)。エラーバーは標準偏差σであり、aの説明にあるΠ(l)により求められたlを用いて〈l^2〉-〈l〉^2で近似される。ネットワークの頂点数Nが大きくなっても、ネットワークの直径dは変わらない。c, d,生物が複雑になって酵素反応の基質の種類(頂点の数 N)が増加すると、基質あたりの反応数の平均(頂点あたりの枝の数の平均 L/N)が増加することが分かる。cは入ってくる枝、dは出ていく枝についてであり、赤は古細菌、緑は細菌、青は真核生物。e, E. coliの代謝ネットワークから基質を除外した場合の直径に及ぼす影響。赤は枝の多い頂点(関わる酵素反応が多い基質)から順に除外した場合、緑はランダムに頂点を除外した場合。除外する頂点数M=60で、代謝に見られる基質の約8%を除外したことに相当する。f, 43種の生物の代謝ネットワークにある基質のうち、平均のランク順〈r〉とその標準偏差σの関係。ランクが高い(横軸で数値が小さい)基質は、普遍的に多くの生物で用いられており、その基質のランクは生物間のばらつきが少ない。


スケールフリー・ネットワークは、少数のハブによってネットワーク全体の結合が保たれているので、ハブが外部から攻撃されたときはネットワークは脆弱である。枝の数が多い頂点(大きなハブ)から順番に取り除いていくと、ネットワークの直径が急速に増加し(=結合性が弱くなり)、非連結のクラスターに分解されてしまう。しかしその一方で、スケールフリー・ネットワークにはハブが存在するそのことにより、ランダムに起きるネットワークのエラーには予想外の頑健性を示す。

そこで、E. coliの代謝ネットワークにも、このような「攻撃に対する脆弱性とエラーに対する耐性」が見られるかをコンピュータ・シミュレーションで検討した。図3eの赤い△のように、最も多く連結している頂点(基質)から順に除外していくと、代謝ネットワークの直径は急速に増加した(Mは除外する基質数、横軸右に行くにしたがい徐々にはハブを除外)。しかし、緑の□のようにランダムに基質を除外していっても、ネットワークの直径は変わらない。仮にランダムな酵素の変異が起きていくつかの基質ができなくなったとしても、これによってネットワークの連結性はほとんど影響を受けないことが分かる。なお、ここでハブとなる基質はごく少数なので、ランダムに起きる酵素の変異によってハブが消失する確率は非常に低いのだろう。このようなE. coli代謝ネットワークの変異に対する耐性は、in silicoin vivoで変異を起こす研究で詳細に検討されている (Edwards JS, PNAS 2000)。なお本研究では、43種類の生物すべてに同様のエラー耐性が認められた。

代謝ネットワークの大規模構造の特性はネットワークがハブを持つことによると考えられるが、全生物で同じ基質がハブとして働いているのか、それともハブは生物ごとに違いがあるのか?これを検討したところ、43の生物でハブとして働く基質のランキングは事実上同じ(論文のsupplementary Table 1)であった。43の生物で認められる全種類の基質の中で、ハブとなる基質は4%のみである。すなわち、生物はごく少数の基質を普遍的に利用していることが分かる。一方、生物に特異的な違いの見られる基質は、反応の枝の数が少ない。これを定量的に表すために、43の生物で認められた基質ランキングr の標準偏差σ(r)を図3fに示した。ハブとなる基質のランク順の平均〈r〉が大きくなるほど、σ(r)が大きくなっており、これは基質としての利用ランクが高いもの(〈r〉が小さいもの)ほど生物間のばらつきが少ない(σが小さい)ことを表している。以上より、43の生物種の代謝ネットワークにおいて、多くの枝を持つ頂点は生物間で普遍的に用いられており、枝の少ない頂点は生物によってばらつきがある。

生物が現在示す代謝ネットワークのトポロジーは、内部からのエラーと外部からの攪乱に対する頑健性や、ある特定の生物が環境のニッチに占めるための特性を得るために長い進化の過程において獲得してきたものと思われる。その結果、このようなネットワークはランダムなものではなく、頑健性とエラー耐性を持つスケールフリー・ネットワークになったのだろう。また、ここで検討したすべての生物でネットワークの直径は同じであり、これも進化の過程で保存されたものなのだろう。もし直径がもっと大きいと内的エラーや外的変化に効率よく対応できず、生存に不利だったのかもしれない。また、スケールフリー・ネットワークは他の細胞内ネットワーク(例えば、アポトーシスや細胞周期ネットワーク)に普遍的に存在するものだろうか?現時点では代謝以外のネットワークは分かっている頂点数や枝の数がまだ小さいので、本研究のように数学的ツールで統計学的に解析するのは難しい。しかし、代謝経路以外の細胞内ネットワークでも結合性の分布がベキ法則に従うことが予想され、上記のようなスケールフリー・ネットワークになっている可能性を今後検討したい。
[PR]
by md345797 | 2014-06-08 17:23

複雑ネットワークの理論(3) エラーに対する耐性と攻撃に対する脆弱性

Error and attack tolerance of complex networks.

Albert R, Jeong H, Barabasi AL.

Nature. 2000 Jul 27;406(6794):378-82

【まとめ】
多くの複雑ネットワークは、ネットワーク内にランダムに起こるエラーに対して驚くべき耐性を持っている。例えば細胞は内部のさまざまな変化が起きても、成長し繁殖することができる。これは代謝ネットワークの根底にある頑健性(robustness)というエラー耐性があるためだろう。社会的なコミュニケーションネットワーク、すなわちインターネットやWorld-Wide Webにも驚くべきエラー耐性があり、部分的な異常を定期的に起こしてもそれがネットワーク全体の情報伝達能力に影響することはほとんどない。このような複雑ネットワークの安定性はネットワークに内在する冗長な結合によるものであるが、エラー耐性はすべての冗長なシステムに見られるのではなく、スケールフリー・ネットワークと呼ばれる、枝が非常に多い少数の頂点を持つ不均質なネットワークでのみ見られることを示す。このネットワークはしかし、枝の多い頂点を狙った攻撃を受けると、ネットワークの結合性を維持することが決定的にできなくなることがある。すなわち、スケールフリー・ネットワークにおいては、高いエラー耐性を示すことは同時に、攻撃に対しては非常に脆弱であることでもある。現実の社会的、生物学的ネットワークの多くはスケールフリー・ネットワークであり、エラー耐性と攻撃に対する脆弱性という2つの普遍的な性質を示すものと考えられる。

【論文内容】
(1) 指数関数的ネットワークとスケールフリー・ネットワーク
大きなネットワークの形すなわちトポロジーのデータが集まるようになり、近年それらのネットワークの普遍的な構造や成長過程についての理解が急速に進んでいる。今までに分かっている複雑ネットワークの形は、連結性の分布(注1)に基づいて大きく2つのグループに分類できる。
注1:頂点から出る枝の数kの確率P(k)が示す確率分布。

第一のネットワークのグループは、P(k)がkの平均値〈k〉でピークを持ち、kが大きくまたは小さくなるP(k)は指数関数的に小さくなるものである。これを指数関数的(exponential)なネットワークと呼ぶ。このようなネットワークの例は、エルデシュが提唱したランダムグラフ (Erdös–Rényi (ER) model) とスモールワールドネットワーク (Watts-Strogatz (WS) model)である(注2)。どちらもすべての頂点が平均〈k〉に近い数の枝を持っている、ランダムで均質なネットワークである。
注2:「ランダムネットワーク」というと上記のERモデルのみを指すことがあるため、論文ではERモデルとWSモデルを合わせて「指数関数的ネットワーク」としている。

それに対し、World-Wide Web (WWW)のような大きなネットワークは、第二のグループであるスケールフリー(scale-free)ネットワークと呼ばれる不均質なネットワークに属する。そこではP(k)の分布はベキ法則(power law)、すなわちP(k)~k^-γに従い、特徴的なスケールがない(平均値や分散などの尺度を表す数値が存在しない)。このスケールフリー・ネットワークでは、均質なネットワークでは決して見られない、非常に多くの枝(k≫〈k〉)を持つ頂点、すなわちハブがある程度存在する。
d0194774_0124917.jpg

図1 指数関数的ネットワーク(a)とスケールフリー・ネットワーク(b) どちらも頂点数130、枝数215であるが、ネットワークの形はまるで違う。
a:指数関数的(exponential)ネットワーク。頂点が持つ枝の数の確立P(k)は〈k〉=3.3をピークとして、指数関数的に減少する。その分布がランダムであることから、「均質な」ネットワークと言える。
b:不均質な性質を持つスケールフリー(scale-free)ネットワーク。大多数の頂点は1-2本の枝しか持たないのに、いくつかの頂点は非常に大きい数の枝を持つ(ハブが存在する)。
aもbもネットワーク内で枝の数が最も多い頂点の上位5個を赤で示し、それと1本の枝で連結している頂点を緑で示した。その結果、aでは全体の27%の頂点しか緑色でないなのに、bでは60%もの頂点が緑色である。すなわち、bはaと違って、ハブを介して多くの頂点が連結していることがわかる。この図はネットワーク解析ソフトPajekを用いて作成した。


(2)ネットワークの直径
ネットワークの相互連結性は、そのネットワークにある頂点間の最短経路の距離の平均で表され、これをそのネットワークの平均距離、または直径d(diameter)と呼ぶ。dが小さいネットワークはすべての頂点間の距離が平均して小さいと考えられる(注3)。頂点数が非常に大きいネットワークでも、そのネットワークの直径は意外と小さく、8億以上のドキュメント(頂点)がリンク(枝)でつながっているWWWでは約19、地球上の60億人以上の社会的ネットワークでも約6とされている。
注3:ここでの定義は上記のように、直径d=ネットワークの平均距離。グラフ理論では、すべての2頂点間の距離の「最大のもの」を直径と呼ぶことがある。いずれにしろ、直径が小さいということはその集団は伝達が速いことを示している。

(3) ネットワークのエラーとそれに対する耐性
ここで、同じ頂点数、同じ枝数を持つ指数関数的ネットワークとスケール・フリーネットワークのエラー耐性について検討する。ネットワークの「エラー」とは、あるネットワーク内の頂点がランダムに機能不全になって、ネットワークから除外される(消失する)ことを指す。頂点が除外されると、その頂点を介する経路がなくってしまうことになるので、残った頂点間の平均直径は一般に増加する。すなわち、dが増加し、ネットワークの相互連結性は減少すると考えられる。ここで、消失する頂点の割合をfとし、頂点が徐々に消失していったときの、fに対するネットワークの直径dの変化について検討した。

図2aのように指数関数的ネットワーク(E)では、消失する頂点の割合fが増えるとネットワークの直径dは一定の割合で増加した(図2aの青い△)。頂点は別の頂点を介して連結をもっているにもかかわらず、頂点が消失していくと、残った頂点どうしが互いの交通を維持するのは徐々に困難になる、ということである。指数関数的ネットワークでは、すべての頂点がほぼ平均した数の枝をもっているので、それぞれの枝がネットワークの直径に及ぼす影響は同じと言える。そのため、どの頂点が除かれても、ネットワークに与える障害の程度は同じになる。

それに対し、スケールフリー・ネットワーク(SF)は、点の消失に対するdの変化は全く異なっていた。すなわち、頂点がランダムに消失していっても、ネットワークの直径dは変わらなかった(図2aの青い□)。5%の頂点が消失しても、ネットワークに残った頂点どうしの交通には影響が見られない。スケールフリー・ネットワークのの連結は、ベキ法則に従う分布のため、ごく少ない枝しか持たない頂点が大多数を占めており、ランダムに頂点が消失する場合このような「小さい」頂点が消失する確率が大きいので、残った頂点間の経路に与える影響はほとんどなく、ネットワーク全体のトポロジーは全く変わらないといってもよい。
d0194774_0145870.jpg

図2 ネットワークの頂点が除外されたときのネットワーク全体の結合性
全体のfの割合の頂点がランダムに除外された場合、ネットワークの平均距離(直径d)がどのように変化するかを、指数関数的ネットワーク(E)とスケールフリー・ネットワーク(SF)で比較した。2つのネットワークはどちらも10,000個の頂点と20,000本の枝からなっている。
a:除外される頂点の割合fを横軸に、そのときのネットワークの直径dを縦軸に示した。すなわち、ネットワーク内部のエラーが全体の相互連結性にどう影響するかを示す。青色は、ネットワークから頂点がランダムに除外される「ネットワークにエラーが起きている状態」を表している。指数関数的ネットワーク(青い△)ではfが増加するとdも直線的に増加するが、スケールフリー・ネットワーク(青い□)ではfが増加してもdは変わらない。
赤色は、すべての頂点のうち「枝の多い頂点」を故意に狙って攻撃された場合を示している。すなわち、枝の多い順に頂点が除外されていくと、指数関数的ネットワークでは、ランダムに除外された場合と同じようにdが直線的に増加するだけだが(赤い◇)、スケールフリー・ネットワークでは急速にdが増加する(赤い○)。これは、スケールフリー・ネットワークはハブを狙った攻撃を受けると急速にネットワークの相互連結性が低下することを示している。
b、c:インターネット(b)やWWW(c)がランダムなエラーまたはハブを狙った攻撃を受けた時の、頂点の消失の割合fとネットワークの直径dの関係。ランダムなエラーの場合は直径は変わらないが、攻撃を受けたときは急速にdが増加する(相互連結性が低下する)。すなわち、インターネットもWWWも、エラー耐性と同時に攻撃に対する脆弱性を示す。


(4)ネットワークへの攻撃とそれに対する脆弱性
次に、ネットワークに故意に障害を与えようとする情報に通じた外部者(informed agent)がいるとする。そういう外部者は、どこでもいいからランダムに頂点を攻撃するのではなく、わざと枝の多い頂点(ハブ)を狙って攻撃してくるだろう。この状況をシミュレーションするため、枝の数が最も多い頂点をまず取り除き、それから枝の数kが大きい順に頂点を除外していくことにした。このように外部からの故意の「攻撃」を受けた場合、指数関数的ネットワークではランダムに頂点が消失した場合と同じようなdの増加しか見られなかった(図2aの赤い◇)。一方、スケールフリー・ネットワークでは最も枝の数が多い頂点が除外されると、ネットワークの直径dは急速に増加し、5%の頂点が枝の数順に除外されるとdは2倍に増加した。dの増加は、残った頂点間の交通が少なくなり、ネットワークの相互連結性が低下していることを表す。すなわち、スケールフリー・ネットワークはハブを狙った攻撃に対しては脆弱なのであり、この脆弱性は、ネットワークの結合が少数の枝の多い頂点によって維持されている(図1b)というまさにその本質的な性質によるものである。

(5) 2つのネットワークにおける、エラーと攻撃に対するクラスター断片化反応
頂点がネットワークから除外されると、その頂点が持つ枝も消失するため、その枝によって連結されていたクラスターがばらばらに断片化するかもしれない。ここでは、ネットワークにおけるエラーと攻撃の被害をより深く理解するため、このクラスター断片化の過程について検討する。

・ここでも、頂点がエラーまたは攻撃によって除外される割合をfとする。また、ネットワークの中で最大のクラスターの大きさ(ネットワーク全体の頂点数に対するクラスターに含まれる頂点数の割合)をSとする。fが0のときは、「ネットワーク全体が1つのクラスター」であるからS=1である。そして、クラスターがまったく存在しなくなったときがS=0である。さらに、メインのクラスター以外のすべてのクラスターの平均サイズ(含まれる頂点の数)を〈s〉で表す。Sは頂点総数に対する割合なので0~1、〈s〉はクラスターのサイズ(頂点の個数)なので1以上の数値を取る。Sと〈s〉では意味合いが違うが、図3では同じ縦軸で表しているので注意。

・さて、指数関数的ネットワークでランダムな頂点の除外(エラー)が起きると、fがある閾値(fc=0.28)を超えて大きくなったときに、メインのクラスターは完全に断片化し、Sはほぼ0となった(図3aの青い□)。その過程で、メインのクラスター以外のすべてのクラスターの平均サイズ s は、fが閾値fcに近づくにつれて急速に増加して2に近づき、その後1まで減少した(図3aの青い■)。すなわち、fが小さいときは頂点が一つ一つ除外されても、メインクラスター以外のクラスターの平均サイズ s はほぼ1である。このネットワークにはもともとあまりクラスターがなく、頂点数1のクラスターすなわちクラスターを作らない単独の頂点が非常に多いと考えられる。ここで、fが増加してくると、最大のクラスターの断片化が大きくなる。fが閾値fcになると最大のクラスターはばらばらの断片となる(Sはほぼ0)。残ったクラスターの大きさ s はこのときにピークとなる(2個程度でクラスターを作っている頂点の割合が多くなる)。さらに頂点が除外され続けてfが閾値fcよりも大きくなると、残ったそれぞれのクラスターも断片化してしまい、 s は1まで減少する。

・しかし、スケールフリー・ネットワークでランダムに頂点が除外されたエラーの場合のネットワークの振る舞いは、それとは異なっていた(図3b)。まず、fが大きくなってくると、最大のクラスターのサイズSは徐々に減少する。しかし、fが大きくなっても s はほぼ1で一定であり、ネットワークから一つ一つ頂点が除外されていっても、メインクラスター以外にはほとんど影響がないことが分かる。(ハブによって強く連結しているメインクラスターが非常に大きく、それ以外は頂点数1の断片がわずかに存在するためであろう。) 指数関数的ネットワークはfが大きくなるとある閾値fcにおいて破局的な断片化を起こすのに対して、スケールフリー・ネットワークはfが大きくなってもメインのクラスターを十分維持することができる(図3bの青い□)。ここでは頂点の除外はランダムに起こるため、ハブとなる頂点が直撃を受ける確率は非常に低い。そのため、メインのクラスターが完全に収縮するまでは、ネットワーク全体は断片化されないだろう。このように、スケールフリー・ネットワークは、ランダムなエラーに対するトポロジーの安定性が、指数関数的ネットワークに比べるとはるかに優れているということができる。

・次に、2つのネットワークが「枝の数が多い頂点」を選んで枝の多い順に攻撃された場合を示す。指数関数ネットワークが攻撃を受けた場合のネットワークの断片化反応(図3aの赤い○と●)と、スケールフリー・ネットワーク攻撃を受けた場合の反応(図3bの赤い○と●)はほぼ同じである。スケールフリー・ネットワークの方がより速やかに断片化してしまうともいえる。なぜなら、メインのクラスターが完全に断片化されてしまうfの閾値fcが、指数関数的ネットワークの0.28に比べると0.18とより小さいためである。

注4:論文では、上記のようなネットワークの振る舞いはパーコレーション理論に相当すると考えている。「指数関数的ネットワークは、パーコレーション理論における無限次元のパーコレーションに相当し、上記で見られた閾値のある振る舞いはパーコレーションの臨界点に相当すると考えられる。(注:「無秩序から突然秩序が形成される相転移」の逆のようなものか?) また、スケールフリー・ネットワークは、パーコレーション理論において臨界点が極限まで遅延した状態ということができるだろう」との記述がある。
d0194774_0163622.jpg

図3:ネットワークにおけるエラーまたは攻撃に対するネットワークの断片化
図2のネットワークにおいて、最大のクラスターの大きさS(○または□で表す)、その他のクラスターの平均サイズ〈s〉(●または■で表す)を、頂点が消失する割合fの関数として示している。
a:指数関数的ネットワーク(E)において、ランダムなエラーが起きた場合(□または■)または枝の多い頂点を狙った攻撃を受けた場合(○または●)のネットワークの断片化。
b:スケールフリー・ネットワーク(SF)において、ランダムなエラーが起きた場合(青い■)または枝の多い頂点を狙った攻撃を受けた場合(赤い●)のネットワークの断片化を示す。bの右上の小さいグラフは、スケールフリー・ネットワークにおいてfが0から1まで変化するときの、大きいグラフで示されたさらに先の「エラー耐性」を示す曲線である。すべての頂点がほぼ除外されるまで(f=1)、最大のクラスターはばらばらにならないことを示す。

スケールフリー・ネットワークでは、起こりえないくらいの高率のエラー(f_max=0.75、頂点のほぼ3/4がランダムに除外された場合)であっても〈s〉(青い■)のピークは非常に小さい(bの大きい方のグラフでf=0.75であっても〈s〉は1.06程度)。aもbも、頂点の数を1,000、5,000、20,000として解析を繰り返したが、Sと〈s〉が示す曲線はオーバーラップするものであった。したがって、ネットワークの大きさ(頂点の数)に関わらず、エラーが起きたときまたは攻撃を受けたときのネットワークの振る舞いは同じであると言える。

c、d:インターネット(c)とWWW (d)における、エラーや攻撃による断片化を示す。用いられる記号はbと同じだが、dは〈s〉の用いられているスケール(右縦軸)が違うので注意。dでは、攻撃を受けた際、fが小さいときにはメイン以外のクラスターの平均サイズ〈s〉はほぼ1.5(赤い●)であるが、fが大きくなるとfc=0.067を閾値として〈s〉は急速に増大し最大60にまで達して、さらにその後急速に減少することを示している。
インターネットとWWWは、ベキ指数γや頂点からの枝の数の平均〈k〉、クラスター係数が異なるのに、エラーや攻撃に対する反応は同じである。bのスケールフリー・ネットワークとインターネットとWWWの間で、閾値fcの値およびd、S、〈s〉の規模は異なるものの、エラーや攻撃に対する反応は同様であった。


(6) インターネットとWWWのエラー耐性と攻撃に対する脆弱性
現実のネットワークでは、エラーや攻撃がもたらす影響についてはほとんど分かっていないのが現状である。そこでインターネットとWWWという2つのネットワークのエラーおよび攻撃に対する耐性について検討した。(なお、「インターネット」はコンピュータの相互連結によるネットワークのことであり、「WWW」はインターネットを利用して提供される、複数のドキュメントを結びつけるサービスのことをいう。)

インターネットはスケールフリー・ネットワークであり、その連結の分布はベキ法則に従ってP(k)~k^-2.48であることが分かっている(Faloutsos M, 1999)。そこで、上記の結果予想されるインターネットのエラー耐性と攻撃に対する脆弱性を検討した。その結果、インタ―ネットでは、頂点の2.5%までがランダムに除外されてもネットワークの直径dは変わらない(エラー耐性がある)が、もっともリンクの多い頂点が除外されたとき(インターネットのハブが攻撃された場合)は、dが3倍以上に増加することが分かった(図2b)。すなわち、エラー耐性と同時に、攻撃に対する脆弱性が見られる。クラスターの断片化に関しても、ランダムな頂点の除外が増えた場合も大きなクラスターは維持されるのに対し、リンクの多い頂点が除外された場合はfが0.03という小さい値でネットワークは臨界点を示し、ばらばらになったクラスターのサイズの急速な増加が見られた(図3c)。

WWWはドキュメントを頂点とし、URLハイパーリンクを枝とする巨大な有向グラフ(それぞれの枝が頂点から頂点へと向きがあるグラフ)である。WWWもスケールフリー・ネットワークであり、ドキュメントから出る枝の数と入ってくる枝の数はべキ法則P(k)~k ^-γ に従っている。P_in(k)のγ_inは2.1、P_out(k)のγ_inは2.45であることが分かっている。WWWの完全なトポロジー地図は得られていないので、ここでは325,729の頂点と1,469,680の枝のwebのサブセット(Albert R, et al. Nature 1999.)を用いた検討を行った。その結果、ランダムに頂点が除外されてもdはほぼ一定であったが、ハブを狙った攻撃を受けた場合はdが大きく増加した(図2c)。また、高率でエラーが起きてもネットワークは大きなクラスターとして維持されるが、攻撃を受けた場合はfc=0.067を閾値としてクラスターのサイズが急激に増加、すなわちネットワークは急速に断片化した(図3d)。

(7) 結果のまとめ
指数関数的ネットワークとスケールフリー・ネットワークで、それぞれランダムなエラーが起きた場合と枝の多い頂点を狙った攻撃を受けた場合のクラスター断片化反応を図4にまとめた。スケールフリー・ネットワークでエラーが起きた場合(図の下側)は、クラスター断片化がほとんど起こらず、指数関数的ネットワークと比較すると「エラー耐性が強い」と考えられる。また、指数関数的ネットワークでのエラーと攻撃、スケールフリー・ネットワークでの攻撃に対しては、同じような急速なクラスター断片化が起こる(図の上側)。すなわち、スケールフリー・ネットワークの「攻撃に対する脆弱性」が理解できる。
d0194774_0175284.jpg

図4:2種類のネットワークにエラーが起きたとき、またはネットワークに対する攻撃を受けたときのクラスター断片化反応のまとめ

a–fは、図2で示したネットワークがランダムなエラー(a-c)または枝の多い頂点を狙った攻撃(d-f)によって頂点が除外されるとき、除外される頂点の割合fの値(0.05、0.18、0.45)によってどのくらいの大きさのクラスターがどれくらいの割合で存在するかを示すグラフである。グラフは、横軸が出現するクラスターのサイズ(クラスターに含まれる頂点の数)、縦軸がそのクラスターの数(全体の数に占める割合)を示している。○はクラスター断片化の模式図。

上側の図は指数関数的ネットワークでエラーが生じたときおよび攻撃を受けたときと、スケールフリー・ネットワークが攻撃を受けたときの反応が同じであることを示す。fが小さいときは(a)、異なるサイズのクラスターが出現し、その中にはまだ大きいクラスターも残っている。クラスターの断片化したサイズは1から16の間に分布しているが、大きいクラスターでサイズが9,000のものもある(当初のネットワーク全体の頂点の数は10,000)。(b)では、閾値fcにおいてネットワークはサイズが1から100の小さい断片に分解され、大きいクラスターが消失することを示している。fがさらに大きい場合でも、クラスターは頂点数が1か2という小さい断片になるまで分解される。

一方、下側の図は、スケールフリー・ネットワークでランダムなエラーが起きた場合に上側とは異なる反応を示すことを表している。fが増加しても、最大のクラスターのサイズはゆっくり減少し、少しずつ小さいクラスターに分解されるのみである。実際、(d)で見られるように、f=0.05では、クラスターが分解されていると言っても単に1-2個の頂点が出現しているだけである。f=0.18では攻撃を受けたクラスターは断片化しているが、頂点数8,000の大きいクラスター1つと頂点数1から5のクラスターがいくつか見られるのみである(e)。非現実的なくらい高度のエラーが起きても(f=0.45)、大きいクラスターは存在し続け、断片化されたクラスターの頂点数も平均で11を超えない程度の小さいものである(f)。


スケールフリー・ネットワークがエラー耐性を持つことは、同時に、攻撃に対する脆弱性を持つことにも直結する。すなわち、非常に多くの枝が集まる頂点があるからこそエラー耐性があるのだが、今度はそのような頂点を狙った攻撃を受けると、たちまちネットワークの直径が増加し、クラスターが断片化する。攻撃に対する脆弱性はインターネットやWWWといったコミュニケーションネットワークにとっては脅威になるものだが、ネットワークに本質的に内在する不均一な性質自体が攻撃に対する脆弱性をもたらしているのだから、その対策は今後詳しく検討されるべきであろう。
[PR]
by md345797 | 2014-06-06 00:21

複雑ネットワークの理論(2) スケールフリー・ネットワークの提唱

Emergence of scaling in random networks.

Barabási AL, Albert R.

Science. 1999 Oct 15;286(5439):509-12.

【背景】
複雑ネットワークを考えるときに、1998年に提唱されたスモールワールド・ネットワーク (ワッツ・ストロガッツモデル)は画期的なものだった。しかし、現実のネットワークにはハブ(枝の数が非常に大きい頂点)が存在し、これはスモールワールド・ネットワークでは説明できない。このことに直面したノートルダム大学のアルバート・ラズロ・バラバシは、それまでのネットワークモデルにおけるランダムな世界観を捨てて、新しいモデルの構築を目指した。
d0194774_146426.jpg
Albert-László Barabási (1967-) 以下の背景の多くは、バラバシの著書『新ネットワーク思考―世界のしくみを読み解く』(青木薫訳、NHK出版)によっている。







① 「ハブ」の存在
現実社会の友人ネットワークについて考えてみると、大多数の人は友人の数は数名だが、「友人の数がずば抜けて多い」人物が何人かはいる。これはウェブでも同様で、全ドキュメント(1999年で10億以上と言われる)の90%以上はリンクされる数は10以下であるが、ごく少数のページは100万近くリンクされている。後者はネットワーク上では「ずば抜けて枝の多い頂点」であり、ハブと呼ばれる。このハブは現実に存在するにもかかわらず、エルデシュのランダムネットワークでやワッツ・ストロガッツのスモールワールド・ネットワークでは生じない。では、ハブが生じるネットワークとはどのようなものなのか?

② ベキ法則
1900年代、イタリアの経済学者ヴィルフレード・パレートは、「収入分布は“ベキ法則”にしたがう」ことを発見。これは「世の中にはごく一握りのきわめて収入の多い人たちがおり、人口の大多数はわずかな収入しかない」ということを表す法則であり、後にパレートの法則とか「80対20の法則」などと呼ばれた(世の中のお金の80%は人口の20%の人という一握りの人たちが持っており、お金の20%はその他大勢の80%が持っている、ということ)。

これをネットワークでは、頂点の枝の数の度数分布として考える。枝の数がkである頂点の数をN(k)とし、全頂点についてkを横軸、Nの頻度を縦軸にプロットする。その結果は下記の式のようになる。
d0194774_153618.png

これは、一般的には
d0194774_1373621.png

で表される「ベキ法則 (power law)」に従うプロットとなる。(aは定数、kはスケーリング指数と呼ばれる定数で、ここではマイナスの値になる。「ベキ法則」は、べき乗則、ベキ則などとも訳される。ベキ(冪)乗は今では累乗と同じことだが、もともとは累乗と混同されて用いられ始めた用語らしい。「冪」の字は当用数字に含まれないため「ベキ」のように書かれる。)
d0194774_1385965.jpg
(ベキ法則に従うグラフ)

一般的なベキ法則の式の両辺の対数をとると、
d0194774_1382366.png

は、
d0194774_1383737.png

のように表される。

ここでは、「枝の数がk本である頂点の数N(k)が、k^-γ(kの-γ乗)で表される関係」を示す。N(k)=k^-γの両辺の対数を取ると、log N = -γ log kとなり、両対数グラフ(x軸がlog k、y軸がlog N)にプロットすると-γの傾きを持つ直線として表される。
d0194774_1524163.png
(ベキ法則のグラフを両対数プロットで表したもの)

③ スケールフリー・ネットワーク
ベキ法則は、正規分布(釣鐘型の分布)とは違って、①どこにもピークがなく、なめらかに減少する、②分布のすそ野は正規分布よりも広い、③ごく少数のきわめて大きい事象と無数の小さい事象が共存する状態を表すなどの特徴を持つ。バラバシは、枝の数と頂点の数がベキ法則に分布をスケールフリー・ネットワークと呼んだ。

スケールフリー・ネットワークはグラフで見ると分かるように、「平均的な数」の枝をもつ頂点というものは存在しない。枝の数には、なめらかに減少するヒエラルキーがあるのみである(これは「ロングテール」とも呼ばれる)。この分布は、ある枝の数を持つ頂点数に平均や分散などの尺度(スケール)が存在しないので「スケール」「フリー」と名付けられた。

下の図は、『新ネットワーク思考―世界のしくみを読み解く』(アルバート・ラズロ・バラバシ、 青木薫訳)より改変引用させていただいた。左は従来考えられていたランダムネットワークで、k本の枝を持つ頂点の数N(k)は確率的に分布するため、正規分布に従っている。ここでは、ずば抜けて多くの枝を持つ頂点が存在する確率はきわめて低い(存在しない)。右はスケールフリー・ネットワークで、k本の枝を持つ頂点の数はベキ法則に従う。大多数の頂点はごく少ない数の枝しか持たないが、一部のごく少数の頂点は莫大な多さの頂点を持つことを表している。それぞれの下に例として、都市をつなぐ高速道路網(ランダムネットワーク)と、空港をつなぐ航空経路網(スケールフリー・ネットワーク)が示されている、左では高速道路がものすごく多数集中する都市などというものは存在しないが、右では航空便が非常に多く集まる空港(ハブ空港)がいくつか存在している。このようにスケールフリー・ネットワークはランダムネットワークとは全く異なるネットワークである。
d0194774_2161124.jpg

(そもそも、確率に支配されるようなランダム・無秩序な事象は正規分布に従うとされる。一方、そこから秩序が生まれると(秩序の創発、相転移とも呼ばれる)、ベキ法則に従うようになると言われる。したがって、現実のネットワークは、全く無秩序な状態ではなく、秩序が創発した、ちょうど相転移を起こしたような状態でありベキ法則に従うことが多いとされる。なぜ、相転移でベキ法則が出現するかは、1971年にケネス・ウィルソンによる「繰り込み群」理論で証明されている。)

④ 「ネットワークの成長」と「ハブの優先的選択」
ランダムモデルは、(a)頂点は最初からすべて存在し、頂点数は一定という仮説の上に成り立っていた。(b)すべての頂点は対等という仮定もあり、互いに区別できないからこそランダムにリンクできたといえる。しかし、現実に存在するネットワークでは(a)(b)のような仮定は成り立たない。

現実のネットワークは、(1)頂点は1つ1つ増えていく(ネットワークは成長する)。(2)すでに多くのリンクを獲得している頂点(ハブ)は、新しくできた頂点から高い確率でリンクされる(ハブは優先的に選択される)、という2つの特徴を示す。バラバシは、この(1)と(2)の特徴を両方組み込むと、ネットワークはスケールフリーになることを以下の論文で示している。

ここに来て、古典的なモデル(ランダムグラフやスモールワールド・ネットワーク)は「静的」(↔成長する)で、「ランダム性の仮定の上に成立」(↔優先的選択)していたことに初めて気づいたわけである。


【論文内容】
遺伝的ネットワークやWorld Wide Web (WWW)のような複雑ネットワークは、頂点どうしがスケールフリーベキ法則に従う分布によって連結しているというモデルを初めて提唱する。複雑ネットワークは、①新しい頂点を追加していくことによってネットワークが成長する(growth)、②新しい頂点はもともと枝が多かった頂点に優先的に接続される(preferential attachment)という2つの普遍的な特徴を持っている。この2つの特徴を持つモデルは、さらにスケールフリーの分布を再生産して自己組織化することを述べる。

まず、映画俳優の共演ネットワークを社会的ネットワークのモデルとして用いて検討した。各俳優が頂点であり、2人の俳優が同じ映画で共演したとき枝によって連結されると考える(この例では頂点数212,250、平均枝数28.78だった)。ある俳優がkの枝を持つ確率P(k)はほぼkの-γ乗というベキ法則で表され、γの値は2.3±0.1であった(図1A)。次に複雑なネットワークであるWWWで、ドキュメントとリンクを頂点と枝と考えた(頂点数325,729、平均枝数5.46)。ここでもP(k)~k^-γであり、γは2.1±0.1だった(図1B)。さらにアメリカ西部の電力供給網で、発電所・変電所を頂点、高圧送電線を枝と考えた(頂点数は4941と少ない、平均枝数2.67)。ここでも同様にP(k)~k^-γであり、γはほぼ4だった(図1C)。そのほかにも図に示していないが、論文を頂点、引用回数を枝とした場合もベキ法則に従い、γは3だった。以上より、これらの大きな社会的ネットワークでは、頂点が、γ=2.1から4程度のベキ法則にしたがうk本の枝数を持つことが明らかになった。
d0194774_1541918.jpg

図1:現実のネットワークで、ある頂点が枝の数kを持つ確率P(k)を両対数プロットで表したもの。A:映画俳優の共演関係、B:WWW、C:電力供給網の例。いずれも、両対数プロットによって傾きがマイナスの直線(ベキ法則)で近似される。

従来のランダムグラフモデル(エルデシュ=レイニィモデル)では、N個の頂点がお互い枝で連結される確率をpとしたとき、ある頂点がk本の枝を持つ確率P(k)はポアソン分布に従っていた。次に、スモールワールド・ネットワーク (ワッツ・ストロガッツモデル)では、N個の頂点を規則的に結合している枝をpの確率でランダムにつなぎかえたところ、頂点間の距離が減少してスモールワールド現象が生じた。しかし、これら2つのモデルでは、kが非常に大きい頂点(ハブ)が出現する確率は指数関数的に減少し、事実上ハブは出現しない。しかし、前述のベキ法則にしたがう分布では、kが非常に大きい頂点(ハブ)が高い確率で存在することになる。このようにハブが出現するためのネットワークの特徴とは何であろうか?

現実のネットワークには、次のような2つの普遍的な特徴がある。第一の特徴は「成長」(growth)である。ランダムグラフもスモールワールド・ネットワークも、頂点数が一定で固定されていた。しかし、現実のネットワークには新しい頂点が追加され、頂点の数はネットワークの成長とともに増加するのが普通である。例えば、映画俳優の共演ネットワークには新しい俳優が出現し、WWWにも新しいウェブページが作られ、論文の引用でも新しい論文が常に発表されている。第二の特徴は「優先的選択」(preferential attachment)である。従来のモデルは2つの頂点が連結する確率は、ランダムかつ一様であった。しかし、現実のネットワークでは選択的な連結が見られるのである。例えば、新しい俳優は、すでによく知られた出演の多い有名俳優が出ている映画に出演しやすい。これは、もともと他の俳優との共演回数が多い俳優は出演も多いため、新しい俳優はその有名俳優と共演しやすくなるためである。同じように新しく作られたウェブページはすでによく知られたリンクの多いページにリンクすることが多いし、新しい論文はそれまで多く引用されてきたすでによく知られた論文を引用することが多い。すなわち、新しい頂点がすでにある頂点に連結する確率は、一様ではない。枝の少ない頂点よりも、すでに多くの枝をもつ頂点の方に連結する確率の方が高いのである。

次に「成長」と「優先的選択」という2つの特徴を持つモデルを考えた。まず、ネットワークの成長という特徴を、少数(m_0個)の頂点から始まり、時間ごとに新しくm本の枝を持つ頂点が1個ずつ付け加わるとする(このときm≦m_0と仮定)。そして、頂点iに新しい頂点が連結する確率Πは、その頂点がもともと多くの枝を持つときに高くなるようにする。これを頂点iの結合性と呼び、Π(ki)=ki/∑j kj の式で表されることにする。この式は、もともとのki(頂点iが持っている枝の数)を他の頂点の枝数の合計で割ったもので、もともとの枝が多い頂点は新しい頂点が連結する確率Π(ki)が高いことを表している。時間がtステップたつと、このモデルは(m_0+t)個の頂点とmt本の枝というランダムネットワークが付け加わる。その結果、このネットワークは図2Aのように、頂点がk本の枝を持つ確率が「γ=2.9±0.1のベキ法則」に従うスケールフリー・ネットワークとなった。ここではランダムネットワークからベキ法則が生じている(論文タイトルにある「ランダムネットワークからのベキ法則(という新たなスケール)の創発」)。このネットワークは、頂点がk本の枝を持つ確率P(k)は、ネットワークの成長に伴う時間tとは独立している(そのため全頂点の個数(m0+t)=すなわちネットワークのサイズからも独立している)ため、持続的に成長するにもかかわらず、スケールフリーの状態を維持しているという特徴を示す。
d0194774_1555921.jpg

図2A:「成長」と「優先的選択」という2つの特徴が持つネットワークでは、ある頂点の枝の数がkである確率p(k)はベキ法則に従う。最初は5個の頂点(m0=5)から始まり、時間ごとに5個(m=5)ずつ頂点が増え、それはもともとある枝の多い頂点を優先的に選択して連結するネットワークを作成した(本文参照)。時間がt=150,000(○)からt=200,000(□)のP(k)の分布を示したところ、kのベキ法則に従っていた。X軸、Y軸とも両対数でプロットしているので、log kとlog P(k)は傾きが-γの直線で示され、ここではγ=2.9である。
B:「成長」だけあって「優先的選択」がないネットワーク。時間当たりm本の枝を持つ頂点が1つずつ増える。この時、mが大きくなると直線の傾きが小さくなるが(○m=1, □m=3, ◇m=5, △m=7)、いずれもベキ法則には従わない(x軸のkが対数ではないことに注意)。
C:ハブの生成。時刻t_1=5(上の点の集団)と、t_2=95(下の点の集団)において付け加わった2つの頂点が時間とともに枝を獲得していく様子。ki(t)はその時刻に持っている枝の数を表す。古くからある(tが小さい、ここでは5)頂点は、新しく付け加わった頂点(tが大きい、ここでは95)に比べ、格段に(kiは対数で示されているのに注意)多くの枝を持つ(すなわちハブとなる)ことが分かる。


上記のように、ネットワークに「成長」と「優先的選択」という2つの条件を与えるとベキ法則のスケールが出現するが、この2つの条件はどちらも必要なのだろうか?モデルAとして「成長」するが「優先的選択」はない(新しくできた頂点は他の頂点に同じ確率で連結する)ネットワークを仮定した。そこではΠ(k)=(定数)=1/(m0+t-1)である。図2Bがそのようなモデルを表すが、そこではベキ法則が成り立たず(x軸が対数ではないことに注意)、スケールフリーの特徴は見られない。また、モデルBとして、初めにN個の頂点があるが枝がないグラフを想定する。そこでランダムな頂点を選び、それをΠ(ki)=ki/∑j kjの確率で頂点iに連結させる。このモデルは当初はベキ法則に従うが、P(k)は一定である。なぜなら、Nが一定で(=成長しないで)枝の数だけが時間とともに増加する場合、時間がNの2乗に漸近的に等しくなるとその後はすべての頂点が連結された状態に到達してしまうためである。このように、モデルAもモデルBもベキ法則にはならないことから、スケールフリー・ネットワークの生成には「成長」と「優先的選択」の両方が必要と考えられる。

新しく出現した頂点は「優先的選択」すなわち、もともと枝の多い頂点に高い確率で連結するため、ネットワークが成長するにつれて2頂点間の結合性は当初に比べてどんどん大きくなっていく。頂点が新しい枝を得る割合は、∂ki/∂t = ki/2tであるため、 ki(t) = m(t/ti)^0.5で示される。ここではtiはネットワークが始まってから頂点iがネットワークに追加されるまでの時間である(図2C)。ここでは、新しく追加された頂点(tiが大きい)から古くからある(tiが小さい)頂点へ連結する可能性が高いので、古くからある頂点のいくつかは非常に多く枝をもつことになる。これは、現実社会でよく見られる「金持ちはより金持ちになる(rich-get-richer)」という現象と同じである。ここで、ある頂点がk本の枝を持つ確率P(k)は、kの-3乗に比例するベキ法則で示され、このγ=3というのは頂点ごとに追加される枝の数mには独立して決められる。すなわち、
d0194774_21367.png
現実のネットワークでは、γは2.1から4の間だったが、これは優先的選択の程度によって調節される。なお、ネットワークには頂点数が増える「成長」ではなく、すでにある頂点間の枝が増える(または減る)というタイプの成長もある。その場合もγの調節は必要だが、同じ くスケールスケールフリーになる。

【結論】
現実の複雑ネットワークでは「成長」と「優先的選択」という2つの特徴が共通して見られ、それらによって複雑ネットワークには普遍的に「スケールフリー」性が出現する。これは生物学的なシステムにおける遺伝的ネットワークやシグナル伝達ネットワークにも応用可能だろう。ただし、遺伝的ネットワークでは頂点が遺伝的にコードされたものであるため、「成長」する開かれたネットワークではないかもしれない。しかし、単純な分子から複雑な生命が形成される進化の過程ではネットワークの成長が起きているとも考えられ、遺伝的ネットワークについても今後スケールフリー・ネットワーク的な理解が可能になるかもしれない。
[PR]
by md345797 | 2014-06-03 01:22