Barabási–Python中的阿尔伯特模型

我正在尝试使用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 ini:
prob_sorteio = (double) rand() / RAND_MAX;
// ... code
if(t already has the connection) { goto ini; }
}
// goto ini: return to calculate a new probability.

,

主要问题是随机生成QueryBuilder query = QueryBuilders.boolQuery()
.filter(QueryBuilders.termQuery("REQ_ID.keyword","1574778361496"))
.filter(QueryBuilders.termQuery("CATEGORY.keyword","WARNING"));
个节点的子集，其中每个节点都有希望的（非均匀）被选择概率。

一种整洁的方法是将权重列表映射到samples from exponential distributions列表，然后选择m最低的数字。可以使用random.expovariate函数来完成。根据需要，将选择权重为m的节点，而不是权重为w_1的权重为w_2的节点。

此解决方案被称为“ Algorithm A-Res”，这归因于Efraimidis and Spirakis。

w_1 / (w_1 + w_2)

示例：

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,12,15,16,17,23},1,6,9,11,13,14,18,19,20,22,24,26,27},10,23,25,21},29},{10,4},21,28},{8,5},{21,6},{2,25},{1,14},20},12},{19,7},{24,13},2},15},{29,22},{27,{16,3},{3,{9,28,{20,7}]
。

集合理解degrees返回{ i for _,i in sorted(mapped_weights)[:m] }中最低数字m的一组索引。对列表进行排序需要O（n log n）时间；因此，在mapped_weights顶点上生成图的整体复杂度为O（n²log n）。

如果要生成大图，则使用优先级队列或quickselect算法来选择n最低数字会更有效；在这种情况下，整体复杂度将为O（n²）。