Barabási–Albert模型在Python中

Question

我正在尝试使用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是每个新节点的链接数。

Answer 1

在使用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.

Answer 2

主要问题是随机生成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²）。