2021/10/28 by Allendorf, Daniel, Meyer, Ulrich, Penschuck, Manuel +2
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #G.2.2
paper · doi:10.48550/arxiv.2110.15015
We consider the following common network analysis problem: given a degree sequence d = (d1, …, dn) ∈ \mathbb Nn return a uniform sample from the ensemble of all simple graphs with matching degrees. In practice, the problem is typically solved using Markov Chain Monte Carlo approaches, such as Edge-Switching or Curveball, even if no practical useful rigorous bounds are known on their mixing times. In contrast, Arman et al. sketch Inc-Powerlaw, a novel and much more involved algorithm capable of generating graphs for power-law bounded degree sequences with γ\gtrapprox 2.88 in expected linear time. For the first time, we give a complete description of the algorithm and add novel switchings. To the best of our knowledge, our open-source implementation of Inc-Powerlaw is the first practical generator with rigorous uniformity guarantees for the aforementioned degree sequences. In an empirical investigation, we find that for small average-degrees Inc-Powerlaw is very efficient and generates graphs with one million nodes in less than a second. For larger average-degrees, parallelism can partially mitigate the increased running-time.