我正在尝试使用Barabási–Albert model生成合成网络。我不希望使用任何“固定”库函数,因为稍后我打算修改所涉及的数学表达式。
吸引的概率是:Π(ki)= ki / ∑j kj。以下代码似乎在m = 1时有效:
if random.uniform(0.0, 1.0) <= p and t not in neighbours_per_node[i]:
currentDegree[t] += 1
currentDegree[i] += 1
我的问题是将上面的代码推广用于更大的m值,其中m是每个新节点的链接数。
在使用if t not in neighbors_per_node[i]:
条件之前,请使用if t in neighbors_per_node[i]:
,重新使用random.uniform(0.0,1.0)
并绘制一个新的概率直到t not in neighbors_per_node[i]
。
如果有帮助,我在C ++中的代码是:
for(int i = 0; i < m; i++) { // m connections
ini:
prob_sorteio = (double) rand() / RAND_MAX;
// ... code
if(t already has the connection) { goto ini; }
}
// goto ini: return to calculate a new probability.
主要问题是随机生成m
个节点的子集,其中每个节点都有希望的(非均匀)被选择概率。
一种好方法是将权重列表映射到samples from exponential distributions列表,然后选择m
最低数字。可以使用random.expovariate功能来完成。根据需要,将选择权重为w_1
的节点,而不是概率为w_2
的权重为w_1 / (w_1 + w_2)
的节点。
此解决方案被称为“ Algorithm A-Res”,这是由于Efraimidis and Spirakis。
import random
def random_subset_with_weights(weights, m):
mapped_weights = [
(random.expovariate(w), i)
for i, w in enumerate(weights)
]
return { i for _, i in sorted(mapped_weights)[:m] }
def barabasi_albert(n, m):
# initialise with a complete graph on m vertices
neighbours = [ set(range(m)) - {i} for i in range(m) ]
degrees = [ m-1 for i in range(m) ]
for i in range(m, n):
n_neighbours = random_subset_with_weights(degrees, m)
# add node with back-edges
neighbours.append(n_neighbours)
degrees.append(m)
# add forward-edges
for j in n_neighbours:
neighbours[j].add(i)
degrees[j] += 1
return neighbours
示例:
>>> from pprint import pprint
>>> pprint(barabasi_albert(30, 3))
[{1, 2, 3, 4, 5, 7, 8, 17},
{0, 2, 3, 5, 8, 12, 15, 16, 17, 23},
{0, 1, 3, 4, 6, 9, 11, 13, 14, 16, 17, 18, 19, 20, 22, 24, 26, 27},
{0, 1, 2, 4, 6, 7, 10, 20, 22, 23, 24, 25, 27},
{0, 2, 3, 5, 6, 8, 10, 11, 13, 21},
{0, 1, 4, 7, 9, 19, 29},
{10, 18, 2, 3, 4},
{0, 3, 5, 15, 23, 29},
{0, 1, 4, 9, 11, 13, 21, 28},
{8, 2, 26, 5},
{21, 3, 4, 12, 6},
{2, 4, 8, 12, 14, 15, 18, 25},
{1, 10, 11, 14},
{8, 16, 2, 4, 20},
{2, 11, 12},
{19, 1, 11, 7},
{24, 1, 2, 13},
{0, 1, 2},
{2, 11, 6},
{2, 5, 15},
{29, 2, 3, 13, 22},
{8, 10, 26, 4},
{27, 2, 3, 20},
{1, 3, 25, 7},
{16, 2, 3},
{3, 11, 23},
{9, 2, 28, 21},
{2, 3, 28, 22},
{8, 26, 27},
{20, 5, 7}]
[通过更改用于计算权重的公式来调整算法,只需使用您自己的公式来计算权重列表,然后使用它代替degrees
。
集合理解值{ i for _, i in sorted(mapped_weights)[:m] }
返回m
中最低数字mapped_weights
的一组索引。对列表进行排序需要O(n log n)时间;因此,在n
顶点上生成图的总体复杂度为O(n²log n)。
如果要生成大图,则使用quickselect算法选择m
最低数字会更有效;在这种情况下,整体复杂度将为O(n²)。