Implementation of the Barabashi-Albert method for creating networks without scaling

Question

I am trying to implement a very simple preferential binding algorithm for creating networks without scale. They have power distributions that follow a power law, that is, P (k) ~ k ^ -g, where g is an exponent. The algorithm below should provide a degree distribution with an indicator equal to 3 +/- 0.1, my implementation does not show indicators closer to 2.5 +/- 0.1. I clearly don’t understand something somewhere and continue to make mistakes.

Sorry if this is in the wrong place, I could not decide if it should be in stackoverflow or 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 

My implementation in 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 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); } } 

Here is an example of a degree distribution i for N = 10000 and 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, so I couldn’t figure out how to execute this particular algorithm correctly, instead I used another one.

 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, ie 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 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. 

Where k (j) is the degree of node j in graph G, and k_tot is twice as many edges (total number of degrees) in graph G.

By changing the parameter a, one can control the exponent of the degree distribution. a = 1.22 gives me the exponent g (in P (k) ~ k ^ -g) 3 +/- 0.1.