複雑ネットワーク
バラバーシ・アルベルト・モデル(バラバシ・アルバートモデル)では、既存の次数の大きな頂点に対して新しい辺が高い確率で加わってゆき、その頂点がハブへと成長してゆく(右の図では一番上にある頂点がハブに相当する)。このモデルでは頂点の次数分布は p(k) = 2m(m+1) / [k(k+1)(k+2)] ∝ k となり γ = -3 のスケールフリー性を満たす。モデルはランダムグラフと似たところもあるので、平均最短距離は L ∝ log n となりスモールワールド性をも満たす。
バラバーシ・アルベルト・モデル(バラバシ・アルバートモデル)の弱点は、クラスター係数が0に近い小さな値となり、クラスター性を満たさないことである。だがその後、これらの研究をさらに発展させる形で、単純なアルゴリズムでありながら「スケールフリー性」「スモールワールド性」「クラスター性」という現実世界のネットワークの3つの特徴全てを満たすようなモデルが発表されている。
現実世界のネットワークが持つ第1の性質は「スケールフリー性」(次数分布のべき乗則)である。これは、一部の頂点が他のたくさんの頂点と辺で繋がっており、大きな次数を持っている一方で、その他の大部分はわずかな頂点としか繋がっておらず、次数は小さいという性質である。次数の大きな頂点は「ハブ」とも呼ばれる。
スケールフリー性は、社会学をはじめとするこれまでの研究により、現実世界のネットワークで幅広く観察されている。例えば、人々の持っている知人関係の数をみると、一部の人は非常にたくさんの知人を持っているが、大多数の人々の知人の数は限られている。WWWではごく少数の有名サイトが数百万単位のリンクを集めているが、大多数のサイトはわずかなリンク先からしかリンクされていない。生体内の相互作用でも、ごく一部のたんぱく質が多数のたんぱく質と反応する構造になっている。男女の性的関係でも、ごく一部の人は何百人という相手と関係するが、大多数の人々は限られた相手としか関係を持たない。
数学的には、スケールフリー性は頂点が次数 k を持つ確率 p(k) の確率分布が p(k) ∝ k のべき乗則になると表現される。