

























Uniform sampling of simple graphs having a given degree sequence is a known problem with exponential complexity in the square of the mean degree. For undirected graphs, randomised approximation algorithms have nonetheless been shown to achieve almost linear expected complexity for this problem. Here we discuss the sequential stub matching for directed graphs and show that this process can be mould to sample simple digraphs with asymptotically equal probability. The process starts with an empty edge set and repeatedly adds edges to it with a certain state-dependent bias until the desired degree sequence is fulfilled, while avoiding placement of a double edge or self loop. We show that uniform sampling is achieved in the sparse regime, when the maximum degree $d_\text{max}$ is asymptotically dominated by $m^{1/4}$, where $m$ is the number of edges. The proof is based on deriving various combinatorial estimates related to the number of digraphs with a given directed degree sequence and controlling concentration of these estimates in large digraphs. This suggests that the sequential stub matching can be viewed as a practical algorithm for almost uniform sampling of digraphs, and we show that this algorithm can be implemented to feature linear expected runtime $O(m)$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。