C++ による数値シミュレーション入門 (4/4)｜実装例
東工大情報理工学院 高安研究室 で開催されている新入生向けのプログラミングゼミの資料を一部公開します．
本稿は C++ による数値シミュレーション入門 の第 4 部です．
ここでは，次の2つのモデルの実装を行ないます．
- Barabashi-Albert モデル
- （課題）ディーラーモデル
Barabashi-Albert モデル
現実のネットワークの生成モデルである Barabashi-Albert モデル（以下，BA モデル）を簡単に紹介した後，その実装例を step by step で紹介します．
[5] Barabási, Albert-László, and Réka Albert. "Emergence of scaling in random networks." science 286.5439 (1999): 509-512. https://www.science.org/doi/10.1126/science.286.5439.509
現実のネットワークのスケールフリー性
ネットワークはノードとノードがリンクによって結ばれてできています．例えば，正方格子は全てのノードが一様に，同じ数のノードとリンクで繋がれています．しかし，現実のネットワーク（例えば，SNS のフォロー関係のネットワークやタンパク質の相互作用のネットワーク）にはそのような均質性はなく，1つのノードが大部分のリンクを占有しています．このような不均質なつながりはスケールフリー性と呼ばれ，ネットワークの複雑さを高めています．スケールフリー性をより正確に表すと，それぞれのノードのリンクでつながったノードの個数を
BA モデル
BA モデルは，スケールフリー性をもつネットワークが生成される過程を記述した，1番最初のモデルです．スケールフリー性は，富めるものがさらに豊かになる性質である，Preferential Attachment (優先的接続) をネットワークの成長過程に導入しました．Twitter を例に挙げれば，フォロワー数の多い人ほど（有名人ほど）フォローされやすいという性質です．具体的には次の通りです．
-
N_0 -
N - ノードは
m - それぞれのリンクの接続先を，ネットワーク上にあるノードから次の確率で決める．
\Pi_i = \frac{k_i}{\sum_j k_j} \propto k_i
- ノードは
- 十分大きな
N N_0 P(>k) \sim k^{-2}
このモデルによって生成されるネットワークが
それでは，BA モデルを実装していきます．考えるべき点は以下です．
- ネットワークのデータ構造
-
N_0 - Preferential Attachment の実装
- （任意）ノード追加時に，自己ループができないようにリンクの接続先を選ぶ
- （任意）ノード追加時に，多重リンクができないようにリンクの接続先を選ぶ
- 生成したネットワークをファイルに出力する
ネットワークのデータ構造
ネットワークの構成要素であるノードは，ノード数が
// 例: 0-1-2
links = [(0,1),(1,2),(2,3)]
のような組の配列で記述できそうです．リンクに向きがない場合は，一方向のみを含める場合と，両方向を一回ずつ含める場合がありますが，ここでは前者を採用することにします．このとき，数字の小さいノードを先に書くなどのルールを決めておくと良いでしょう．
また，偶数番目とその次を1組のリンクだと思うと，() を取り払って
// 例: 0-1-2
links = [0,1,1,2,2,3]
のようにデータ構造を定義できそうです．
// 例: 0-1-2
std::vector<int> links = {0,1,1,2,2,3};
リンクを追加していく必要があるので，可変長配列 std::vector を使っています．
初期ネットワークの生成
(0,1),(0,2),(0,3),
(1,2),(1,3),
(2,3)
の合計6本のリンクが作られます．これは二重 for 文を使って簡単に書けそうです．
// Assume undirected graph
// Node labels: 0,...,N-1
std::vector<int> generate_complete_graph(int N)
{
std::vector<int> links;
for (int i = 0; i < N; ++i)
{
for (int j = i + 1; j < N; ++j)
{
links.push_back(i);
links.push_back(j);
}
}
return links;
}
links に (i,j) リンクを追加することは，この後も何度も出てきそうですので，次のように関数化してしまっても良いでしょう．
void add_link(std::vector<int> &links, int i, int j)
{
// add i -> j link (i < j)
links.push_back(i);
links.push_back(j);
}
関数には links を参照渡しする必要があります．& を付けず値渡ししてしまうと，コピーされた links に対して(i,j) リンクが追加されてしまいます．
Preferential Attachement
ノードを追加する際，リンクの先をネットワーク上のノードから次数に比例する確率
で選ぶことをそのままプログラムで再現しようとすると，次数の配列を用意して，離散分布を利用する
std::vector<int> degrees = {k0, k1, ...};
std::discrete_distribution<int> discrete(degrees);
int target = discrete(gen); // gen は乱数生成器
といった発想になるかと思います．ノードを追加する度に degrees をするのが面倒ですが，いちおう実装はできそうです．ただ，もっと簡単な方法があります．
実は，links から一様ランダムに要素を取り出すだけで preferential attachment を実装できます．links にはノード links.size() に一致します．つまり，links からランダムに要素を選んだ時に，ノード
に一致します．このことを利用すると，preferential attachment による接続先の選択は次のように書けます．
std::uniform_int_distribution<int> uni(0, links.size()-1);
int target = links[uni(gen)]; // gen は乱数生成器
ファイル出力
BA モデルによって生成されたネットワーク（リンクの集合）をファイルに出力します．ファイル出力には fstream ライブラリの std::ofstream を使います．下記のように関数化しておくと main 関数の見通しが良くなります．
void output_links(std::vector<int> &links, std::string path = "")
{
if (path == "")
{
for (int i = 0; i < links.size() / 2; ++i)
std::cout << links[2 * i] << "," << links[2 * i + 1] << std::endl;
return;
}
std::ofstream ofs(path);
for (int i = 0; i < links.size() / 2; ++i)
ofs << links[2 * i] << "," << links[2 * i + 1] << std::endl;
}
プログラムの全体像
以上をまとめると，BA モデルは下記プログラムのように実装できます．
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <random>
void add_link(std::vector<int> &links, int i, int j)
{
// add i -> j link (i < j)
links.push_back(i);
links.push_back(j);
}
// Assume undirected graph
// Node labels: 0,...,N-1
std::vector<int> generate_complete_graph(int N)
{
std::vector<int> links;
for (int i = 0; i < N; ++i)
{
for (int j = i + 1; j < N; ++j)
{
add_link(links, i, j);
}
}
return links;
}
// Determine if a vector contains specified target
bool contains(std::vector<int> &vec, int target)
{
for (auto element : vec)
{
if (element == target)
return true;
}
return false;
}
// BA model: generate a network (list of links)
std::vector<int> BA(std::mt19937 &gen, int N, int N0, int m)
{
// Initialize a graph
std::vector<int> links = generate_complete_graph(N0);
// For N-N0 steps, add a node with m links
// Labels of new nodoes: N0,...,N-1
// Choose targets of m links by preferential attachment
std::uniform_real_distribution<double> uni(0.0, 1.0);
for (int new_node = N0; new_node < N; ++new_node)
{
// Select targets to connect m links
// by preferential attachment
std::vector<int> targets;
int L = links.size();
while (targets.size() < m)
{
int index = int(uni(gen) * L);
int new_target = links[index];
// Avoid multi-links
if (contains(targets, new_target))
continue;
targets.push_back(new_target);
}
// add m links to the network
for (auto target: targets)
{
add_link(links, target, new_node);
}
}
return links;
}
// output links as csv
void output_links(std::vector<int> &links, std::string path = "")
{
if (path == "")
{
for (int i = 0; i < links.size() / 2; ++i)
std::cout << links[2 * i] << "," << links[2 * i + 1] << std::endl;
return;
}
std::ofstream ofs(path);
for (int i = 0; i < links.size() / 2; ++i)
ofs << links[2 * i] << "," << links[2 * i + 1] << std::endl;
}
int main(int argc, char *argv[])
{
if (argc < 2)
{
std::cout << "Required an output directory." << std::endl;
std::cout << "[Usage] <bin> <out_dir>" << std::endl;
return 0;
}
// 乱数列の出力ファイル
// std::string out_dir = "../result/";
std::string out_dir = argv[1];
std::string out_file = out_dir + "ba.csv";
int seed = 1;
std::mt19937 gen(seed);
int N = 1e6;
int N0 = 5;
int m = 3; // 新規参入するノードのリンク数
std::vector<int> links = BA(gen, N, N0, m);
output_links(links, out_file);
return 0;
}
課題 4（ディーラーモデルの実装）
ディーラーモデルを実装してください．
[1] Yamada, Kenta, Hideki Takayasu, Takatoshi Ito, and Misako Takayasu. 2009. “Solvable Stochastic Dealer Models for Financial Markets.” Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics 79 (5 Pt 1): 051120. http://dx.doi.org/10.1103/PhysRevE.79.051120
Discussion