论文标题
连接性问题：连接图的结构和精确随机采样
Connectedness matters: Construction and exact random sampling of connected graphs
论文作者
论文摘要
我们描述了一种具有指定度序列的连接网络随机采样的新方法。我们考虑了简单图的情况，也是无环的多编码的情况。在构建用于物理或生物网络的实际分析的无效模型时，固定度和连接性的限制是两个最常用的限制。然而，处理这些约束，更不用说将它们结合起来是不平凡的。我们的方法建立在最近引入的新型采样方法的基础上，该方法独立地构建具有给定度的图形（与边缘开关马尔可夫链蒙特卡洛方法不同）并有效地（与配置模型不同），并扩展了它以结合连接性的约束。此外，我们提出了一种简单而优雅的算法，用于直接构建一个简单序列的单个连接实现，无论是简单的图形还是多编码。最后，我们在无标度的示例以及连接的现实世界网络的程度序列上演示了我们的采样方法，并证明执行连接性可以显着改变采样网络的属性。
We describe a new method for the random sampling of connected networks with a specified degree sequence. We consider both the case of simple graphs and that of loopless multigraphs. The constraints of fixed degrees and of connectedness are two of the most commonly needed ones when constructing null models for the practical analysis of physical or biological networks. Yet handling these constraints, let alone combining them, is non-trivial. Our method builds on a recently introduced novel sampling approach that constructs graphs with given degrees independently (unlike edge-switching Markov Chain Monte Carlo methods) and efficiently (unlike the configuration model), and extends it to incorporate the constraint of connectedness. Additionally, we present a simple and elegant algorithm for directly constructing a single connected realization of a degree sequence, either as a simple graph or a multigraph. Finally, we demonstrate our sampling method on a realistic scale-free example, as well as on degree sequences of connected real-world networks, and show that enforcing connectedness can significantly alter the properties of sampled networks.
