人気ブログランキング | 話題のタグを見る

一人抄読会

syodokukai.exblog.jp
ブログトップ

複雑ネットワークの理論(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〉)を持つ頂点、すなわちハブがある程度存在する。
複雑ネットワークの理論(3) エラーに対する耐性と攻撃に対する脆弱性_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%の頂点が消失しても、ネットワークに残った頂点どうしの交通には影響が見られない。スケールフリー・ネットワークのの連結は、ベキ法則に従う分布のため、ごく少ない枝しか持たない頂点が大多数を占めており、ランダムに頂点が消失する場合このような「小さい」頂点が消失する確率が大きいので、残った頂点間の経路に与える影響はほとんどなく、ネットワーク全体のトポロジーは全く変わらないといってもよい。
複雑ネットワークの理論(3) エラーに対する耐性と攻撃に対する脆弱性_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:論文では、上記のようなネットワークの振る舞いはパーコレーション理論に相当すると考えている。「指数関数的ネットワークは、パーコレーション理論における無限次元のパーコレーションに相当し、上記で見られた閾値のある振る舞いはパーコレーションの臨界点に相当すると考えられる。(注:「無秩序から突然秩序が形成される相転移」の逆のようなものか?) また、スケールフリー・ネットワークは、パーコレーション理論において臨界点が極限まで遅延した状態ということができるだろう」との記述がある。
複雑ネットワークの理論(3) エラーに対する耐性と攻撃に対する脆弱性_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にまとめた。スケールフリー・ネットワークでエラーが起きた場合(図の下側)は、クラスター断片化がほとんど起こらず、指数関数的ネットワークと比較すると「エラー耐性が強い」と考えられる。また、指数関数的ネットワークでのエラーと攻撃、スケールフリー・ネットワークでの攻撃に対しては、同じような急速なクラスター断片化が起こる(図の上側)。すなわち、スケールフリー・ネットワークの「攻撃に対する脆弱性」が理解できる。
複雑ネットワークの理論(3) エラーに対する耐性と攻撃に対する脆弱性_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といったコミュニケーションネットワークにとっては脅威になるものだが、ネットワークに本質的に内在する不均一な性質自体が攻撃に対する脆弱性をもたらしているのだから、その対策は今後詳しく検討されるべきであろう。
# 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年に提唱されたスモールワールド・ネットワーク (ワッツ・ストロガッツモデル)は画期的なものだった。しかし、現実のネットワークにはハブ(枝の数が非常に大きい頂点)が存在し、これはスモールワールド・ネットワークでは説明できない。このことに直面したノートルダム大学のアルバート・ラズロ・バラバシは、それまでのネットワークモデルにおけるランダムな世界観を捨てて、新しいモデルの構築を目指した。
複雑ネットワークの理論(2) スケールフリー・ネットワークの提唱_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の頻度を縦軸にプロットする。その結果は下記の式のようになる。
複雑ネットワークの理論(2) スケールフリー・ネットワークの提唱_d0194774_153618.png

これは、一般的には
複雑ネットワークの理論(2) スケールフリー・ネットワークの提唱_d0194774_1373621.png

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

一般的なベキ法則の式の両辺の対数をとると、
複雑ネットワークの理論(2) スケールフリー・ネットワークの提唱_d0194774_1382366.png

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

のように表される。

ここでは、「枝の数がk本である頂点の数N(k)が、k^-γ(kの-γ乗)で表される関係」を示す。N(k)=k^-γの両辺の対数を取ると、log N = -γ log kとなり、両対数グラフ(x軸がlog k、y軸がlog N)にプロットすると-γの傾きを持つ直線として表される。
複雑ネットワークの理論(2) スケールフリー・ネットワークの提唱_d0194774_1524163.png
(ベキ法則のグラフを両対数プロットで表したもの)

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

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

下の図は、『新ネットワーク思考―世界のしくみを読み解く』(アルバート・ラズロ・バラバシ、 青木薫訳)より改変引用させていただいた。左は従来考えられていたランダムネットワークで、k本の枝を持つ頂点の数N(k)は確率的に分布するため、正規分布に従っている。ここでは、ずば抜けて多くの枝を持つ頂点が存在する確率はきわめて低い(存在しない)。右はスケールフリー・ネットワークで、k本の枝を持つ頂点の数はベキ法則に従う。大多数の頂点はごく少ない数の枝しか持たないが、一部のごく少数の頂点は莫大な多さの頂点を持つことを表している。それぞれの下に例として、都市をつなぐ高速道路網(ランダムネットワーク)と、空港をつなぐ航空経路網(スケールフリー・ネットワーク)が示されている、左では高速道路がものすごく多数集中する都市などというものは存在しないが、右では航空便が非常に多く集まる空港(ハブ空港)がいくつか存在している。このようにスケールフリー・ネットワークはランダムネットワークとは全く異なるネットワークである。
複雑ネットワークの理論(2) スケールフリー・ネットワークの提唱_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本の枝数を持つことが明らかになった。
複雑ネットワークの理論(2) スケールフリー・ネットワークの提唱_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)=すなわちネットワークのサイズからも独立している)ため、持続的に成長するにもかかわらず、スケールフリーの状態を維持しているという特徴を示す。
複雑ネットワークの理論(2) スケールフリー・ネットワークの提唱_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には独立して決められる。すなわち、
複雑ネットワークの理論(2) スケールフリー・ネットワークの提唱_d0194774_21367.png
現実のネットワークでは、γは2.1から4の間だったが、これは優先的選択の程度によって調節される。なお、ネットワークには頂点数が増える「成長」ではなく、すでにある頂点間の枝が増える(または減る)というタイプの成長もある。その場合もγの調節は必要だが、同じ くスケールスケールフリーになる。

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

複雑ネットワークの理論(1) 「スモールワールド」ネットワークの集合的ダイナミクス

Collective dynamics of 'small-world' networks.

Watts DJ, Strogatz SH.

Nature. 1998 Jun 4;393(6684):440-2.

【背景】
複雑なネットワークに関する重要論文をいくつか読みながら、代謝や疾患のネットワーク的な解明のために必要な概念の理解を目指す。ここではまず背景となる研究の流れを理解し、次に1998年のワッツ・ストロガッツ論文を読む。

① グラフ理論
グラフとはいくつかの点とそれらを結ぶ線からできている図のことで、これを研究する数学の分野をグラフ理論という。点は頂点(vertex、または結節点node)、それらを結ぶ線は枝(edge、または辺、リンクlink)と呼ばれる。ある頂点からある頂点までの最短の行き方(パスpath)のうち、最短のものを2頂点間の距離(distance)といい、グラフのすべての頂点間の距離の平均を平均距離(以下で出てくるcharacteristic path length固有パス長とも)などという。

