python - Networkx 的有效学位序列是什么

Question

我正在尝试生成具有最小度值(rho)的幂律度分布，并使用它通过 networkx 包构建随机图。我用来生成幂律度分布的函数如下(指数是 alpha，rho 是最小值):

import random
import networkx as nx

def generate_pl_dd(no_of_nodes, alpha, rho):
  degree_distribution = []
  for i in range(no_of_nodes):
    r = random.random()

    degree_distribution.append(int(rho * (1 - r)**(-1/(alpha - 1))))

  return sorted(degree_distribution, reverse=True)

现在我希望使用此函数生成的度数列表来构建 networkx 图形对象。在我这样做之前，像这样的健全性检查会返回以下结果。

dd1 = generate_pl_dd(100, 2.2, 50)
nx.is_valid_degree_sequence(dd1) # returns False

文档提到度数序列的总和必须是偶数，但即使我生成偶数求和的度数序列，结果也是 False。我在下面捕获了该函数的一些运行。

dd2 = generate_pl_dd(100, 2.2, 50)
sum(dd2) # returns 15710
nx.is_valid_degree_sequence(dd2) # returns False

dd3 = generate_pl_dd(100, 2.2, 10)
sum(dd3) # returns 4540
nx.is_valid_degree_sequence(dd3) # returns False

dd4 = generat_pl_dd(100, 2.2, 1)
sum(dd4) # returns 344
nx.is_valid_degree_sequence(dd4) # returns True

最后一次运行如何返回True？我在这里缺少什么细节？

Answer 1

经is_valid_ Degree_sequence测试的有效度序列是简单图(简单图没有自环且没有重复边)可能具有的序列。因此，例如，你不能拥有一个只有两个节点的图，两个节点的度数均为 3。这个例子显然是不可能的，但一般来说，序列“图形化”的具体条件是更复杂的计算，通常通过Havel-Hakimi algorithm .

当您说“文档提到度数序列的总和必须为偶数”时，我相信您指的是 documentation对于configuration_model，它实际上生成多重图(允许自循环和多条边)。这样做的唯一限制是输入度数的总和应该是偶数(并且作为技术细节，自循环在生成过程中对度数计数两次，尽管在其他情况下它们可能只计数一次)。

(就其值(value)而言 --- configuration_model 用于测试度数序列是否为“图形化”，但是 not anymore 。我对此承担一些责任。)