複雑ネットワークの理論(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〉)を持つ頂点、すなわちハブがある程度存在する。

図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％の頂点が消失しても、ネットワークに残った頂点どうしの交通には影響が見られない。スケールフリー・ネットワークのの連結は、ベキ法則に従う分布のため、ごく少ない枝しか持たない頂点が大多数を占めており、ランダムに頂点が消失する場合このような「小さい」頂点が消失する確率が大きいので、残った頂点間の経路に与える影響はほとんどなく、ネットワーク全体のトポロジーは全く変わらないといってもよい。

図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：ネットワークにおけるエラーまたは攻撃に対するネットワークの断片化
図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にまとめた。スケールフリー・ネットワークでエラーが起きた場合(図の下側)は、クラスター断片化がほとんど起こらず、指数関数的ネットワークと比較すると「エラー耐性が強い」と考えられる。また、指数関数的ネットワークでのエラーと攻撃、スケールフリー・ネットワークでの攻撃に対しては、同じような急速なクラスター断片化が起こる(図の上側)。すなわち、スケールフリー・ネットワークの「攻撃に対する脆弱性」が理解できる。

図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といったコミュニケーションネットワークにとっては脅威になるものだが、ネットワークに本質的に内在する不均一な性質自体が攻撃に対する脆弱性をもたらしているのだから、その対策は今後詳しく検討されるべきであろう。