配置模型

配置模型（configuration model）通过均匀配对半边，构造具有指定度序列的随机无向多重图。每个顶点先拥有与目标度数相同数量的带标签半边，每对半边连成一条边；同一顶点的两半边配对产生自环，不同顶点之间多次配对产生平行边。自环对度数贡献二。

只有两个顶点 $a,b$，目标度数均为二时，四条半边记为 $a_1,a_2,b_1,b_2$。共有三种无序配对：$a_1{a}_2|b_1{b}_2$ 产生两个自环；$a_1{b}_1|a_2{b}_2$ 与 $a_1{b}_2|a_2{b}_1$ 都产生两条平行的 $ab$ 边。三种半边配对等概率，两个无标签结果的概率却分别为三分之一和三分之二。

模型均匀抽样的是半边配对，不是每一种最终无标签多重图。

均匀配对与精确期望

给定非负整数度数 $d_1,\dots ,d_n$，令 $L=\sum _i{d}_i=2m$ 为偶数。$L>0$ 时，带标签半边的完全配对数为 $$(L-1)!!=(L-1)(L-3)\cdots 1.$$ 证明是固定第一条半边，其伙伴有 $L-1$ 种，余下再固定一条，有 $L-3$ 种，依此递归。空半边集有一种空配对。奇数总和不能完全配对；偶数总和则不要求该度序列能由简单图实现。

对任一指定半边，其他 $L-1$ 条半边作为伙伴的地位对称，所以与某一指定半边配对的概率为 $1/(L-1)$。对不同顶点 $i,j$，潜在跨点半边对有 $d_i{d}_j$ 个，线性期望给出边的重数 $M_{ij}$ 满足 $$𝔼M_{ij}=\frac{d_i{d}_j}{L-1},𝔼{\ell }_i=\frac{(\genfrac{}{}{0ex}{}{d_i}{2})}{L-1},$$ 其中 ${\ell }_i$ 为顶点 $i$ 的自环数，$L\ge 2$。前式不是“至少有一条边”的概率，因为可能有平行边。主例给出跨点边期望 $4/3$，每点自环期望 $1/3$，与三个配对的直接枚举一致。

一个可运行的抽样器

下面给每条半边保留顶点标号，均匀打乱后将相邻半边配对。返回端点对列表，重复端点对和自环均保留；输入度数不被改写。随机种子控制复算，模型的均匀性按理想均匀打乱理解。

Python 3

import random

def configuration_sample(degrees, seed=None):
    degrees = tuple(degrees)
    if any(type(d) is not int or d < 0 for d in degrees):
        raise ValueError("nonnegative integer degrees required")
    if sum(degrees) % 2:
        raise ValueError("degree sum must be even")
    stubs = [v for v, degree in enumerate(degrees) for _ in range(degree)]
    random.Random(seed).shuffle(stubs)
    return list(zip(stubs[::2], stubs[1::2]))

degrees = [2, 2]
edges = configuration_sample(degrees, seed=17)
actual = [0]*len(degrees)
for u, v in edges:
    actual[u] += 1
    actual[v] += 1  # a loop contributes twice
assert actual == degrees
assert configuration_sample([0, 0], 1) == []
print(edges)

若概念上把同点半边也赋予不同编号，每个完全配对恰对应 $2^{m}m!$ 个打乱排列：各对可交换内部次序，全部对可任意排列。因此从均匀排列得到均匀配对。代码虽只保存顶点标号，打乱仍等价于先打乱带标签半边再忘掉内部编号。每条半边恰使用一次，所以生成度数恒等于目标度数。时间为 $O(n+L)$，含半边列表和返回边的空间也为 $O(n+L)$。

变式。 度序列为 $(1,1,1,1)$ 时，三个配对都是无自环、无重边的完美匹配，各概率三分之一。若为 $(2,1,1)$，一个配对给中心自环加叶间边，另两个给中心连两片叶子，因此得到简单图的概率为三分之二。直接删去不合意的自环会改变度数，不能称为同一度序列的抽样。

若固定度序列存在简单实现，并拒绝整张含自环或重边的结果后重抽，那么条件于简单的分布在带标签简单图上均匀：每个简单实现恰对应 $\prod _i{d}_i!$ 个半边配对，因为每点的半边标签可任意分配给其相邻边。这个数量与具体实现无关。但接受概率可能很小，条件均匀不等于抽样必然快速。对重尾或高最大度的序列，也不能无条件声称自环和平行边在大图中可忽略。