C/C++で実装するBarabási-Albertグラフ（スケールフリーモデル向け）とは？

バラバーシ・アルバート（BA）モデルとは

バラバーシ・アルバート（BA）モデルは、スケールフリーネットワークを生成するために提案された複数のモデルの一つとして扱われています。このモデルは、「成長（growth）」と「選択的接着（preferential attachment）」という2つの重要な概念を組み合わせたものです。どちらの概念も、現実のネットワークに広く見られる性質です。

成長（Growth）

「成長」とは、ネットワーク内のノード数が時間の経過とともに増加していくことを意味します。

選択的接着（Preferential Attachment）

「選択的接着」とは、すでに多くの接続を持つノードほど、新しいリンクを受け取る確率が高くなるという仕組みです。次数の高いノードほど、ネットワークに追加されるリンクをつかみ取る能力が強いといえます。

選択的接着は、人と人とをつなぐソーシャルネットワークをイメージすると直感的に理解しやすくなります。ここで、XからYへのリンクは「人物Xが人物Yを知っている（面識がある）」ことを表します。リンクを多く持つノードは、人脈の広い著名人に相当します。新たにコミュニティへ参加してきた人は、無名の人よりも、そうした存在感のある人物と知り合いになる可能性のほうが高いでしょう。

BAモデルは、World Wide Web（WWW）においても同様の現象を前提として提案されました。つまり、新しいページは、ほとんど誰も知らないページではなく、YahooやGoogleといった非常に有名なサイト（ハブ）へ優先的にリンクを張るという仮定です。もし誰かが既存のリンクをランダムに選んでリンク先を決めるとすれば、特定のページが選ばれる確率は、そのページの次数（被リンク数）に比例します。

BAモデルのグラフ例（50ノード）

次の画像は、選択的接着モデルに従って生成された、50ノードからなるBAモデルのグラフを示しています。

上記のグラフは、「富める者はさらに富み、貧しき者はさらに貧しくなる」といういわゆる「マタイ効果（rich-get-richer）」の論理を見事に体現しています。