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

neural network python

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 poder, 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í hay un ejemplo de distribución de grados que obtengo para 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

De acuerdo, entonces 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 el doble del número de aristas (el número total de grados) en el gráfico G.

Al modificar 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.