グラフ理論は、数学者レオンハルト・オイラー「ケーニヒスベルクの7つの橋の問題」を解決したエピソード(1736年)に始まる。その後200年近く進展がなかったが、1960代にフランク・ハラリーらにより近代のグラフ理論が整備された。なお、グラフ理論を初歩から着実に理解するには、『あたらしいグラフ理論入門』小林みどり著、牧野書店)が有用である。

「グラフ理論」は、ある条件を設定して無矛盾な論理を展開するという数学の一分野である。しかし、現実社会や自然界に見られるネットワークではそれらの前提条件が厳密に満たされることは少ない。実際に見られるネットワークは頂点数がきわめて多く、不規則で複雑なネットワークであり、グラフ理論に基づいて不規則で複雑なネットワークを表現し解析する方法が求められるようになってきた。

② ランダムグラフ
現実に見られるネットワークは、グラフ理論にもっと乱雑な性質を加えたものであると考えられる。そこで、1959年に数学者ポール・エルデシュがランダムグラフを提唱した。これは、n個の頂点があるときに2頂点間に確率pで枝をおき、確率(1-p)で枝をおかないようにしたもの。確率pが小さいと枝が少なくネットワークが分断され、pが大きいと枝が多くてすぎてネットワークが密になりすぎる。ある程度のpなら、現実のネットワークのように枝の数も中等度(ある程度疎)で乱雑なものとなる。提唱者の名前を取って、Erdős–Rényiグラフ(ERモデル)とも呼ばれる(Erdős P, Rényi A. "On Random Graphs. I.". Publicationes Mathematicae 6:290–297, 1959)。

エルデシュは、「複雑さとはランダムということである」と仮定し、頂点をランダムに結ぶランダムグラフ理論を作った。しかし、現実のネットワークでは、各頂点がそのように平等で、しかも頂点間の連結が全くランダムであるはずがない。エルデシュの目標は、現実のネットワークに応用できる普遍的なモデルを作成することではなく、ランダムグラフ理論の数学的な深さに対する探究だったのかもしれない。では、現実のネットワークはどのように形成されるのだろうか?

③ スモールワールドの発見
現実の社会的ネットワークでは、比較的少数の人を介して誰ともつながれることが知られている。これは、1969年のスタンレー・ミルグラムの実験によって、世界中の人は平均6人の知り合いを介して高度に相互連結している現象として明らかにされた。後に言われる「6次の隔たり」による「小さな世界(small world)」の発見である。これは、n個の頂点が、平均k本の枝を持つネットワークがあると、dステップ離れた頂点はk^d (kのd乗)個ある。Nやkが非常に大きくなっても、k^dはNを超えることはないから、最大でk^d=Nと考えられる。両辺の対数を取ると、ネットワークの平均距離は、d=log N/log kで表される。頂点数Nが世界の人口のように非常に大きくなっても、対数の関係で表されるのでぐっと収縮し、現実のネットワークでは平均距離dは意外と小さくなることが分かる。「ネットワークの平均距離が短い」という点では、格子型のグラフのような規則的なネットワーク(別の頂点に到達するまでの距離は長い)より、エルデシュのランダムグラフの方が現実のネットワークに近いと考えられる。

・なお、6次の隔たりと言っても、現実に「目的の人物まで簡単に到達できる」ということではない。平均の知り合い数(各頂点の枝の数)をkとすると、単純にk^6人の知り合いを全部チェックしないと目的の人には到達できないことになるためである。ただし、この場合も実際にはすべての知り合いをチェックしなくても、近い人を選んでチェックするだろうから、もっと早く到達しうるだろう。「6次」というのはむしろ上限なのかもしれない。

・「世界は小さい(It’s a small world)」というときのネットワーク上の「距離」は、ここでは頂点からの別の頂点まで最短で到達できる枝の数のことであり、今までのユークリッド空間の「距離」とは本質も扱いも大きく異なる。したがって、ネットワークを考える際には、非ユークリッド的世界の新しい幾何学といったものを学ぶ必要があるだろう。(『新ネットワーク思考―世界のしくみを読み解く』 アルバート・ラズロ・バラバシ、 青木薫訳より)

④ ネットワークのクラスター的現実
さて、社会学者マーク・グラノヴェッターは1969年に、「新しい仕事を見つける力になってくれたのは親しい友人ではなく、ちょっとした知り合いであること」を発見した。これは「弱い社会的絆(弱い紐帯)の重要性」として報告され、社会学における重要な知見となった。親しい友人はでは知りうる情報が似ていて役に立たず、一方、単なる知り合いの方が異なる情報を持っているために新しい仕事を見つけるのには有用なことがあるためなのだろう。

ここでまず、「親しい友人」どうしで密に結ばれるネットワークを想定する。それらのネットワークがお互い、「単なる知人どうし」という弱い絆によって結ばれているのが、現実のあり方であることが明らかになった。前者の親しい友人どうしの密なネットワークは、「クラスター」と呼ばれる。現実のネットワークはこのように、全くのランダムな頂点の結びつきではなく、いくつかのクラスターを含むものである。

そこで、当時コーネル大学で応用数学から社会学を研究していたダンカン・ワッツとその指導教官スティーブン・ストロガッツは、このようなクラスター化の程度を定量化することを考え、クラスター係数(clustering coefficient)という量を導入した。例として、自分につながる友人たちがどのくらいクラスター化されているかということを考えるとする。「友人たちの間に実際に存在する枝の数を、生じうる可能な枝の数で割ったもの」を求めると、友人たちがみんな互いに友人どうしであればその数は1になり、友人たちがお互い全然友人でない(自分を介してつながっているだけ)であればその数は0となる。これをネットワーク全体で平均したものを、そのネットワークのクラスター係数と呼んだ。

実際のネットワークの例として、論文の共著関係でクラスター化があるかを実証した。ここでは数学論文のデータベースを用いて、前述のエルデシュと論文の共著者としてどのくらいの数でつながっているのか(エルデシュ数)を測定することもできる。このような論文共著のネットワークを検討したところ、それは①平均距離が小さく(小さい世界であり)、②クラスター性を持つという2つの特徴を満たすことが実証された。
複雑ネットワークの理論(1)  「スモールワールド」ネットワークの集合的ダイナミクス_d0194774_2034041.png
Duncan J. Watts (1971-)
現実のネットワークは平均距離が小さく、かつクラスター化されている。全く規則的なグラフではクラスター化はされているが平均距離は大きい。一方、ランダムグラフでは、平均距離は小さいものの、クラスター化されていない。それらの折り合いをつけて、現実のネットワークに近いモデルとして提唱されたのが、後述ののスモールワールド・ネットワークであった。

⑤ なおこの翌年に、さらに動的に成長する現実のネットワークの新しいモデル(スケールフリー・ネットワーク)が提唱されることになる。



【論文内容】
従来、ネットワークの結合の形態は完全に規則的か、完全にランダムかと考えられてきた。しかし、現実の社会的ネットワークや自然界のネットワークはこの両極端の間にあるのではないだろうか。この研究では、完全に規則的と完全にランダムのちょうど中間のネットワークの単純なモデルを提案する。それは、規則的なネットワークを「つなぎかえる(rewire)」ことによりランダムさを増加させるという方法によっている。

