Реализация метода Барабаси-Альберта для создания безмасштабных сетей

Я пытаюсь реализовать очень простой алгоритм предпочтительного присоединения для создания безмасштабных сетей. . Они имеют распределения степеней, которые следуют степенному закону, т. Е. P (k) ~ k ^ -g, где g - показатель степени. Приведенный ниже алгоритм должен создавать распределения степеней с показателем степени, равным 3 +/- 0,1, в моей реализации показатели не ближе к 2,5 +/- 0,1. Я явно чего-то не понимаю и продолжаю ошибаться.

Извините, если это не то место, я не мог решить, должно ли это быть в stackoverflow или maths.stackexchange.com.

The Algorithm:
Input: Number of Nodes N; Minimum degree d >= 1.
Output: scale-free multigraph
G = ({0,....,N-1}, E)
M: array of length 2Nd
for (v=0,...,n-1)
   for (i=0,...,d-1)
      M[2(vd+i)] = v;
      r = random number selected uniformly at random from {0,.....,2(vd+i)};
      M[2(vd+i)+1] = M[r];
   end
end

E = {};
for (i=0,...,nd-1)
   E[i] = {M[2i], M[2i+1]}
end

Моя реализация на C/C++:

void SF_LCD(std::vector< std::vector<int> >& graph, int N, int d) {
    if(d < 1 || d > N - 1) {
        std::cerr << "Error: SF_LCD: k_min is out of bounds: " << d;
    }

    std::vector<int> M;
    M.resize(2 * N * d);

    int r = -1;
    //Use Batagelj's implementation of the LCD model
    for(int v = 0; v < N; v++) {
        for(int i = 0; i < d; i++) {
            M[2 * (v * d + i)] = v;
             r = mtr.randInt(2 * (v * d + i));
            M[2 * (v * d + i) + 1] = M[r];
        }
    }

    //create the adjacency list
    graph.resize(N);
    bool exists = false;
    for(int v = 0; v < M.size(); v += 2) {
        int m = M[v];
        int n = M[v + 1];

        graph[m].push_back(n);
        graph[n].push_back(m);
    }
}

Вот пример распределения степеней, которое я получаю для N = 10 000 и d = 1:

1   6674
2   1657
3   623
4   350
5   199
6   131
7   79
8   53
9   57
10  27
11  17
12  20
13  15
14  12
15  5
16  8
17  5
18  10
19  7
20  6
21  5
22  6
23  4
25  4
26  2
27  1
28  6
30  2
31  1
33  1
36  2
37  2
43  1
47  1
56  1
60  1
63  1
64  1
67  1
70  1
273 1
6
задан Gauntlet 16 May 2012 в 16:07
поделиться