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

一人抄読会

syodokukai.exblog.jp
ブログトップ

複雑ネットワークの理論(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つの特徴を満たすことが実証された。
d0194774_2034041.png
Duncan J. Watts (1971-)
現実のネットワークは平均距離が小さく、かつクラスター化されている。全く規則的なグラフではクラスター化はされているが平均距離は大きい。一方、ランダムグラフでは、平均距離は小さいものの、クラスター化されていない。それらの折り合いをつけて、現実のネットワークに近いモデルとして提唱されたのが、後述ののスモールワールド・ネットワークであった。

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



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

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

図1左のように、n個の頂点にそれぞれ枝がk本ある規則的な格子(lattice)グラフがあるとする。この枝をすべて確率pでランダムにつなぎかえる。それにより、p=0で規則的な格子、p=1でランダムなグラフの間を調節することができる。今まで、このpが0と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も小さい。(高度にクラスター化されていれば平均距離が大きく、クラスター化が少なければ平均距離も小さい=スモールワールド)
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を計算すると、これらがすべてスモールワールド・ネットワークを示していることが明らかになった。したがって、スモールワールド現象は人工的・社会的ネットワークだけでなく、自然界の大きいネットワークに普遍的に見られる現象と思われる。

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)が減少することを表す。すなわち、意外と少ないランダムなショートカットがあれば、簡単にランダムネットワークと同じ程度急速な感染症拡大が起きるようになる。
d0194774_20223456.gif

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

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

[PR]
by md345797 | 2014-05-30 03:03