以下で提唱するネットワークモデルは、以前「スモールワールド」またの名を「6次の隔たり」と呼ばれた現象との類似性により、「スモールワールド・ネットワーク」と呼ぶことにする。スモールワールド・ネットワークは。線虫(C. elegans)の神経系のネットワーク、米国西部の電力系統、映画俳優の共演関係に共通して認められるものであった。またこのネットワークは、情報の拡散速度や同期性が大きく、感染症はスモールワールド・ネットワークでは規則的なネットワークに比べて速く拡大することが示された。

図1左のように、n個の頂点にそれぞれ枝がk本ある規則的な格子(lattice)グラフがあるとする。この枝をすべて確率pでランダムにつなぎかえる。それにより、p=0で規則的な格子、p=1でランダムなグラフの間を調節することができる。今まで、このpが0と1の間という中間領域についてはほとんどわかっていなかった。
複雑ネットワークの理論(1)  「スモールワールド」ネットワークの集合的ダイナミクス_d0194774_394161.gif

図1:ここでは、グラフの頂点と枝の数を変えることなく、規則的なネットワーク(左)からランダムなネットワーク(右)に移行するための、ランダムな枝の「つなぎ替え」を示している。左は、n個の頂点とそれぞれから出るk本の枝で最も近い頂点どうしが結ばれる規則的なグラフである(図では分かりやすくするため、n=20、k=4としているが、後述の実際のネットワークではnもkも非常に多い)。真ん中は、これらの枝を確率pでランダムな頂点につなぎ替え、確率(1-p)でそのままにしたものである。この確率は0から1まで変化するが、p=0のときは規則的な格子で変わらないが、徐々にランダムさが増加し、右のp=1で頂点間の枝は完全にランダムにつなぎかえられる。真ん中のグラフが、スモールワールド・ネットワークであり、規則的なネットワークに見られるような高いクラスター性と、ランダムネットワークに見られるような短い平均距離という2つの特徴を併せ持っている。

ここで、これらのグラフの平均距離(characteristic path length固有パス長=すべての2頂点間の距離の平均) L(p)クラスター係数 C(p)を求めた。平均距離Lはすべての2つの頂点の間の最短の枝の数の平均、すなわちグラフの全体的な特性を表し、クラスター係数Cは隣接するはずの頂点どうしが実際にどのくらい枝でつながっているかの平均、すなわちグラフがどのくらいクラスター化されているか(cliquishness)という局所的な特性を表す(cliqueは派閥とか仲良しグループというような意味である)。

実際のネットワークは、多くの頂点がある程度疎に結合しているが、グラフが非連結になるほど疎ではない。式で表すと、n≫k≫ln(n)≫1であり、ここでk≫ln(n)であることが「ランダムグラフが連結である」ために必要である(頂点の数nは各頂点の枝の数kに比べて非常に多い=すなわちネットワークが疎、kは頂点の対数より非常に多い=すなわち枝はある程度密である)。このときpが0に近づく(=ネットワークが規則的になる)とLはn/2kに近似(これは≫1)でCは3/4に近づく。一方、pが1に近づく(=ネットワークがランダムになる)とL_randomはln(n)/ln(k)、C_randomはk/n(これは≪1)となる。

すなわち、規則的な格子(p=0)は高度にクラスター化されており、頂点数nが増えるにしたがってネットワークの平均距離Lは直線的に増加する。一方、ランダムネットワーク(p=1)はクラスター化が少なく頂点数nが増えても平均距離Lは対数的にしか増加しないためスモールワールドになる。このような両極端では、Cが大きい時はLも大きく、Cが小さい時はLも小さい。(高度にクラスター化されていれば平均距離が大きく、クラスター化が少なければ平均距離も小さい=スモールワールド)
複雑ネットワークの理論(1)  「スモールワールド」ネットワークの集合的ダイナミクス_d0194774_20243184.gif

図2:図1で示した頂点間の枝のつなぎ替え確率がpのときの、ネットワークの平均距離L(p)とクラスター係数C(p)の関係をプロットした。
ネットワークの平均距離Lは2つの頂点をつなぐ最小の枝の数を全頂点間で平均値を取ったもの。クラスター係数Cはネットワーク全体がどのくらいクラスター化されているかを0から1までの数値で表したもので、ある頂点vにkv個の頂点が隣接しているとき、取りうる枝の数は最大でkv(kv-1)/2本であるが、そのうち実際に存在する枝の数の割合をCvとして求め、頂点全部で平均を取ったものがCである。友人のネットワークでいえば、平均距離Lは2人を結ぶ最短人数であり、ある人vの友人どうしが「彼らの間でどのくらい友人どうしか」を表すCvのネットワーク全体の平均がクラスター係数Cである。


図2では頂点数n=1000、頂点あたりの枝の数(次数)k=10のとき、pが増加する(ネットワークのランダムさが増加する)ことによって、LやCがどの程度低下するかを示した。Lの低下は急速だったので、横軸のLは対数で表示してある。pが中等度のとき、平均距離は急速に低下するのに、クラスター係数はあまり低下しない(局所的なクラスターは十分保たれる)、というスモールワールド現象が生じる。

図2のように、pが大きくなってネットワークの平均距離L(p)がほとんどL_randomまで小さくなっても、クラスター係数はしばらくC(p)≫C_randomであるようなpが存在する。これは、規則的な枝をある程度ランダムにつなぎかえると、「クラスター性を保ちながら、ネットワークの平均距離は短い」というスモールワールド・ネットワークの特徴が出現することを示している。もともとは距離が遠かった頂点間を結ぶ「ショートカット(近道)」の枝を導入することによって、完全なランダムネットワークではないスモールワールドが実現する。pが小さい場合は、ショートカットはネットワークの平均距離を大きく短縮させる(pが少し大きくなるだけで非直線的に大きい効果がある)。これは、ショートカットはそれが結ぶ頂点間だけではなく、それらの近傍、さらにはその近傍間を結ぶ距離をすべて短縮することができるためである。一方、ショートカットとなるためにクラスター化された近傍から除かれた枝は、クラスター係数Cの低下には直線的に影響する。pが小さいときL(p)が急激に低下しても事実上C(p)は低下しないからである。ここで重要なことは、スモールワールドへの移行はクラスター係数C(p)によって表される局所的な状態からはほとんど分からないということである。これらの結果の正しさを検証するために、様々な異なるタイプのネットワークで当初は規則的なグラフで、異なるアルゴリズムによりランダムなつなぎ替えを行ったとき、本質的に同じ結果が得られるかを検討した。この時、頂点のつなぎ替えに際して、L_randomよりも遠く離れているはずの頂点を結合させるようにつなぎ替えなければならないことだけを条件とした。

