スモールワールド性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/26 11:37 UTC 版)
「複雑ネットワーク」の記事における「スモールワールド性」の解説
現実世界のネットワークが持つ第2の性質は「スモールワールド性」である。これは、任意の2つの頂点が、中間にわずかな数の頂点を介するだけで接続されるという性質である。上述のミルグラムの実験は現実世界のスモール・ワールド現象を最初に実証しようとした試みであるが、近年の研究ではネットワークのスモールワールド性が実際に測定されている。 例としてしばしば取り上げられるのは「エルデシュ数」である。先に登場した数学者ポール・エルデシュと論文を共著で執筆したことのある数学者のエルデシュ数を1、エルデシュ数 e の数学者と共著関係にある数学者のエルデシュ数を e+1 とする。世界中の数学者のエルデシュ数を調べてみると、大部分はエルデシュ数5から6程度で繋がっている。「ベーコン数」という遊びもある。アメリカの俳優ケヴィン・ベーコン（起点は誰でも良いのだが）と映画で共演したことのある俳優のベーコン数を1、ベーコン数 b の俳優と共演関係にある俳優のベーコン数を b+1 とする。世界中の俳優のベーコン数を調べてみると、大多数がベーコン数3から4の範囲に収まる。 The Oracle of Bacon at Virginia - ベーコン数がわかるサイト 数学的には、スモールワールド性はグラフの「平均最短距離」（固有パス長もしくは直径ともいう） L が頂点数 n の大きさに比べて小さい値となることで表現される。無方向・重み無しのグラフにおいて、任意の頂点 vi から頂点 vj へ行くまでに通過しなければならない辺の最小の本数を「パス長」（距離ともいう）、パス長の中で最短のものを ij 間の「最短距離」 dij と呼ぶが、dij の平均値がそのグラフの平均最短距離である。グラフにおいて n が増大したときに L が高々 log(n) に比例する程度でゆるやかに増加するとき、そのグラフはスモールワールド性を満たすと定義される。 スモールワールド性を持つグラフを数学モデルで表現することができるだろうか。まず2次元格子を考えると、グラフの端から端まで行くためにはいくつもの頂点を経由せねばならない。すなわち L は√n に比例する。n が増大すると L もかなり増大してしまうので、スモールワールド性を満たさない。一方、ランダムグラフでは頂点がランダムに繋がっているので、格子の場合と違って近道がありそうである。実際、ランダムグラフでは L = log(n) / log(pn) ∝ log(n) となる。この点では、ランダムグラフは現実世界のネットワークに近いといえる。
※この「スモールワールド性」の解説は、「複雑ネットワーク」の解説の一部です。
「スモールワールド性」を含む「複雑ネットワーク」の記事については、「複雑ネットワーク」の概要を参照ください。
- スモールワールド性のページへのリンク
