複雑ネットワーク
このように、グラフ理論における既存の数学モデルは現実社会のネットワークを表現する上では一長一短といったところであったが、1998年にブレイクスルーが訪れた。ダンカン・ワッツとスティーヴン・ストロガッツが「ワッツ・ストロガッツモデル」(WSモデル)を発表したのである。
ワッツ・ストロガッツモデルでは次のアルゴリズムでグラフを生成する。
全ての頂点を、近隣の a 個の頂点と格子(1次元格子)状に辺で繋ぐ。
それらの辺を確率 p でランダムに張り替える。
パラメータ p を0とおけば格子、1とおけばランダムグラフとなる。p を0.1前後とすると、格子とランダムグラフをあわせもったような性質のグラフが生成される。ワッツ・ストロガッツモデルでは、ショートカットが形成される効果によって平均最短距離はほぼ L ∝ log n となり、スモールワールド性を満たす。同時に格子の構造を残していることで、クラスター係数は格子に近い値となりクラスター性をも満たす。
もっともワッツ・ストロガッツモデルにも限界があり、次数分布は格子とポアソン分布の中間となるのでスケールフリー性は満たさない。しかし、現実世界のネットワークに近いような性質を持つグラフを極めて単純なアルゴリズムで生成できることが関心を呼んだ。この研究に触発される形で、現実世界のネットワークが持つ性質への関心が高まり、またこの研究をさらに発展させた研究が続々と発表されていった。
グラフ理論は、18世紀にレオンハルト・オイラーが創始した学問で、この場合のグラフは頂点と辺の集合である。グラフ G は頂点(ノード、サイトともいう)の集合 V = {v1, v2, ..., vn} と辺(枝、リンク、ボンドともいう)の集合 E = {e1, e2, ..., em} によって記述される。頂点 i に繋がっている辺の本数をその頂点の次数 ki という。右図の例では、頂点1の次数は2、頂点2の次数は3である。頂点と辺のパターンを変えることによって様々な特性を持つグラフが生成される。
1959年にポール・エルデシュとアルフレッド・レーニィ(英語版)は、グラフの一種であるランダムグラフ(英語版)を作るエルデシュ=レーニィモデル(英語版)を考案した。エルデシュ=レーニィモデルは、各種の興味深い性質を有し、グラフの解析的な取り扱いを大きく進歩させた。だが、その後はグラフ理論の分野では目立った進展はあまり起きていなかった。
1960年代から70年代にかけて社会学で2つの動きがあった。第1は実験社会心理学者スタンレー・ミルグラムによる、いわゆるスモール・ワールド現象、日本語にすれば「世間は狭い」現象を実証しようという試みである。ミルグラムは1967年に考案した実験において、アメリカ内陸部の住人に手紙を渡し、全く面識のない東海岸の受取人へ向けて、郵便ではなく知人(ファーストネームで呼び合うような親しい間柄)経由で転送するように依頼し、届くまでに何人の仲介者が必要かを調べた。