このような理想的な構成を行うことにより、ショートカットの重要な役割が明らかになった。すなわち、スモールワールド現象は、多くの頂点を持つ疎なネットワークに起きやすく、その際ショートカットの数は割と少なくても十分であることが分かった。このことを検証するため、さまざまなネットワークの実例で平均距離Lとクラスター係数Cを計算することにした。実例は、映画俳優の共演関係(ランダムネットワークの提唱者・P エルデシュとの論文共著関係を表すグラフに似たものである)、米国西部の電力供給網、線虫C.elegansの神経ネットワーク(すべての細胞系譜と神経ネットワークが明らかになっている)である。これら3つのグラフでLとCを計算すると、これらがすべてスモールワールド・ネットワークを示していることが明らかになった。したがって、スモールワールド現象は人工的・社会的ネットワークだけでなく、自然界の大きいネットワークに普遍的に見られる現象と思われる。

複雑ネットワークの理論(1)  「スモールワールド」ネットワークの集合的ダイナミクス_d0194774_20233910.gif

表1:スモールワールドネットワークの実際の例。
上から映画俳優の共演関係、米国西部の電力供給網、線虫の神経ネットワークであり、それぞれの頂点数n、頂点あたりの枝の平均kが説明文に書かれている。L_actual、C_actualはそれぞれの現実のネットワークの平均距離とクラスター係数であり、L_random、C_randomはそれぞれの頂点数、平均次数を持つランダムネットワークの平均距離とクラスター係数を示す。いずれの実際のネットワークでも、L_randomに比べLはやや大きいか同程度なのに、C_randomに比べてCが非常に大きく、短い平均距離の割に大きくクラスター化されている(すなわちスモールワールド・ネットワークである)ことが分かる。


そこで次に、感染症の拡大の単純化モデルを用いて、スモールワールド現象の重要性をさらに検討することにした。このモデルは図1のようなグラフを想定し、t=0で健康な集団に1名の感染患者が発生したとする。さらに、ある一定期間感染症が続いた後、感染患者は免疫成立または死亡によって除かれ、その後は二度と感染が起きないと仮定する。この期間に、感染患者に接した健康な人は確率rで感染するとする。これにより、感染が拡大して全員が感染または死亡するか、ある一部が感染している状態が進行していることになる。

図3aでは、集団の半数が感染するために必要な感染の確率(critical infectioneness:感染力) r_halfは、pが大きくなるにつれて減少することを示している。すなわち、ネットワークがランダムであるほど平均距離が短くなるため、感染の確率が低くても(弱い感染力の感染症でも)、集団の半数が感染しうる(図3a)。また、感染症が集団全体を感染させるに十分な感染力がある場合(r=1)、感染がネットワーク全体に拡大するのに必要な時間T(p)が減少するカーブは、ネットワーク平均距離L(p)が減少するカーブとほぼ同じであった(図3b)。この図の横軸は対数表示であるので、ごくわずかにpが増加しただけでも、急速にT(p)が減少することを表す。すなわち、意外と少ないランダムなショートカットがあれば、簡単にランダムネットワークと同じ程度急速な感染症拡大が起きるようになる。
複雑ネットワークの理論(1)  「スモールワールド」ネットワークの集合的ダイナミクス_d0194774_20223456.gif

図3:感染症拡大の単純モデルのシミュレーション結果
a:集団の半数が感染するために必要な感染の確率(r_half)は、ネットワークがランダムであるほど小さくて済むことを表す。
b:また、感染の確率が最大(r=1)のとき、集団全体に感染が拡大するまでの時間T(p)は、ネットワークの平均距離L(p)の減少のカーブと同じになる。ここで、横軸は対数であることに注意。これは、ごくわずかのpの増加でも、急速にT(p)が減少することを表す。すなわち、数本のランダムな枝のつなぎ替えによって、感染が全体に広がる時間はランダムネットワークと同様になる。

【結論】
スモールワールド・ネットワークに見られる①クラスター性が高く、かつ②ネットワークの平均距離が短い、という2つの組み合わせは、従来の規則的な格子モデルやランダムグラフモデルでは見られなかったものである。今後、現実社会や自然界のネットワークにこのモデルが広く見いだされると思われる。

# by md345797 | 2014-05-30 03:03

Points of significanceコラム 1:標準偏差(SD)と標準誤差(SEM)を区別する

Points of significance :Importance of being uncertain.(統計学は不確実性を扱う)
Points of significance :Error bars.(エラーバーと有意差の解釈)

Krzywinski M, Altman N.

Nat Methods. 2013 Sep;10(9):809-10、Oct;10(10):921-2.

【総説内容】

1. 統計学は不確実性を扱う
われわれがまた自然現象について何かを調べるとき、毎回全く同一の値が得られることはまずない。われわれの観察や経験は常にいろいろな不確実性を伴い、決して完全ではありえない。しかも、その観察や経験が1回しか行われないことが多い。このような不確実性を伴う、たった1回の経験だけをもとに、一般化した本質を理解するには何らかの危険が伴う。われわれの経験を要約して一般化して理解する際に、「どのくらいの危険が伴うのか」「その一般化はどれくらい信頼できるのか」を扱うのが統計学である。ここでは、統計学の基本的な概念を、直観的に理解しにくい部分も含めて考察する。また、「医学雑誌に掲載された論文の約半分は統計を誤用している」とする報告もあり、よく見られる統計に対する認識の誤りについても考える。

統計学は、記述的な面(descriptive:経験をまとめ要約する部分)と推測的な面(inferential:たった1回の経験からそれが一般化できるかを推定する部分)からなる。推測を行うべき全体のデータは、母集団(population)と呼ばれる。母集団の分布は横軸に数値、縦軸に頻度を取った度数分布(frequency distribution)で表され、これは度数分布をある範囲の数値ごとに頻度をまとめて棒グラフにしたヒストグラムや、ヒストグラムの各棒の上端をなめらかな線で結んだ分布曲線で表されることが多い。
Points of significanceコラム 1:標準偏差(SD)と標準誤差(SEM)を区別する_d0194774_1122315.jpg

上の図1aはこの母集団分布の位置を表す平均(μ)と広がりを表す標準偏差(SD、s.d.、σ)を表す。これは図1bのようにさまざまな値を取り、直接は分からないこれらの値を推測することが統計の主要な目的である。母集団は非常に大きく、その平均を直接求めることはできないので、母集団から標本(sample)を得ることによって推定することになる。

2. 標本から、母集団の平均を推定する
(1) 標本で観測される平均や標準偏差などの数値を統計量(statistics)、母集団の平均や標準偏差(これらは直接は知り得ない)を母集団パラメータ(population parameter)と呼ぶ。前者はローマ字(X barやs)、後者はギリシア文字(μ、σ)で書く。標本の統計量を用いて、母集団のパラメータを推定することが主要な目的である。

