python - Python 中的 Barabási-Albert 模型

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

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