📂グラフ理論

スケールフリーネットワーク

定義 ¹

次数分布がパレート分布に従うランダムネットワークをスケールフリーネットワーク^{scale-free Network}という。

説明

スケールフリー(SF)ネットワークという名前は、パレート分布が持つスケールフリー性から来ている。次数分布で定義されるネットワークであるため、その分布の性質を強く受け継いでいるのが特徴だ。数式で表すと、スケールフリーネットワーク$G$のノード$v \in V(G)$の次数はあるパラメータ$\gamma > 0$に対して次のように表すことができる。 $$ P \left( \deg v = k \right) \sim k^{-\gamma} $$ SFネットワークはパレート分布のように科学界全般で頻繁に現れ、社会や自然現象を説明するにはとても良いモデルとして知られている。しかし、最近ではこのSFネットワーク万能論への警鐘を鳴らす論文²も発表されたので注意が必要だ。

その代表的な応用は特定のダイナミクスの基盤構造を模倣することだ。数多くの実際のデータから導かれるので、人間関係、交通網、生態系など数学的に普遍的な構造が必要な場合に最初に考慮され、実際に広く使われている。SFネットワークを人工的に生成する方法としては、次のモデルが知られている。

• チョン・ル適合度モデル
• バラバシ・アルバートモデル

次はバラバシ・アルバートモデルで生成されるSFネットワークの視覚化だ。

式で、次数分布のヒストグラムはログログ図を描いたときに直線を形成すべきだ。つまり、 $$ p(x) \sim x^{-\gamma} $$ の両辺にログをとったとき $$ \log p (x) = - \gamma \log x $$ なので、傾きが$- \gamma$の直線になる。実際に描いてみると、ハブノードが出現する領域を除いて、はっきりした直線を形成しているのが確認できる。