べき分布のメカニズム

「べき分布」、あるいは「スケールフリーネットワーク」という言葉を聞いたことがありますか？
私もつい最近までは知りませんでした。
ベキ分布というのは、データの分布がベキ乗法則 f(x) = a x^-k に従う分布のこと。
私が「べき分布」に興味を持ったのは、人気投票で上位が票を独占する、というところからでした。
* 人気投票はベキ分布 >> d:id:rikunora:20090820
調べてみると、このベキ乗法則、身の回りのいろいろなところに見出せます。
人気投票や友達関係、インターネットや生体内の相互作用、などなど。
ただ、あちこちにベキ乗法則が見出せることはわかっても、なぜそうなるのか、
その理由が私にはよくわかりませんでした。
（前記事のコメントが全てのきっかけでした、fkさん、Thanks!）

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

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

この道の第一人者が書いた一般向けの本。内容はもちろんのこと、書きっぷりもいい。
インターネットに携わる人は必読かと。

複雑ネットワークの科学

上の本では物足りなかった本質的な内容が、数式も交えてしっかり解説してある。
べき分布の仕組みも、これでわかる。

ヒントは「ネットワーク」にあります。
べき分布が形成される様子を、とりあえず Flash にて再現してみました。まずはご覧あれ。
>> http://brownian.motion.ne.jp/memo/ScaleFreeNet.html

このFlashでは、左側の画面に２００個の点をランダムに打っています。
この２００個の点が、インターネット上のサイトだと思ってください。
右側の画面には、横軸にリンク数、縦軸にそのリンク数を持つサイトの数がグラフ表示されます。
要はリンク数のヒストグラムです。
画面には２つのボタン「ランダム」と「リンク数に比例」が付いています。
まずは「ランダム」を押してみましょう。
サイト同士が、全くランダムにリンクされてゆきます。（ここでは確率５％としています）
リンクが増えてゆくにつれて、ヒストグラムの形は平均を中心とした山型のカーブになると思います。
この山型のカーブは、いわゆる正規分布というやつです。 ポアソン分布という形になっています。
つまり、各サイトのリンク数は「平均値プラスマイナス誤差」というに近い形になっているわけです。

以上を確認したところで、もう１度「ランダム実行」ボタンを押すと実行が止まります。
（あるいは最大値の２００で止まります）

次に「リンク数に比例」ボタンを押してみましょう。
今度もリンクが増えていって、ヒストグラが描かれるのですが、、、さっきと形が違っていますね。
今度の場合、大多数のサイトはのリンク数は最低数（２に設定している）なのに、
ごく一部の上位サイトだけが抜きんでて多数のリンクを獲得しています。
実は、このヒストグラムの形がベキ分布となっているのです。

何をしたのか。
今度の場合、リンクをランダムに張ったのではなくて、
「それまでサイトが持っていたリンク数に比例する確率で」張っていたのです。
インターネット上でリンクを張ろうと思ったとき、でたらめに張るより、
なるべくなら既にリンクがたくさん張られている人気サイトに張ろうと思いますよね。
たとえば、既にリンクを１０本持っているサイトと、２０本持っているサイトがあるとしたら、
２０本持っているサイトの方が、１０本のサイトの２倍の確率で新規リンクを獲得する、
そのようにしてあります。
人気のあるサイトが、ますます人気を獲得してゆく、、、
その結果が、上位人気独占という形になって表れているわけです。
>> wikipedia:複雑ネットワーク “バラバシ＝アルバートモデル”を参照。

まとめると、
・ランダム 　　　=> 正規分布 ポアソン分布
・リンク数に比例 => べき分布
ということです。
言われてみると結果はシンプルなのですが、
試しにやってみないことには、なかなか気付かないですよ、これ。
ベキ乗法則はインターネットを始め、いろいろなところに見出されますが、
その全てが必ずしも「リンク数に比例」モデルで説明し尽くせるわけではないと思います。
例えばインターネット１つ取っても、そこにはリンク数の他にもいろいろな要因が絡んでいるでしょう。
そういった点では、この「リンク数に比例」は最も単純なモデルであり、
ここからさらに様々な発展型モデルが考えられるわけです。

ベキ乗法則は、シンプルにして強力なツールだと改めて実感しました。
サイトのアクセス数を調べるにしても、インフルエンザの感染を調べるにしても、
こういった「ネットワーク思考」は欠かせないでしょう。