實現用於創建無標度網絡的Barabasi-Albert方法

Question

我試圖實現用於創建無標度網絡的非常簡單的優先附件算法。它們具有遵循冪律的度分佈，即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); 
    } 
} 

這裏的一個度分佈I獲得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 

Answer 1

好了，所以我無法弄清楚如何使這個特定的算法正常工作，而不是我用另一個。

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. 

其中k（j）是節點j的圖中的G和k_tot度是邊在圖G

數（度總數）兩次通過改變參數一個人可以控制程度分佈的指數。 a = 1.22給出了指數g（在P（k）〜k^-g）爲3 +/- 0.1。