なお、ある分布が正規分布曲線に従うとき、平均±1SDの間、平均±2SDの間、平均±3SDの間には、それぞれ68%、95%、99.7%の面積が含まれる(これらは概数であり、正確には整数を正規分布曲線の式にあてはめた68.26…%、95.44…%、99.74…%のような数値である)。
Points of significanceコラム 1:標準偏差(SD)と標準誤差(SEM)を区別する_d0194774_1125297.jpg

ここで、標本の抽出(sampling)にあたり、1つの母集団からランダムに何組も標本を取ることを想定する。例えば、図2aのような不規則な分布曲線で表される母集団から、標本の大きさ(標本のデータの数)が5個の標本(n=5)を3種類得たとする(図2b)。標本1はX_1(_は1が下付き文字であることを表す)、そして標本1の5個のデータの平均値はX_1 bar(図のようにX_1の上に横棒)と書く。

(2) ところで、母集団から組数の標本を取ると、それら多数の標本の平均(X_bar)の分布というものができる。これは標本分布(sampling distribution)と呼ばれる概念である(図2c)。図2cのように、標本分布の平均をμ_X bar (X barは下付き文字)、標本分布の標準偏差をσ_X bar (X barは下付き文字)で表す。

ここで、標本の大きさが大きくなればなるほど、母集団の形が何であれ、標本分布は正規分布に近づく(下の図3)。これは、中心極限定理(central limit theorem; CLT)という、統計学の最も基本的で重要な定理に基づいている(定義の詳細は省略)。
Points of significanceコラム 1:標準偏差(SD)と標準誤差(SEM)を区別する_d0194774_1132129.jpg


(3) このとき、CLTに基づいて次のことが導かれる。nが十分に大きくなるとき、

標本分布の平均μ_X barは、母集団の平均μに等しくなる。
標本分布の標準偏差σ_X barは、(母集団の標準偏差σ)/√(標本の大きさn)に等しくなる。

②の方は混乱を招くことが多いが、σ_X barは「標本分布の」標準偏差σは「母集団の」標準偏差であり、後述の標準誤差(SEM=s/√n)は②のσ/√nの推定値(estimate)である。多くの本には「標本分布の標準偏差=標準誤差」と書かれていることが多いが、厳密には母集団標準偏差/√nの推定値である。

上記の①②は、nが無限大に大きくなった場合を想定しているのであって、現実にはnは有限個しか集められない。そのため、
①′ 母集団の平均μは、標本の統計量に基づいて、「ある区間にある確率で含まれる」というように区間で推定するほかない。
②′ 標本平均の標準偏差σ_X bar母集団の標準偏差σもいずれも仮想上のもので、直接には求めることはできない。標本の標準偏差sはnが十分に大きくなれば母集団の標準偏差σの代用にはなるが(下図4参照)、①′の推定に使うには不十分である*。そこで、後述の標準誤差(=s/√n)をσ/√nの推定値として用い(図4参照)、σ/√nはσ_X barと等しいことから、①′の標本分布の平均の区間推定に用いる。

(*ここでは、「標本の標準偏差と母集団の標準偏差に差がない」と仮定して、母集団の平均を推測する。実際は標本と母集団の標準偏差に差がある場合もあるだろうが、それはあまりに複雑になるので割愛し、上記のような仮定での説明を続ける。)

(4) 標本分布の標準偏差(の推定値)は、標準誤差(SEM、s.e.m.=standard error of the mean)と呼ばれる。標準誤差は、標本の「標準偏差(SD)と大きさ(n)」という既知の値から(標本のSD)/√(標本の大きさn)で求められる。

さて、前述のように標準分布の平均は、ある範囲で推定するしかない。標本分布において、標本平均±1SEMの範囲に標本分布の平均が含まれる確率は68%である。また、標本平均±3SEMの範囲であれば、標本分布の平均は99.7%の確率で含まれる。このように「信頼度を上げるためには推測の範囲を大きくする必要があり、逆に「推測の範囲を狭めれば信頼度は下がってしまう」というジレンマがある。そこで慣習上、標本平均±2SEMの範囲で95%程度の信頼度で、標本分布の平均(すなわち母集団平均)を推測することにしている。この標本分布の平均±2SEM範囲を、標本分布の平均の「95%信頼区間(confidence interval; CI)」と呼んでいる。

(5) 以上より、標準分布のSEMが分かり、標本分布の平均が95%の確率で標本の平均±2SEMの区間に入ることが示された。中心極限定理に基づくと、標準分布の平均母集団平均は等しいので、母集団平均標本平均±2SEMの範囲を95%信頼区間として求めることができた。

(6) 以上で見たように、SDとSEMはまったく異質のものである。SDは、ある標本の平均のまわりのデータのばらつきを表す。一方SEMは、「標本分布においてどのくらいのばらつき具合で標本平均がばらついているか、これにより標本平均の上下どのくらいの範囲で標本分布の平均が含まれる区間を絞れるか」というを表す。nが十分大きい時、標本分布の平均母集団平均と等しいので、SEMは得られた標本平均によってどのくらいの精度で、どのくらいの信頼性をもって母集団平均を予測できるかの指標になる。SDは標本のばらつきを表す「量」で、SEMは標本平均から母集団平均を推測するためのこの標本平均の「質」と言えるかもしれない。

(7) したがって、標本のばらつきを表すSDの代用として、SEMを用いてはならない。グラフではSEMの方がSDのエラーバーより小さくなるので、「ばらつきが少なく、実験の精度が高く見える」「エラーバーが小さいのでより有意差があるように表現できる」と、見栄えを考えてSDで書くべきエラーバーをSEMのエラーバーで代用する、といったSEMの誤用は論外である。そもそもSDも標本のデータがもともとばらついていることを表しているだけで、実験の精度とは関係がない。さらには、あなたが論文の読者で、著者がSEMのエラーバーを用いていたら、その長さを√n倍して標本のSDを求め、±2SDの間に95%の標本データが含まれる、というように考えよう。

Points of significanceコラム 1:標準偏差(SD)と標準誤差(SEM)を区別する_d0194774_114123.jpg

上の図4は、図2aの母集団から3種類の標本(X_1, X_2, X_3)を取って、標本の大きさnを1から100まで増加させた場合の標本平均(X_bar)、標本の標準偏差(s)、標本分布の標準誤差(s.e.m.)の変化を点で示したものである(これらは標本から求められる)。赤い線は母集団の平均μ、母集団の標準偏差σ標本分布の標準偏差σ_X barを表している(これらは理論上の仮想で、現実には求められない)。上から1番目、2番目のように母集団の平均と母集団の標準偏差は取る標本の大きさに関わらず同一の値であるが、3番目のグラフのように標本分布の標準偏差σ_X barはnが大きくなるにつれて徐々に減少していって一定の値に収束する。標準誤差s.e.m.がいかに標本分布の標準偏差σ_X barの推定値になり、標本平均から母集団平均を推測するのに有用かが分かる。

