Implementacja metody Barabasi-Albert do tworzenia sieci bezskalowych

Question

Próbuję zaimplementować bardzo prosty algorytm przywiązania preferencyjnego do tworzenia sieci bezskalowych. Mają one rozkłady stopni, które są zgodne z prawem mocy, tj. P (k) ~ k^-g, gdzie g jest wykładnikiem. Poniższy algorytm powinien dawać rozkłady stopni z wykładnikiem równym 3 +/- 0,1, moja implementacja nie wykładników jest bliższa 2,5 +/- 0,1. Najwyraźniej nie rozumiem gdzieś czegoś i nadal się mylę.

Przepraszam, czy to jest w niewłaściwym miejscu, nie mogłem się zdecydować, czy powinien on być w stackoverflow lub 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 

Moja Implementacja w 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); 
    } 
} 

Oto przykład z rozkładu stopni ja trafiam dla N = 10000 i 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 

Answer 1

Ok, więc ja nie mogłem wymyślić, jak sprawić, aby ten konkretny algorytm działał poprawnie, zamiast tego użyłem innego.

The Algorithm: 
Input: Number of Nodes N; 
     Initial number of nodes m0; 
     Offset Exponent a; 
     Minimum degree 1 <= d <= m0. 
Output: scale-free multigraph G = ({0,....,N-1}, E). 

1) Add m0 nodes to G. 
2) Connect every node in G to every other node in G, i.e. create a complete graph. 
3) Create a new node i. 
4) Pick a node j uniformly at random from the graph G. Set P = (k(j)/k_tot)^a. 
5) Pick a real number R uniformly at random between 0 and 1. 
6) If P > R then add j to i's adjacency list. 
7) Repeat steps 4 - 6 until i has m nodes in its adjacency list. 
8) Add i to the adjacency list of each node in its adjacency list. 
9) Add i to to the graph. 
10) Repeat steps 3 - 9 until there are N nodes in the graph. 

gdzie k (j) jest stopień węzła j na wykresie G i k_tot jest dwukrotnie większa od liczby krawędzi (całkowitą liczbę stopni) na wykresie G.

Poprzez zmianę parametru można kontrolować wykładnik rozkładu stopni. a = 1,22 daje mi wykładnik g (w P (k) ~ k^-g) 3 +/- 0,1.