組合せとグラフの理論(塩田)第15回 (1) 複雑ネットワーク
戻る / 次へ
$\newcommand{\ol}[1]{\overline{#1}}$
$\newcommand{\card}[1]{\left|\,#1\,\right|}$
スモールワールド
ドラえもんのひみつ道具のひとつに
「七人の知り合い」 というものがあります。
知り合いの知り合いを辿って、必ず7人目までにどんな人ともつなげてしまうという道具です。
(ちょんまげ型をしているのは
映画「七人の侍」 から名前をもじったから、のようです。)
この、「知り合いの知り合いを辿ると必ず7人目までにどんな人ともつながっている」という仮説は「スモールワールド現象」と呼ばれ、
1967年に行われたイェール大学ミルグラム教授の実験で広く知られるようになりました。
複雑ネットワーク
複雑ネットワークとは、現実世界の巨大かつ複雑なネットワークを研究する学問分野です。
上記の「スモールワールド性」を含め、現実世界のネットワークは次の3つの性質を持つと考えられます:
- スケールフリー性 :
次数の大きい頂点もあれば小さい頂点もある
- スモールワールド性 :
任意の2頂点間の最短距離は意外に短い
- クラスター性 :
ひとつの頂点の隣接点同士も、結構、隣接していることが多い
人間関係としては、それぞれ
- スケールフリー性 :
顔の広い人もいれば、付き合いの狭い人もいる
- スモールワールド性 :
間に顔の広い人をはさむと、どんな人とも意外に近かったりする
- クラスター性 :
あちこちにコミュニティができている
といったことになります。
現実社会のネットワークをシミュレートする為には、
この3条件を満たすネットワーク・モデルを生成するアルゴリズムが必要であり、
そのようなアルゴリズムの研究も進んでいます。