Uniform generation of random graphs with power-law degree sequences

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

2 Citations (Scopus)

Abstract

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)
Pages1741-1758
Number of pages18
ISBN (Electronic)9781611975031
DOIs
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

Conference

ConferenceACM-SIAM Symposium on Discrete Algorithms, 2018
Abbreviated titleSODA 2018
CountryUnited States of America
CityNew Orleans
Period7/01/1810/01/18
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

Gao, P., & Wormald, N. (2018). Uniform generation of random graphs with power-law degree sequences. In A. Czumaj (Ed.), Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms: 29th 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 (pp. 1741-1758). Association for Computing Machinery (ACM). https://doi.org/10.1137/1.9781611975031.114
Gao, Pu ; Wormald, Nicholas. / Uniform generation of random graphs with power-law degree sequences. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms: 29th 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. editor / Artur Czumaj. Association for Computing Machinery (ACM), 2018. pp. 1741-1758
@inproceedings{f37ee542afa441c5b30f3be5af7272f0,
title = "Uniform generation of random graphs with power-law degree sequences",
abstract = "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.",
author = "Pu Gao and Nicholas Wormald",
year = "2018",
month = "1",
day = "1",
doi = "10.1137/1.9781611975031.114",
language = "English",
pages = "1741--1758",
editor = "Artur Czumaj",
booktitle = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",
publisher = "Association for Computing Machinery (ACM)",
address = "United States of America",

}

Gao, P & Wormald, N 2018, Uniform generation of random graphs with power-law degree sequences. in A Czumaj (ed.), Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms: 29th 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. Association for Computing Machinery (ACM), pp. 1741-1758, ACM-SIAM Symposium on Discrete Algorithms, 2018, New Orleans, United States of America, 7/01/18. https://doi.org/10.1137/1.9781611975031.114

Uniform generation of random graphs with power-law degree sequences. / Gao, Pu; Wormald, Nicholas.

Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms: 29th 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. ed. / Artur Czumaj. Association for Computing Machinery (ACM), 2018. p. 1741-1758.

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

TY - GEN

T1 - Uniform generation of random graphs with power-law degree sequences

AU - Gao, Pu

AU - Wormald, Nicholas

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85045545375&partnerID=8YFLogxK

U2 - 10.1137/1.9781611975031.114

DO - 10.1137/1.9781611975031.114

M3 - Conference Paper

SP - 1741

EP - 1758

BT - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

A2 - Czumaj, Artur

PB - Association for Computing Machinery (ACM)

ER -

Gao P, Wormald N. Uniform generation of random graphs with power-law degree sequences. In Czumaj A, editor, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms: 29th 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. Association for Computing Machinery (ACM). 2018. p. 1741-1758 https://doi.org/10.1137/1.9781611975031.114