实现Barabasi-Albert方法建立无标度网络
实现Barabasi-Albert方法建立无标度网络
提问于 2012-05-17 00:07:31
我正在尝试实现一个非常简单的优先连接算法来创建无尺度网络。它们的度分布遵循幂律，即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);
}
}下面是我得到的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回答 1
Stack Overflow用户
发布于 2012-05-17 20:06:34
好吧，所以我不知道如何让这个特殊的算法正确工作，所以我使用了另一个算法。
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)是图G中节点j的度，k_tot是图G中边数(度的总数)的两倍。
通过改变参数，可以控制度分布的指数。A= 1.22给出了指数g(在P(k) ~k^-g中)为3 +/- 0.1。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/10622401
复制相关文章
相似问题
腾讯云开发者