3. エラーバーの解釈
次に、ここに2つの独立した標本があるとする。これらの標本は、同じ大きさで、同じ広がりをもつ正規分布に従っているとする。これら2つの標本の平均の間に有意差があるかどうか、2標本のt-検定(two-sample t-test)を用いてP値を計算した。

有意差について詳しくは次回以降述べるとして、ここではこの結果を3種類のエラーバー(すなわちSD、SEM、95%CI)を用いて表現したものを下の図5に示す。2つの標本の平均は0と1.0とする。
Points of significanceコラム 1:標準偏差(SD)と標準誤差(SEM)を区別する_d0194774_1142488.jpg

図5aは、3種類のエラーバーでP値は異なるが、同じ長さで表現した場合である。2つの標本のエラーバーがちょうど接するとき、3種類でP値は全く異なることを示している。図5bでは、同じP=0.05になるようなエラーバーとしたところ、3種類の長さは異なり、オーバーラップまたはギャップがあることを示す。図5bで分かるように、「エラーバーどうしが重なり合っていない場合、2つの標本の平均の間には有意な差がある」とか「エラーバーが重なっているので、平均間に有意差はない」という思い込みは、どちらも全く誤りである

2012年にNature Methodsに掲載された論文の2/3の図でエラーバーが使われていた。しかしそのうち、エラーバーがSDを表すものは45%、SEMを表すものは49%、95%CIを表すものはある論文の1つの図のみだった。そのほか5%では何とエラーバーが何を示すのかが文中に述べられていなかった。

(1)エラーバーがSD
図5aではn=10の2つの標本のエラーバーどうしが接触しているが、P=0.0003と有意差がある。図5bではP=0.05で有意差があると言えるがエラーバーは重なっていない。エラーバーの重なりと有意差については一概に、直観的には判断できない。

(2) エラーバーがSEM
図5aではn=10の2つの標本のエラーバーどうしが接触しているが、P=0.17と有意差はなく、図5bでは有意差があってエラーバーが離れている。ここでも「2標本のエラーバーが重ならないからといって、標本間に有意差がある」と考えるのは間違いである。

(3)エラーバーがCI
95%CIがよく用いられるが、下の図6のように標本平均のエラーバーとしてCIが用いられると、95%の確率で母集団平均がエラーバー内にあることになる(同一の母集団から別の標本を取ったとき、その標本の平均が95%の確率でエラーバー内にある、というのはよくある間違い)。95%CIのエラーバーはn=3でおよそ4 x SEM、nが15以上でおよそ2 x SEMでSEMのエラーバーに比べて大きい(図6b)。
Points of significanceコラム 1:標準偏差(SD)と標準誤差(SEM)を区別する_d0194774_1115316.jpg


現時点では不幸なことに、上記3種類のエラーバー(SDとSEMと95%CI)は理解不十分のまま混在している。したがって、論文を読む際には、このエラーバーは何であり、どう解釈するのが正しいのかを常に考える必要があるだろう。

付記:
上記のまとめでは、『新・涙なしの統計学』 (D. ロウントリー著・加納 悟訳:新世社、2001)の記述が大変分かりやすかったので参考にさせていただいた。


# by md345797 | 2014-05-07 01:04 | その他

複数祖先集団GWASのメタアナリシスは、新たな2型糖尿病感受性座位の発見と微細地図解像度の上昇に有用

Genome-wide trans-ancestry meta-analysis provides insight into the genetic architecture of type 2 diabetes susceptibility.

DIAbetes Genetics Replication And Meta-analysis (DIAGRAM) Consortium.

Nat Genet. 2014 Mar;46(3):234-44.

【用語集】
Single nucleotide polymorphism; SNP (一塩基多型):ゲノムDNA上の一塩基の置換。塩基の置換のうち、頻度が非常に少ないものを変異(mutation)、人口の0.5%以上に見られるようなある程度の頻度で見られるものを多型(polymorphism)と呼ぶ。SNPの中でも置換の頻度の多い(人口の5%以上に見られる)ものをコモンSNP(common SNP)と呼ぶ。2003年から始まったInternational HapMap Projectによってcommon SNPの大部分が明らかにされた。
Locus, Loci (座位):ゲノム上の位置のこと。1つの座位に対し、1つの遺伝型(genotype)が対応する。ある1つの塩基の場所を「座位」とよび、それが何の塩基であるかを「遺伝型」と呼んでもよい。
(これらの語は、遺伝子が発見される前に作られた用語なので、「遺伝子」の場所や型というわけでもない。したがって、「遺伝子座」「遺伝子型」というより「座位」「遺伝型」という訳が適しているとされる。)
Trait (形質):形質は、一つの座位に可能な表現型をまとめたもの。
「エンドウマメの形」という形質(trait)に対し、「丸い」「しわがある」という表現型(phenotype)がある、などと考える。
Allele(アレル):ある個体では、1つの座位に父母由来の2つの遺伝型が存在し、この関係をアレルと呼ぶ。1つの塩基の座位にある、2つの塩基をアレルと呼んでもよい。「アレル」も遺伝子発見以前からの用語であり、しかも実体ではなく関係を表す語なので、「対立遺伝子」と訳すより、「アレル」のまま用いるのがよい。
アレルの人口の中での頻度を調べて、頻度の高いものを「メジャーアレル」、低いものを「マイナーアレル」と呼ぶ。マイナーアレルは「多型」であり、疾患と関連することが多い。
Allele Frequency (アレル頻度):マイナーアレルの頻度が5%以上のSNPはコモンSNP、0.5~5%のSNPはレアSNP、0.5%未満のものは変異(mutation)と呼ばれる。SNPの多型の頻度(アレル頻度)を横軸に取り、その多型が表現型にどう影響するか(疾患となるオッズ比)を縦軸に取ったグラフが非常に有名である(Manolio TA et al. Finding the missing heritability of complex diseases.
Nature. 2009 Oct 8;461(7265):747-53.
)
複数祖先集団GWASのメタアナリシスは、新たな2型糖尿病感受性座位の発見と微細地図解像度の上昇に有用_d0194774_14534374.jpg

左上は非常にまれなSNP変異だがその影響は大きいもの(その変異があるとほぼ必ずその疾患となる)、右下は頻度の多いSNP多型だがその一つ一つのSNPが疾患に及ぼす影響が少ないもの(疾患発症のオッズ比が1.1-1.5程度のもの)である。前者はメンデル型遺伝性疾患、後者はよくみられる、コモンな疾患と考えられている。このようにコモンな疾患とは、頻度は多いがその影響は少ないSNP多型が積み重なってできているとする仮説がある。これが「コモンな疾患はコモンな多型によって起こる」(common disease-common variants; CDCV)仮説であり、CDCV仮説に基づいてGWASを用いたコモンな疾患の原因検索が行われてきた。GWASは、頻度の多いSNP多型を検出することにより、疾患とSNPの関連を調べる方法である(後述)。

