Hatena::ブログ(Diary)

小人さんの妄想 このページをアンテナに追加 RSSフィード Twitter

2009-11-30

べき分布のメカニズム

べき分布」、あるいは「スケールフリーネットワーク」という言葉を聞いたことがありますか?

私もつい最近までは知りませんでした。

ベキ分布というのは、データの分布がベキ乗法則 f(x) = a x^-k に従う分布のこと。

私が「べき分布」に興味を持ったのは、人気投票で上位が票を独占する、というところからでした。

* 人気投票はベキ分布 >> id:rikunora:20090820

調べてみると、このベキ乗法則、身の回りのいろいろなところに見出せます。

人気投票や友達関係、インターネットや生体内の相互作用、などなど。

ただ、あちこちにベキ乗法則が見出せることはわかっても、なぜそうなるのか、

その理由が私にはよくわかりませんでした。

(前記事のコメントが全てのきっかけでした、fkさん、Thanks!


ところが最近、このベキ乗法則のメカニズムが書かれている本を見つけて「なるほど」と納得させられました。

新ネットワーク思考―世界のしくみを読み解く

新ネットワーク思考―世界のしくみを読み解く

この道の第一人者が書いた一般向けの本。内容はもちろんのこと、書きっぷりもいい。

インターネットに携わる人は必読かと。

複雑ネットワークの科学

複雑ネットワークの科学

上の本では物足りなかった本質的な内容が、数式も交えてしっかり解説してある。

べき分布の仕組みも、これでわかる。


ヒントは「ネットワーク」にあります。

べき分布が形成される様子を、とりあえず Flash にて再現してみました。まずはご覧あれ。

>> http://brownian.motion.ne.jp/memo/ScaleFreeNet.html

このFlashでは、左側の画面に200個の点をランダムに打っています。

この200個の点が、インターネット上のサイトだと思ってください。

右側の画面には、横軸にリンク数、縦軸にそのリンク数を持つサイトの数がグラフ表示されます。

要はリンク数のヒストグラムです。

画面には2つのボタン「ランダム」と「リンク数に比例」が付いています。

まずは「ランダム」を押してみましょう。

サイト同士が、全くランダムにリンクされてゆきます。(ここでは確率5%としています)

リンクが増えてゆくにつれて、ヒストグラムの形は平均を中心とした山型のカーブになると思います。

この山型のカーブは、いわゆる正規分布というやつです。 ポアソン分布という形になっています。

つまり、各サイトのリンク数は「平均値プラスマイナス誤差」というに近い形になっているわけです。

f:id:rikunora:20091130142008g:image

以上を確認したところで、もう1度「ランダム実行」ボタンを押すと実行が止まります。

(あるいは最大値の200で止まります)


次に「リンク数に比例」ボタンを押してみましょう。

今度もリンクが増えていって、ヒストグラが描かれるのですが、、、さっきと形が違っていますね。

今度の場合、大多数のサイトはのリンク数は最低数(2に設定している)なのに、

ごく一部の上位サイトだけが抜きんでて多数のリンクを獲得しています。

実は、このヒストグラムの形がベキ分布となっているのです。

f:id:rikunora:20091130142041g:image


何をしたのか。

今度の場合、リンクをランダムに張ったのではなくて、

「それまでサイトが持っていたリンク数に比例する確率で」張っていたのです。

インターネット上でリンクを張ろうと思ったとき、でたらめに張るより、

なるべくなら既にリンクがたくさん張られている人気サイトに張ろうと思いますよね。

たとえば、既にリンクを10本持っているサイトと、20本持っているサイトがあるとしたら、

20本持っているサイトの方が、10本のサイトの2倍の確率で新規リンクを獲得する、

そのようにしてあります。

人気のあるサイトが、ますます人気を獲得してゆく、、、

その結果が、上位人気独占という形になって表れているわけです。

>> wikipedia:複雑ネットワーク “バラバシ=アルバートモデル”を参照。


まとめると、

・ランダム    => 正規分布 ポアソン分布

・リンク数に比例 => べき分布

ということです。

言われてみると結果はシンプルなのですが、

試しにやってみないことには、なかなか気付かないですよ、これ。

ベキ乗法則はインターネットを始め、いろいろなところに見出されますが、

その全てが必ずしも「リンク数に比例」モデルで説明し尽くせるわけではないと思います。

例えばインターネット1つ取っても、そこにはリンク数の他にもいろいろな要因が絡んでいるでしょう。

そういった点では、この「リンク数に比例」は最も単純なモデルであり、

ここからさらに様々な発展型モデルが考えられるわけです。


ベキ乗法則は、シンプルにして強力なツールだと改めて実感しました。

サイトのアクセス数を調べるにしても、インフルエンザ感染を調べるにしても、

こういった「ネットワーク思考」は欠かせないでしょう。


fkfk 2009/12/01 19:03 これは一般の人にもわかりやすい説明ですね!フラッシュがあるのでイメージしやすいですし。これでネットワークのことがもっと一般の人にも知られれば嬉しいです。

ただランダムにリンクを張っていく場合は、正規分布ではなくてポアッソン分布になります。スパゲッティの麺を床に落として複数本に折れたときの長さの分布と同じです。

rikunorarikunora 2009/12/03 13:46 おかげさまで、すっかりネットワークの虜になりました。奥が深いですね。
分布の形が見えたときには、なるほど、へーっ!と思いました。

“正規分布ではなくてポアッソン分布”ご指摘ありがとうございます。
「スパゲッティの麺を床に落として複数本に折れたときの長さ」
これまた、へーっ! 一度試しにやってみます。

T_NAKAT_NAKA 2009/12/06 08:30 そのスパゲッティの話はこれと関係あるんでしょうかね?
http://med-legend.com/mt/archives/2005/07/post_607.html

rikunorarikunora 2009/12/08 12:47 スパゲッティ奥深し!
実はその後スパゲッティを買ってきてやってみたのですが、
すぐにわかったのは、床に落としたくらいでは簡単に折れない、ということでした。
とほほ、、、上手い折り方を模索中。
あと、試しに手元にあったシャーペンの芯を折ってみたら、本当に3つになりました。おどろき。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/rikunora/20091130/p1