Networkx的有效学位序列是什么

Question

我试图用最小度值（rho）生成幂律度分布，并用它来构建networkx包中的随机图。我用来生成幂律度分布的函数如下（指数为α，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图形对象。在我这样做之前，像这样的健全性检查返回以下结果。在

^{pr2}$

文档中提到度序列的和需要是偶数的，但是即使我生成了一个偶数和的度序列，结果也是错误的。我在下面捕获了这个函数的一些运行。在

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度。这个例子显然是imposile，但是一般来说，一个序列成为“图形化”的具体条件是一个更复杂的计算，通常通过Havel-Hakimi algorithm完成。在

当你说“文档提到度序列的和需要是偶数”时，我相信你指的是documentationfor configuration_model，它实际上生成了多图（允许自循环和多条边）。它这样做的唯一限制是输入度数的总和应该是偶数（作为一个技术细节，在生成过程中，self循环对度数计数两次，尽管在其他上下文中，它们可能只计算一次）。在

（值得一提的是-configuration_model用来测试度序列是“图形化的”，但是not anymore。我声称对此负有一定责任。）