上図の中間(水色)の疾患はアレル頻度のやや低い(0.5~5%)のレアSNP多型が、それぞれ疾患に対しやや大きい影響をもたらすというものである。稀少疾患(rare disease)がこれに当たると考えられる。また、コモンな疾患の一部にはこのようなレアなSNP多型が関与しているかもしれない(common disease-rare variant; CDRV仮説)。この集団は従来のGWASではとらえることが困難であり、今後、密度の非常に高いSNPアレイ、次世代シークエンサーを用いた全ゲノムシークエンスやエキソン全体のエキソームシークエンスなど(深度が高い=ディープシークエンスと呼ぶ)の発達によって解析が可能になると考えられる。

Linkage disequilibrium; LD(連鎖不均衡):染色体が子孫に受け継がれるとき、遺伝子の相同組み換えが起きる。その際、相同組み換えが起こりやすい場所(ホットスポット)がある。これらのホットスポット間のSNPは、高い確率で挙動を共にするが、この挙動を共にするSNPsを「連鎖不均衡の関係にある」という。これらのホットスポット間の1区画をブロックと考え、ハプロブロック(haploblock)という。HapMap Projectによってこの「ハプロブロック構造」が明らかになったため、ある数種類のSNPs(タグSNPs)の変化のみ調べればSNP全体の多様性が分かるようになった。

Haplotype(ハプロタイプ):一般には、一緒に(haplo-)遺伝する傾向のあるDNA変異または多型のことをいうが、ゲノム上に見られるSNPのセットまたはアレルの組み合わせのこともハプロタイプと呼ぶ。

Genome-wide association study; GWAS (ゲノムワイド関連解析):ある疾患(disease)や形質(trait)と関連があると考えられるSNPを、全ゲノムを対象に網羅的に検索し抽出する方法。疾患群(cases)と対照群(controls)からそれぞれDNAを抽出し、SNPチップ(SNP array)とハイブリダイズさせることにより、その疾患と有意に関連するSNPを検出する。ある座位のSNPの一方(アレル)が疾患群で有意に多く見られるとき、そのSNPが疾患と関連する(associated)と考える。

ここで用いるSNPは、全SNPである必要はなく、挙動を共にするSNP(連鎖不均衡の関係にあるSNP)があるため、ある種のタグSNP(lead SNP)について調べるだけでよい。全SNPの中でも、マイナーアレル頻度が5%以上のcommon SNPの1/10程度について調べれば、どのようなSNPのパターン(ハプロタイプ)に属するかが分かるとされている。したがって、現在明らかな1,000万のcommon SNPsから大体1/10の100万のタグSNPsを調べるため、1,000K SNPチップなどが用いられる。

通常、群間の差は、群間の違いが偶然である確率が5%未満(P<0.05)で「有意な差がある」と考える。しかし群の数が多い場合の群間の比較ではBoferroniの補正が用いられる。これは有意水準を決めるのに5%を群数で割ったものであり、100万SNPsで調べた(1,000KのSNPチップを用いた)場合は、0.05÷1,000,000=5x 10 -8、すなわちP<5x10 -8を有意水準とする。P値をlog変換し、-log10 P が8以上で有意に「疾患と関連する」などとされるのはこのため。

以下にGWASおよびそのメタアナリシスの概略図を示す(Manolio TA. Genomewide association studies and assessment of the risk of disease. N Engl J Med. 2010 Jul 8;363(2):166-76.より引用)
複数祖先集団GWASのメタアナリシスは、新たな2型糖尿病感受性座位の発見と微細地図解像度の上昇に有用_d0194774_1455385.jpg

上の図1Aでは、3人(Person 1, 2, 3)のゲノムにおける、染色体9番上のある小さい座位を示している。SNP1はPerson 1ではGGであるところが、Person 2ではGT、Person 3ではTTとなっている(同様にSNP2は、Person 1ではAAであるところが、Person 2ではAG、Person3ではGG)。ここではそれぞれ、最初が①頻度の多い「野生型の」ホモ型(common homozygote)、二番目が②ヘテロ型(heterozygote)、三番目が③頻度の少ない「多型」ホモ型(variant homozygote)とする。SNP1ではGがメジャーアレルでTがマイナーアレル、SNP2ではAがメジャーアレルでGがマイナーアレルである。
図1Bでは、疾患群(Cases)と対照群(Controls)の全DNAをSNPアレイで解析し、SNPsをゲノム全体で比較したところ、SNP1はP=1x10 -12、SNP2はP=1x10 -8の有意水準で「マイナーアレルが有意に関連している」ことが明らかになったことを示している。なお、ここで上記の①と(②+③)を比較するか(優性遺伝形式)、(①+②)と③を比較するか(劣性遺伝形式)、さらには①と②と③を比較するかは有意差が大きいものを取るとされている。
図1Cは、横軸に順番に染色体(番号ごとに色が変えてある)を並べ、その上のSNPを点で表している。縦軸はそれぞれの点(SNP)が疾患と関連する有意水準Pをlog変換で表している。このグラフ(signal plot)は、ニューヨークのマンハッタンにある高層ビル群をイメージさせることから「マンハッタンプロット」のニックネームで呼ばれる。この例では、SNP1が10の12乗、SNP2が10の8乗で有意に疾患に関連があることを示す(左のプロットでは同一線上にあるように見えるが、これを大きく拡大すると実際には右プロットのように染色体9番の上のずれた位置にある)。

このようにして明らかになったSNPを疾患の「感受性座位」(susceptibility loci)と呼ぶこれは、SNPの多型「だけ」で疾患が起こるわけではないが、そのSNPを含む多くのSNPsの多型の蓄積によって疾患が「起きやすくなる」、疾患発症が「影響される」=susceptibleと考えられるため。

なお、このようなシグナルが認められるハプロタイプブロックのすべてのSNP(タグSNPだけでなく分かりうるすべてのSNP)が疾患に関連するかを調べ、より強く関連するSNPを絞っていくことをファインマッピング(fine mapping; 微細地図作成)と呼ぶ。この微細地図(fine map)の解像度(fine-mapping resolution)を上げていくことが、GWASの精度を高めるには重要とされる。

なお、GWASで最終的に分かるのは、あくまでも「どのSNPが」疾患に関連しているかであり、「どの遺伝子(gene)」が関連しているかまでは分からない。しかし、特定されたSNPが近傍の遺伝子にどう影響しているかはexpression quantitative trait loci; eQTL(量的形質座位)解析の結果明らかになることがある。
複数祖先集団GWASのメタアナリシスは、新たな2型糖尿病感受性座位の発見と微細地図解像度の上昇に有用_d0194774_14564017.jpg

