Mar 2008
ランダムグラフの最大クラスターの成長過程
19/03/08 15:25 格納先: Mathematics
先日来読んでいるスチュアート・カウフマンの「自己組織化と進化の理論」（ちくま学芸文庫）に以下のようなことが書かれています。
１万個のボタンが（中略）ばらまかれているところを想像してみよう。ランダムに２つのボタンを選んで、それらを糸でつなぐ。今度は、このペアを下に置き、さらに２つのボタンをランダムに選ぶ。そして、それを取り上げて糸でつなぐ。これを続けるのである。（中略）しばらくして、ボタンはより大きなかたまり、つまりクラスターへと相互に連結されるようになる。（中略）ランダムグラフの重要な特徴は、糸とボタンの比を調節していったとき、非常に規則的は統計的振るまいを見せることである。とくに、糸とボタンの比が0.5を超えると、相転移が生ずる。この点において、「巨大なクラスター」が突然形成されるのである。
著者の言う比の値 0.5 はちょっと小さ過ぎるのではないかと思いましたので、Javaの練習のつもりでプログラムを書いてN=5000で走らせた結果が下のグラフです。横軸が糸の本数、縦軸が最大のクラスターのサイズです。2785回糸で結んだあたりで最大サイズのクラスターが倍増する様子が見え、小さな飛躍がありますが、その後は結構なだらかな増加であるように見えます。10000本の糸を使ったのですが、最大サイズは5000まで行きませんでした。つまり、全部のボタンがが繋がった状態には届かなかったということです。
これについて、同僚の八森先生からb Bela Bollobas の The evolution of random graphs という論文（Transactions of the American Mathematical Society, Vol. 286, No. 1. (Nov., 1984), pp. 257-274. ）を教えてもらいました。
１万個のボタンが（中略）ばらまかれているところを想像してみよう。ランダムに２つのボタンを選んで、それらを糸でつなぐ。今度は、このペアを下に置き、さらに２つのボタンをランダムに選ぶ。そして、それを取り上げて糸でつなぐ。これを続けるのである。（中略）しばらくして、ボタンはより大きなかたまり、つまりクラスターへと相互に連結されるようになる。（中略）ランダムグラフの重要な特徴は、糸とボタンの比を調節していったとき、非常に規則的は統計的振るまいを見せることである。とくに、糸とボタンの比が0.5を超えると、相転移が生ずる。この点において、「巨大なクラスター」が突然形成されるのである。
著者の言う比の値 0.5 はちょっと小さ過ぎるのではないかと思いましたので、Javaの練習のつもりでプログラムを書いてN=5000で走らせた結果が下のグラフです。横軸が糸の本数、縦軸が最大のクラスターのサイズです。2785回糸で結んだあたりで最大サイズのクラスターが倍増する様子が見え、小さな飛躍がありますが、その後は結構なだらかな増加であるように見えます。10000本の糸を使ったのですが、最大サイズは5000まで行きませんでした。つまり、全部のボタンがが繋がった状態には届かなかったということです。
これについて、同僚の八森先生からb Bela Bollobas の The evolution of random graphs という論文（Transactions of the American Mathematical Society, Vol. 286, No. 1. (Nov., 1984), pp. 257-274. ）を教えてもらいました。
