VaLUH: Fast Algorithms for the Configuration Model of Vertex-Labeled Undirected Hypergraphs

We present VaLUH, a suite of Markov-Chain-Monte-Carlo algorithms for uniformly sampling non-degenerate, vertex-labeled, undirected hypergraphs with prescribed vertex degrees and hyperedge sizes (the hypergraph micro-canonical configuration model). One of our methods is based on stub-labeled hypergraphs, one on edgelabeled hypergraphs, and the third directly samples vertex-labeled hypergraphs. We theoretically show that our algorithms require as many or fewer steps to converge to the stationary distribution than existing ones, because they are higher in Peskun's order. We obtain this improvement by carefully defining the state space graph of the Markov chains and by optimizing the transition probabilities, using the Metropolis-Hastings approach. Our experimental evaluation on real networks shows that our methods are up to 6x faster, in number of steps and also in wall-clock time, than existing approaches, as they require less computation per step, with the direct algorithm being the fastest.