人工知能に関する断創録

このブログでは人工知能のさまざまな分野について調査したことをまとめています(更新停止: 2019年12月31日)

6次の隔たりの数学的証明

6次の隔たり(2005/3/27)の続き。

ミリグラムは6次の隔たりを確かめるために手紙を使った社会学的な実験を行っている(6次の隔たりのキーワードリンク参照)が、6次の隔たりを数学的に証明するという試みもあるそうだ。キーとなるのはグラフ理論

人をノードとし、人と人とのつながりを枝とする。60億(地球の人口)個のノードをばらまいてその間を枝でつなぐ。このとき、スモールワールド現象(6次の隔たり)が成り立つためには枝をどのようにつなげばよいか?

というのが問題になる。こう考えると社会学の問題を数学に置き換えることができる。では枝をどのようにつなげばいいのか?

  • 単にランダムにつなげる

ランダムに選んだ50人とつなげるとする。Aさんは50人とつながり、Aさんとつながっている各人がそのまた50人とつながっている。6次の隔たりでつながれる人は50の6乗。つまり、156億2500万人となる。地球の人口は60億人だから余裕でカバーできる!

欠点として、各自は異なる50人を知っているわけではない。互いに知り合っている場合の方が多い。それにランダムにつなげるというのはコミュニティや社会的集団の存在という現実にはそぐわないことがあげられる。

  • 近所を考慮して直近の50人とつなげる

友人、知人の概念を表せクラスターが形成される。ただし、遠くのクラスター(違う国に住んでいる)とは6次の隔たりでたどりつけなくなってしまう。

これらの結果から考えるとランダムと直近の中間のつなぎ方が妥当だろう。直近のつながりでクラスターを形成しつつ遠くの人とつながる架け橋が必要になる。マーク・グラノヴェターはこの架け橋を「弱い絆」と呼び、スモールワールド形成にとって重要な要素だと述べている。

複雑な世界、単純な法則  ネットワーク科学の最前線

複雑な世界、単純な法則 ネットワーク科学の最前線

の2章までを少しまとめてみた。結論は当たり前って感じもするなぁ。弱い絆がどうつながればよいかが分かってないからまだ証明はされてないのかな?なんにしてもグラフ理論に置き換えるという発想の転換に大変感動した。