Parallel Global Edge Switching for the Uniform Sampling of Simple Graphs with Prescribed Degrees
2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS)(2022)
摘要
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 uni-form 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.
更多查看译文
关键词
random graphs,degrees,edge switching,markov chain,parallelism
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要