このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

はじめに

 ワッツとストロガッツは、現実のネットワークがスモールワールド性(小さい距離、高いクラスター性)であることに注目した。しかし、彼らは1998年当初、ネットワークの次数分布についてはあまり考えていなかったという。  一方、バラバシとアルバートは、インターネットのデータ解析によって、多くのネットワークの次数分布がべき則(1/kγ)になることを知っていた。さらに、ワッツとストロガッツから提供してもらったデータを調べてみると、これらの次数分布もべき則になっていることを発見した。

スケールフリー性

  • ネットワークの次数分布がべき則となる性質をスケールフリー性という。
  • 特徴的なスケール(縮尺)がない(フリー)という意味で名づけられた。
    • ここでいう特徴的なスケールとは、釣り鐘型分布のときの平均値や分散のようなものである。平均値と分散がわかれば、平均からどれくらい離れていて、全体で何番目くらいかがわかる。
      • 縮尺がないスケールフリー分布では、そういったことは簡単に測定できない。
  • スモールワールド性(小さい平均距離と高いクラスター性の組み合わせ)は、ほとんどの実世界のネットワークが持っている。
    • しかし、スケールフリー性を持つネットワークは実世界にたくさん存在する。

スケールフリーネットワークの構成

BAモデル

  • BAモデルは成長するので、新しい頂点が1つずつネットワークに加入する。
    • 頂点は、ネットワークに入ってくるときに新しい枝を何本か持ってくる。各枝の行き先はランダムに決められるが、優先的選択というルールを適用する。これにより、先に存在する頂点の中で、次数の大きいものが優先的に新しい枝を受け取りやすい。

一般化ランダムグラフ

コンフィグレーションモデル

ハブの存在性

スケールフリーネットワークにはハブが存在することが多い。

インターネット

  • ランダムな攻撃で、スケールフリーネットワークをばらばらにするほどハブがやられるには、かなりの割合の頂点を壊さなければならない。
    • つまり、ランダムな攻撃に対しては頑強といえる。
  • ハブを集中攻撃されてしまうと、スケールフリーネットワークは早い段階でばらばらにやりやすい。
    • つまり、ハブを狙った攻撃に対しては頑強でない。

以上より、重点的にハブのセキュリティを上げることは非常に有効である。

感染症モデル

スケールフリーネットワークでは、ハブが多くて次数分布が不均等なほどパーコレーションの臨界確率pcが小さくなる。極端な場合では0になる。 pcが小さいほど病気は広がりやすい。 もしpc=0であれば、どんなに感染確率p(>0)が小さくても、病気が全体に広がることになってしまう。

以上はパーコレーションについての結果だが、SIRモデル、SISモデル、ほかの感染症モデルでも同様の事実が成り立つことが知られている。

予防接種はハブを優先した方がネットワークにおける感染拡大を抑えることができる*1


*1 倫理的には人権平等で、次数の大きいハブも小さい頂点も、等しい確率で予防接種の権利が与えられるべきかもしれないが。