Implementación del método Barabasi-Albert para crear redes sin escala

Question

Estoy tratando de implementar un algoritmo de conexión preferencial muy simple para crear redes sin escala. Estos tienen distribuciones de grados que siguen una ley de potencia, es decir, P (k) ~ k^-g, donde g es el exponente. El algoritmo siguiente debe producir distribuciones de grados con el exponente igual a 3 +/- 0.1, mi implementación no hace que los exponentes estén más cerca de 2.5 +/- 0.1. Claramente no estoy entendiendo algo en alguna parte y continúo haciéndolo mal.

Lo siento si esto está en el lugar equivocado, no pude decidir si debería estar en stackoverflow o 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 

mi implementación en 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); 
    } 
} 

Aquí está un ejemplo de una distribución de grado que consigo por N = 10,000 y 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

bien, así que No pude entender cómo hacer que este algoritmo en particular funcione correctamente, en su lugar usé otro.

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. 

Donde k (j) es el grado de nodo j en el gráfico G y k_tot es dos veces el número de bordes (el número total de grados) en el gráfico G.

Al alterar el parámetro uno puede controlar el exponente de la distribución de grados. a = 1.22 me da un exponente g (en P (k) ~ k^-g) de 3 +/- 0.1.