図1は疾患に関連のあるSNPsを検出するための集団(initial discovery set)を対象にしたものであった。上の図2はそこで明らかになったSNPsを確認し、偽陽性の結果を除外するために別の集団(replication set)を対象とした検討である。図2の例では3つの集団をreplication setとしており、一つ一つの検討では、このSNPが疾患に有意に関連していることは示されていない。しかし、これらのメタアナリシスを行うとこのSNPが強いシグナルとなって認められ、有意に疾患に関連していることが示されている。

【論文内容】
2型糖尿病(T2D)の疾患感受性に対するGWASは、大部分がヨーロッパ白人を祖先とした集団(European ancestry)を対象としたものである。近年は、東アジア人、南アジア人、メキシコ人およびメキシコ系アメリカ人、アフリカ系アメリカ人など他の祖先集団でも検討が行われ、ヨーロッパ白人とオーバーラップする結果が得られている。そこでこの研究では、多くの祖先集団のGWASの結果を組み合わせた「複数の祖先集団にわたる(trans-ancestry)」メタアナリシスを行った。これにより、より大きいサンプルサイズで解析ができ、また連鎖不均衡(LD)構造の異なる集団を対象とすることによって、T2D感受性座位の微細地図の解像度(fine-mapping resolution、感受性座位をいかに絞り込めるか)が強化されると考えられる。

研究の概要
現在までに報告されている4つの人種集団、すなわちDIAGRAM(ヨーロッパ人)、AGEN-T2D(東アジア人)、ST2D(南アジア人)、MAT2D(メキシコおよびメキシコ系アメリカ人)の各コンソーシアムの、合計26,488名の疾患群(case)と83,964名の対象群(control)を対象とした。遺伝的多様性を統一して検討するために、HapMap Projectによる250万のcommon SNPを用いてメタアナリシスを行った。

複数の祖先集団メタアナリシスによる新たな感受性座位の発見
現在までにT2D感受性座位として確立しているものは69個あり、それらのアレル効果(その座位のアレルが疾患発症に関与する影響度)の多様性を、祖先集団間で検討した。その結果、下記の3つの座位のSNPで大きな違いがあることが示された。すなわち、TCF7L2 (SNP番号:rs7903146)はどの集団でもT2Dと大きな関連があったが、その関連(疾患に関連するオッズ比)はヨーロッパ人集団で最も大きかった。一方、PEPD (rs3786897)とKLF14 (rs13233731)は、それぞれ東アジア人とヨーロッパ人でT2Dと大きな関連があった。今回、これら69個の確立したT2D感受性座位を除いた後に、複数の祖先集団で共通してT2D感受性座位(リスクアレル)と考えられるSNPの発見を試みた。

その結果、まず33個のSNPが同定された。これらに対し、ヨーロッパ人の疾患群21,491名と対照群55,647名を対象として、T2Dおよび他の代謝形質および心血管形質との関連を調べるreplication studyを行った。その結果、全ゲノムにおいて有意に(P<5x10 -8)T2Dと関連する7つの座位が新たに同定された(TMEM154、FAF1、POU5F1-TCF19、SSR1-RREB1、MPHOSPH9、LPP、ARL15)。これらの座位は、すべての祖先集団において比較的頻度の高いコモンなSNPで、T2Dへの効果は中等度のものであり、その点で上記のような集団間の多様性は見られなかった。

・これらの新しいT2D感受性座位の一つは、免疫に必要なMHC(major histocompatibility complex; 主要組織適合遺伝子複合体)内のPOU5F1-TCF19の近傍にあるSNPである。MHCにある1型糖尿病(T1D)のリスク座位がlatent autoimmune diabetes of adulthood (LADA)に関連があることが分かっており、これは臨床的にはT2Dと誤って診断されていることがある。
・また、新しい座位にはARL15およびSSR1-RREB1近傍のSNPsが含まれ、これらはそれぞれ空腹時インスリンと血中アディポネクチン値(さらにHOMA-IRで示されるインスリン抵抗性)および空腹時血糖(さらにHOMA-βで示されるインスリン分泌低下)と関連がある。
・新たなT2D感受性座位についていくつかの組織でeQTL解析を行ったところ、SSR1-RREB1座位が膵β細胞においてSSR1の、MPHOSPH9座位が肝においてABCB9および肺においてSETD8の、POU5F1-TCF19座位が単球においてHCG27の発現に強く影響していた。
・また、これらの新たな座位がどのようにT2D感受性に影響しているかも検討した。その結果、POU5F1-TCF19座位はTCF19のミスセンス変異(p.Val211Met)となっている、MPHOSPH9座位はABCB9、OFGOD2、PITPNM2のUTRの変異となっている、FAF1座位はインスリン転写調節に関わるELAVL4発現に関与するオープンクロマチン部位に存在することなどが明らかになった。

複数の祖先集団メタアナリシスによる感受性座位の微細地図解像度(fine-mapping resolution)の上昇
複数の祖先集団のGWASの結果のメタアナリシスにおいて、ベイズ統計学の手法であるMANTRA
http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3460225/
(Meta-ANalysis of Transethnic Association studies)ソフトウェアを用いた各集団データの統合を行った。その結果として、T2D感受性座位の微細地図解像度が上昇するか(SNPsの数が増加するか、SNPsの99%信頼セットのゲノム上間隔が短縮するか=感受性座位をいかに絞り込めるか)を検討した。

方法として、すでに確立した10のT2D感受性座位(JAZF1、SLC30A8、CDKAL1、HHEX/IDE、TCF7L2、IGF2BP2、FTO、CDKN2A/B、PPARG、MTNR1B)を対象に、ヨーロッパ人におけるメタアナリシス(疾患群12,171名と対照群56,862名)よりも複数祖先集団を統合したメタアナリシス(疾患群26,488名と対照群83,964名)の方がSNPsの99%信頼セットのゲノム上の間隔が短縮するかどうかを検討した。その結果、MTNR1Bを除いて、複数の集団を統合したメタアナリシスを用いてT2D感受性座位のSNP数が増加、または、感受性座位の微細地図解像度が上昇した。
複数祖先集団GWASのメタアナリシスは、新たな2型糖尿病感受性座位の発見と微細地図解像度の上昇に有用_d0194774_14503950.jpg

図3SLC30A8(rs13266634)のsignal plotsであり、上がヨーロッパ人でのGWAS、下が複数祖先集団を統合したGWASの結果を示している。下の方が微細地図の解像度(fine-mapping resolution)が上昇している。

【結論】
複数の祖先集団におけるT2D感受性座位のGWASでメタアナリシスをおこなうことにより、①新たなT2D感受性座位が明らかになり、また、②すでに知られているT2D感受性座位の微細地図の解像度が上昇した。このことは、従来のGWAS、特にヨーロッパ人の祖先集団のみのGWASでは関連が有意でなかったT2D感受性座位がまだ存在することを意味しており、これらの座位はサンプルサイズの大きい複数祖先集団のGWASメタアナリシスで検出できる可能性がある。


# by md345797 | 2014-04-28 18:08 | その他