Uniform generation of random graphs with power-law degree sequences

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearch

10 Citations (Scopus)


We give a linear-time algorithm that approximately uniformly generates a random simple graph with a power-law degree sequence whose exponent is at least 2.8811. While sampling graphs with power-law degree sequence of exponent at least 3 is fairly easy, and many samplers work efficiently in this case, the problem becomes dramatically more difficult when the exponent drops below 3; ours is the first provably practicable sampler for this case. We also show that with an appropriate rejection scheme, our algorithm can be tuned into an exact uniform sampler. The running time of the exact sampler is O(n2:107) with high probability, and O(n4:081) in expectation.

Original languageEnglish
Title of host publicationProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Subtitle of host publication29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018; Astor Crowne Plaza - New Orleans French QuarterNew Orleans; United States; 7 January 2018 through 10 January 2018
EditorsArtur Czumaj
PublisherAssociation for Computing Machinery (ACM)
Number of pages18
ISBN (Electronic)9781611975031
Publication statusPublished - 1 Jan 2018
EventACM-SIAM Symposium on Discrete Algorithms, 2018 - New Orleans, United States of America
Duration: 7 Jan 201810 Jan 2018
Conference number: 29th


ConferenceACM-SIAM Symposium on Discrete Algorithms, 2018
Abbreviated titleSODA 2018
Country/TerritoryUnited States of America
CityNew Orleans
OtherThis symposium focuses on research topics related to efficient algorithms and data structures for discrete problems. In addition to the design of such methods and structures, the scope also includes their use, performance analysis, and the mathematical problems related to their development or limitations. Performance analyses may be analytical or experimental and may address worst-case or expected-case performance. Studies can be theoretical or based on data sets that have arisen in practice and may address methodological issues involved in performance analysis.

Cite this