とはずがたり数理解析研究所講究録 - 1489154682

1：とはずがたり：2017/03/10(金) 23:04:42: 名前負け及び過疎スレ化必至で恥ずかしいけど数学綜合スレ。
15：とはずがたり：2017/12/23(土) 07:26:12: 複雑ネットワークの理論(2)　スケールフリー・ネットワークの提唱
http://syodokukai.exblog.jp/20771928/
Emergence of scaling in random networks.

Barabasi AL, Albert R.

Science. 1999 Oct 15;286(5439):509-12.

【背景】
複雑ネットワークを考えるときに、1998年に提唱されたスモールワールド・ネットワーク (ワッツ・ストロガッツモデル)は画期的なものだった。しかし、現実のネットワークにはハブ(枝の数が非常に大きい頂点)が存在し、これはスモールワールド・ネットワークでは説明できない。このことに直面したノートルダム大学のアルバート・ラズロ・バラバシは、それまでのネットワークモデルにおけるランダムな世界観を捨てて、新しいモデルの構築を目指した。
d0194774_146426.jpg
Albert-Laszlo Barabasi (1967-)　以下の背景の多くは、バラバシの著書『新ネットワーク思考―世界のしくみを読み解く』(青木薫訳、NHK出版)によっている。

① 「ハブ」の存在
現実社会の友人ネットワークについて考えてみると、大多数の人は友人の数は数名だが、「友人の数がずば抜けて多い」人物が何人かはいる。これはウェブでも同様で、全ドキュメント(1999年で10億以上と言われる)の90％以上はリンクされる数は10以下であるが、ごく少数のページは100万近くリンクされている。後者はネットワーク上では「ずば抜けて枝の多い頂点」であり、ハブと呼ばれる。このハブは現実に存在するにもかかわらず、エルデシュのランダムネットワークでやワッツ・ストロガッツのスモールワールド・ネットワークでは生じない。では、ハブが生じるネットワークとはどのようなものなのか？

②　ベキ法則
1900年代、イタリアの経済学者ヴィルフレード・パレートは、「収入分布は“ベキ法則”にしたがう」ことを発見。これは「世の中にはごく一握りのきわめて収入の多い人たちがおり、人口の大多数はわずかな収入しかない」ということを表す法則であり、後にパレートの法則とか「80対20の法則」などと呼ばれた(世の中のお金の80％は人口の20％の人という一握りの人たちが持っており、お金の20％はその他大勢の80％が持っている、ということ)。

これをネットワークでは、頂点の枝の数の度数分布として考える。枝の数がkである頂点の数をN(k)とし、全頂点についてkを横軸、Nの頻度を縦軸にプロットする。その結果は下記の式のようになる。

N(k)=1/k^r

これは、一般的には

f(x)=a x^k

で表される「ベキ法則 (power law)」に従うプロットとなる。(aは定数、kはスケーリング指数と呼ばれる定数で、ここではマイナスの値になる。「ベキ法則」は、べき乗則、ベキ則などとも訳される。ベキ(冪)乗は今では累乗と同じことだが、もともとは累乗と混同されて用いられ始めた用語らしい。「冪」の字は当用数字に含まれないため「ベキ」のように書かれる。)…

③ スケールフリー・ネットワーク
ベキ法則は、正規分布(釣鐘型の分布)とは違って、①どこにもピークがなく、なめらかに減少する、②分布のすそ野は正規分布よりも広い、③ごく少数のきわめて大きい事象と無数の小さい事象が共存する状態を表すなどの特徴を持つ。バラバシは、枝の数と頂点の数がベキ法則に分布をスケールフリー・ネットワークと呼んだ。
16：とはずがたり：2017/12/23(土) 07:26:39: >>15-16

スケールフリー・ネットワークはグラフで見ると分かるように、「平均的な数」の枝をもつ頂点というものは存在しない。枝の数には、なめらかに減少するヒエラルキーがあるのみである(これは「ロングテール」とも呼ばれる)。この分布は、ある枝の数を持つ頂点数に平均や分散などの尺度(スケール)が存在しないので「スケール」「フリー」と名付けられた。

下の図は、『新ネットワーク思考―世界のしくみを読み解く』(アルバート・ラズロ・バラバシ、青木薫訳)より改変引用させていただいた。左は従来考えられていたランダムネットワークで、k本の枝を持つ頂点の数N(k)は確率的に分布するため、正規分布に従っている。ここでは、ずば抜けて多くの枝を持つ頂点が存在する確率はきわめて低い(存在しない)。右はスケールフリー・ネットワークで、k本の枝を持つ頂点の数はベキ法則に従う。大多数の頂点はごく少ない数の枝しか持たないが、一部のごく少数の頂点は莫大な多さの頂点を持つことを表している。それぞれの下に例として、都市をつなぐ高速道路網(ランダムネットワーク)と、空港をつなぐ航空経路網(スケールフリー・ネットワーク)が示されている、左では高速道路がものすごく多数集中する都市などというものは存在しないが、右では航空便が非常に多く集まる空港(ハブ空港)がいくつか存在している。このようにスケールフリー・ネットワークはランダムネットワークとは全く異なるネットワークである。

http://syodokukai.exblog.jp/iv/detail/?s=20771928&i=201406%2F03%2F74%2Fd0194774_2161124.jpg

（そもそも、確率に支配されるようなランダム・無秩序な事象は正規分布に従うとされる。一方、そこから秩序が生まれると(秩序の創発、相転移とも呼ばれる)、ベキ法則に従うようになると言われる。したがって、現実のネットワークは、全く無秩序な状態ではなく、秩序が創発した、ちょうど相転移を起こしたような状態でありベキ法則に従うことが多いとされる。なぜ、相転移でベキ法則が出現するかは、1971年にケネス・ウィルソンによる「繰り込み群」理論で証明されている。）

④ 「ネットワークの成長」と「ハブの優先的選択」
ランダムモデルは、(a)頂点は最初からすべて存在し、頂点数は一定という仮説の上に成り立っていた。(b)すべての頂点は対等という仮定もあり、互いに区別できないからこそランダムにリンクできたといえる。しかし、現実に存在するネットワークでは(a)(b)のような仮定は成り立たない。

現実のネットワークは、(1)頂点は1つ1つ増えていく(ネットワークは成長する)。(2)すでに多くのリンクを獲得している頂点(ハブ)は、新しくできた頂点から高い確率でリンクされる(ハブは優先的に選択される)、という2つの特徴を示す。バラバシは、この(1)と(2)の特徴を両方組み込むと、ネットワークはスケールフリーになることを以下の論文で示している。

ここに来て、古典的なモデル(ランダムグラフやスモールワールド・ネットワーク)は「静的」(?成長する)で、「ランダム性の仮定の上に成立」(?優先的選択)していたことに初めて気づいたわけである。