組合せとグラフの理論(塩田)第15回 (1) 複雑ネットワーク

戻る / 次へ $\newcommand{\ol}[1]{\overline{#1}}$ $\newcommand{\card}[1]{\left|\,#1\,\right|}$

スモールワールド

 ドラえもんのひみつ道具のひとつに 「七人の知り合い」 というものがあります。 知り合いの知り合いを辿って、必ず7人目までにどんな人ともつなげてしまうという道具です。 (ちょんまげ型をしているのは 映画「七人の侍」 から名前をもじったから、のようです。)

 この、「知り合いの知り合いを辿ると必ず7人目までにどんな人ともつながっている」という仮説は「スモールワールド現象」と呼ばれ、 1967年に行われたイェール大学ミルグラム教授の実験で広く知られるようになりました。

複雑ネットワーク

 複雑ネットワークとは、現実世界の巨大かつ複雑なネットワークを研究する学問分野です。 上記の「スモールワールド性」を含め、現実世界のネットワークは次の3つの性質を持つと考えられます:
  1. スケールフリー性
    次数の大きい頂点もあれば小さい頂点もある
  2. スモールワールド性
    任意の2頂点間の最短距離は意外に短い
  3. クラスター性
    ひとつの頂点の隣接点同士も、結構、隣接していることが多い
人間関係としては、それぞれ
  1. スケールフリー性
    顔の広い人もいれば、付き合いの狭い人もいる
  2. スモールワールド性
    間に顔の広い人をはさむと、どんな人とも意外に近かったりする
  3. クラスター性
    あちこちにコミュニティができている
といったことになります。

 現実社会のネットワークをシミュレートする為には、 この3条件を満たすネットワーク・モデルを生成するアルゴリズムが必要であり、 そのようなアルゴリズムの研究も進んでいます。