The uniform sampling of simple graphs matching a prescribed degree sequence is an important tool in network science, e.g., to construct graph generators or null-models. Here, the Edge Switching Markov Chain (ES-MC) is a common choice. Given an arbitrary simple graph with the required degree sequence, ES-MC carries out a large number of small changes involving at most four edges to eventually obtain a uniform sample. In practice, reasonably short runs efficiently yield approximate uniform samples. We first engineer a simple sequential ES-MC implementation representing the graph in a hash-set. Despite its simplicity and to the best of our knowledge, our implementation significantly outperforms all openly available solutions. Secondly, we propose the Global Edge Switching Markov Chain (G-ES-MC) and show that it, too, converges to a uniform distribution. We provide empirical evidence that G-ES-MC requires not more switches than ES-MC (and often fewer). Thirdly, we engineer shared-memory parallel algorithms for ES-MC and G-ES-MC; we find that they benefit from the easier dependency structure of the G-ES-MC. In an empirical evaluation, we demonstrate the scalability of our implementations.
翻译:对符合规定度序列的简单图表进行统一抽样,这在网络科学中是一个重要的工具,例如,用来建造图形生成器或无名模型。这里,边缘开关马可夫链(ES-MC)是一个常见的选择。鉴于一个带有所需度序列的任意简单图表,ES-MC可以进行大量小的改动,在大多数四个边缘进行,以便最终获得一个统一的样本。在实践中,合理的短跑效率能产生大致相同的样本。我们首先设计一个简单的顺序顺序的ES-MC实施方法,在散列中代表该图。尽管我们的知识非常简单,但我们的实施工作大大超越了所有公开提供的解决办法。第二,我们建议采用全球开关马可夫链(G-ES-MC),并表明它也与统一分布。我们提供了实证证据,证明G-ES-MC所需要的开关并不比ES-MC(而且往往更少)多。第三,我们为ES-MC和G-ES-MC设计了一个共同的模拟平行算法。我们发现它们从G-ES-MC的较容易依赖性结构中获益。我们的经验性评估了。我们如何评价。