『複雑ネットワーク』
グラフ理論における「グラフ」はノードとエッジの集合である。
グラフ G はノード(頂点ともいう)の集合 V = {v1, v2, ..., vn} とエッジ(枝、弦、リンク、紐帯ともいう)の集合 E = {e1, e2, ..., em} によって記述される。
ノード i に繋がっているエッジの本数をそのノードの次数 ki という。(図1では、ノード1の次数は2、ノード2の次数は3である)
ノードとエッジのパターンを変えることによって様々な特性を持つグラフが生成される。
グラフ理論は18世紀にレオンハルト・オイラーが創始した学問であるが、20世紀に理論に重要な影響を与えたのはポール・エルデシュの業績であった。
1959年にエルデシュとアルフレッド・レーニィが考案した「ランダムグラフ」(エルデシュ＝レーニィモデル、ERモデル)は、各種の興味深い性質を有し、グラフの解析的な取り扱いを大きく進歩させた。
だが、その後はグラフ理論の分野では目立った進展はあまり起きていなかった。
1960年代から70年代にかけて社会学で2つの動きがあった。
第1は実験社会心理学者スタンレー・ミルグラムによる、いわゆるスモール・ワールド現象、日本語にすれば「世間は狭い」現象を実証しようという試みである。
ミルグラムは1967年に考案した実験において、アメリカ中西部の住人に手紙を渡し、全く面識のない東部の受取人へ向けて、郵便ではなく知人(ファーストネームで呼び合うような親しい間柄)経由で転送するように依頼し、届くまでに何人の仲介者が必要かを調べた。
結果は、平均して6人を仲介するだけで届くというものであった。
第2は、社会学者マーク・グラノヴェッターが発見した「弱い紐帯の重要性」と呼ばれる性質である。
グラノヴェッターは1973年の論文において、人々が職を探す活動をする際に有効な紹介者となるのは、親友や家族などの身近な付き合いのある「強い紐帯」の間柄ではなく、ごくまれに接するような「弱い紐帯」の間柄であることを見出した。
以降、こうした社会的ネットワークの性質は主に社会学の研究対象となってきたが、1998年にブレイクスルーが訪れた。
コーネル大学の博士課程の学生だったダンカン・ワッツと指導教官だったスティーヴン・ストロガッツは、多数のホタルの明滅やコオロギの鳴き声が同調する現象を究明する中で、「スモールワールドモデル」(WSモデル)という数学モデルを考案し、同様の性質が映画俳優の共演関係や、電力系統、線虫の神経細胞など、現実世界の様々なネットワークにも共通して存在することを発見した。
研究成果は『ネイチャー』に発表され、これに触発された研究によって、インターネット、食物連鎖、さらには論文の被引用関係や言語の文法構造といったネットワークにおいても同様の性質が発見された。
こうして、社会学、経済学、情報工学、生物学などの幅広い分野において「複雑ネットワーク」という新たなパラダイムが注目を集めることになった。
『現実世界のネットワークの性質』
現実世界に存在するネットワークは多様であり、巨大で複雑な構造を有しているが、一定の共通する性質を見出すことができる。
それらの性質は「スケールフリー性」(次数分布のべき乗則)、「スモールワールド性」、「クラスター性」と呼ばれている。
< スケールフリー性 >
図２ [完全グラフ K6]
現実世界のネットワークが持つ第1の性質は「スケールフリー性」(次数分布のべき乗則)である。
これは、一部のノードが他のたくさんのノードとエッジで繋がっており、大きな次数を持っている一方で、大多数のノードはごくわずかなノードとしか繋がっておらず、次数は小さいという性質である。
次数の大きなノードは「ハブ」とも呼ばれる。
スケールフリー性は、社会学をはじめとするこれまでの研究により、現実世界のネットワークで幅広く観察されている。
例えば、人々の持っている知人関係の数をみると、一部の人は非常にたくさんの知人を持っているが、大多数の人々の知人の数は限られている。
WWWではごく少数の有名サイトが数百万単位のリンクを集めているが、大多数のサイトはわずかなリンク先からしかリンクされていない。
生体内の相互作用でも、ごく一部のたんぱく質が多数のたんぱく質と反応する構造になっている。
男女の性的関係でも、ごく一部の人は何百人という相手と関係するが、大多数の人々は限られた相手としか関係を持たない。
数学的には、スケールフリー性はノードが次数 k を持つ確率 p(k) の確率分布が p(k) ∝ k-γ のべき乗則になると表現される。
このような次数分布では、分布の偏りを特徴付ける平均的な尺度(スケール)といったものが存在しない。
グラフがこのような性質を持つことを「スケールフリー」と呼ぶ。
また、このような確率分布のとき分散 V は無限大となる。
スケールフリー性を持つグラフを数学モデルで表現することができるだろうか。
まず、n 個のノードの間に全てエッジを張った「完全グラフ」 Kn を考えてみる。
完全グラフでは全てのノードの次数は n-1 であるからスケールフリー性を全く満たさない。
「格子」状のグラフでも同様である。
図2のような2次元の三角格子を考えてみると、全てのノードの次数は6であるから、やはりスケールフリー性を満たさない。
それではランダムグラフではどうであろうか。
ランダムグラフはエッジを生成確率 p でランダムに張るものである。ノード数を n とするとノードの次数が k となる確率は p(k) = n-1Ck pk(1-p)n-1-k の二項分布となり、n→∞、p→0、np→λ の極限では p(k) = e-λλk / k! のポアソン分布となる。ポアソン分布では全てのノードの次数は平均値の周辺に分散 λ で分布しており、べき乗則の分布には程遠い。
< スモールワールド性 >
図３ [2次元格子]
現実世界のネットワークが持つ第2の性質は「スモールワールド性」である。
これは、任意の2つのノードが、中間にわずかな数のノードを介するだけで接続されるという性質である。
上述のミルグラムの実験は現実世界のスモール・ワールド現象を最初に実証しようとした試みであるが、近年の研究ではネットワークのスモールワールド性が実際に測定されている。
例としてしばしば取り上げられるのは「エルデシュ数」である。
先に登場した数学者ポール・エルデシュと論文を共著で執筆したことのある数学者のエルデシュ数を1、エルデシュ数 e の数学者と共著関係にある数学者のエルデシュ数を e+1 とする。
世界中の数学者のエルデシュ数を調べてみると、大部分はエルデシュ数5から6程度で繋がっている。
「ベーコン数」という遊びもある。
アメリカの俳優ケヴィン・ベーコン(起点は誰でも良いのだが)と映画で共演したことのある俳優のベーコン数を1、ベーコン数 b の俳優と共演関係にある俳優のベーコン数を b+1 とする。
世界中の俳優のベーコン数を調べてみると、大多数がベーコン数3から4の範囲に収まる。
数学的には、スモールワールド性はグラフの「平均最短距離」(固有パス長もしくは直径ともいう) L がノード数 n の大きさに比べて小さい値となることで表現される。
無方向・重み無しのグラフにおいて、任意のノード vi からノード vj へ行くまでに通過しなければならないエッジの最小の本数を「パス長」(距離ともいう)、パス長の中で最短のものを ij 間の「最短距離」 dij と呼ぶが、dij の平均値がそのグラフの平均最短距離である。
グラフにおいて n が増大したときに L が高々 log(n) に比例する程度でゆるやかに増加するとき、そのグラフはスモールワールド性を満たすと定義される。
スモールワールド性を持つグラフを数学モデルで表現することができるだろうか。
まず図3のような2次元格子を考えると、グラフの端から端まで行くためにはいくつものノードを経由せねばならない。
すなわち L は√n に比例する。n が増大すると L もかなり増大してしまうので、スモールワールド性を満たさない。
一方、ランダムグラフではノードがランダムに繋がっているので、格子の場合と違って近道がありそうである。
実際、ランダムグラフでは L = log(n) / log(pn) ∝ log(n) となる。この点では、ランダムグラフは現実世界のネットワークに近いといえる。
< クラスター性 >
図４ [ランダムグラフ]
現実世界のネットワークが持つ第3の性質は「クラスター性」である。
身の回りの知人関係のネットワークを見てみよう。
「自分と知人Aさんがいるときに、自分もAさんもどちらも知っている共通の知人Bさんのような人が1人もいない」という状況は、出会い系サイトでも利用しない限りまずありえない。
すなわち、現実世界のネットワークには、自分、Aさん、Bさんから構成される三角形のネットワークがたくさん含まれている。
このような性質を、ワッツとストロガッツは「クラスター性」と名づけた。
数学的には、クラスター性はグラフの「クラスター係数」 C が十分大きな値を取ることで表現される。
グラフにおいて任意のノード vi と vj、同じく vi と vk が共にエッジで繋がっているような組み合わせの数を N3、vi、vj、vk が三角形で繋がっているような組み合わせの数を NΔ とする。
このグラフのクラスター係数は C = 3NΔ / N3と定義される。
クラスター係数は現実世界の各種のネットワークにおいて計測されており、それらの値は0.1から0.7程度と報告されている。
クラスター性を持つグラフを数学モデルで表現することができるだろうか。
まずランダムグラフでは、全てのエッジはランダムに生成されるのであるから、都合よく三角形が形成される確率はきわめて低い。
エッジの生成確率 p の値にもよるが、p が小さければクラスター係数はほぼ0となるのでクラスター性を満たさない。
一方、2次元の三角格子では、図4でわかる通り三角形が多数含まれている。
2次元の三角格子のクラスター係数は 6 / 6C2 = 0.4 となる。
格子のクラスター係数は十分に大きく、この点では現実世界のネットワークに近いといえる。
『複雑ネットワークのモデル』
図５ [1次元格子]
< スモールワールドモデル >
図６ [1次元格子からのスモールワールドモデルの生成]
このように、グラフ理論における既存の数学モデルは現実社会のネットワークを表現する上では一長一短といったところであったが、1998年にブレイクスルーが訪れた。
ダンカン・ワッツとスティーヴン・ストロガッツが「スモールワールドモデル」(ワッツ＝ストロガッツモデル、WSモデル)を発表したのである。
スモールワールドモデルでは次のようなアルゴリズムでグラフを生成する。
1. 全てのノードを、近隣の a 個のノードと格子(1次元格子)状にエッジで繋ぐ。
2. それらのエッジを確率 p でランダムに張り替える。
パラメータ p を0とおけば格子、1とおけばランダムグラフとなる。
p を0.1前後とすると、格子とランダムグラフをあわせもったような性質のグラフが生成される。
スモールワールドモデルでは、ショートカットが形成される効果によって平均最短距離はほぼ L ∝ log n となり、スモールワールド性を満たす。
同時に格子の構造を残していることで、クラスター係数は格子に近い値となりクラスター性をも満たす。
もっともスモールワールドモデルにも限界があり、次数分布は格子とポアソン分布の中間となるのでスケールフリー性は満たさない。
しかし、現実世界のネットワークに近いような性質を持つグラフを極めて単純なアルゴリズムで生成できることが関心を呼んだ。
この研究に触発される形で、現実世界のネットワークが持つ性質への関心が高まり、またこの研究をさらに発展させた研究が続々と発表されていった。
< バラバシ＝アルバートモデル >
図７ [バラバシ＝アルバートモデル]
1999年、アルバート＝ラズロ・バラバシとレカ・アルバートはスケールフリー性を持つグラフの数学モデルを考案した。
「バラバシ＝アルバートモデル」(BAモデル)では次のようなアルゴリズムでグラフを生成する。
やはり、極めて単純なアルゴリズムである。
1. m 個のノードからなる完全グラフ Kmをスタートとする。
2. 新しいノードを1個追加する。そのノードから、すでに存在している m個のノードに対してエッジを張る。
このとき、エッジが張られる確率は、それぞれのノードのその時点での次数 k に比例するものとする。
3. 2を、ノードが所定の数になるまで繰り返す。
バラバシ＝アルバートモデルでは、既存の次数の大きなノードに対して新しいエッジが高い確率で加わってゆき、そのノードがハブへと成長してゆく。(図7で一番上にあるノードがハブに相当する)
このモデルではノードの次数分布は p(k) = 2m(m+1) / [k(k+1)(k+2)] ∝ k-3 となり γ = -3 のスケールフリー性を満たす。
モデルはランダムグラフと似たところもあるので、平均最短距離は L ∝ log nとなりスモールワールド性をも満たす。
『スケールフリーグラフの頑強性と脆弱性』
スケールフリーグラフが持つ注目すべき特性として、ネットワーク障害に対する頑強性が高いことがあげられる。
スケールフリーなトポロジーを持つネットワークでは、全ノードのうちの5パーセントがダウンしたとしても、代替経路の存在によってノード間の接続を維持でき、系全体の平均経路長(平均最短距離)はほとんど変化しないのである。
同じノード数、同じエッジ数でトポロジーが異なる他のネットワークではこのような特性は見られない。
一方で、スケールフリーなネットワークは、特定の重要なハブをピンポイントで狙った攻撃に対しては脆弱であるという弱点も併せ持っている。
次数の集中した上位5パーセントのノードがダウンしたとすると、系全体の平均経路長は約2倍にまで増大してしまう。
同様の特性は自然界の食物連鎖のネットワークでも観察されている。
食物連鎖のネットワークは生物種のランダムな絶滅に対しては頑強であるが、特定の重要な種が絶滅すると大きな影響を受けてしまう。
こうした点を考慮することは生物多様性に関する議論においても重要であろう。
『複雑ネットワーク研究の現状と今後』
2008年現在、複雑ネットワークの研究は急速に進展しており、他の研究分野との相互影響も活発化している。
そうした中で、「コミュニティ構造」などの現実世界のネットワークを分析するための新たな視点が提案され、「スケールフリー性」、「スモールワールド性」、「クラスター性」といった従来からの分析指標はもはや”古典的”な部類に属するものとなりつつある。
今後、複雑ネットワークの科学は、堅牢な通信ネットワークの構築、感染症の予防、口コミのマーケティングといった、ネットワークの問題が関連する多数の分野において、普遍性と重要性を増していくものと予想される。
『情報のストレス緩和と問題点』
左図のようなネットワークを縦系列の企業に例えると、Aのノードが上司でB、Cのノードが部下になる。
例えば社員Bの企画書を上司Aに提出し、その企画が通りプロジェクトを進めることになり、社員Cに資料収集を求めた時、情報は一度、上司Aを経由するためタイムラグが発生する。
しかし、右図のようなネットワークが構築されていれば、情報が共有されているためタイムラグは左図よりも短くなる。
しかし、この時、注意しなくてならないのは、情報管理(情報モラル・セキュリティ)やリテラリーに関する教育が必要となる。
『インターネットにおけるネットワークの構築と拡散』
インターネットにおいてユーザー間のネットワークは、メールやSNS、コミュニティなど限られたスペースで構築されるぐらいで、さほど大きなネットワーク構築にはならない。
図のA、B、C、Dのようなハブ的な存在が、そう言ったユーザーを収束している。
このハブ的存在がYahoo!であったり、Googleであったりする。
【 参考文献 】
・Wikipedia
・「新ネットワーク思考 ～ 世界のしくみを読み解く ～」 アルバート・ラズロ・バラバン著