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

一人抄読会

syodokukai.exblog.jp
ブログトップ

複雑ネットワークの理論(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