Uniform generation of random graphs with power-law degree sequences

Pu Gao; Nicholas Wormald

doi:10.1137/1.9781611975031.114

Uniform generation of random graphs with power-law degree sequences

Pu Gao, Nicholas Wormald

School of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research

18 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 language	English
Title of host publication	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Subtitle of host publication	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
Editors	Artur Czumaj
Publisher	Association for Computing Machinery (ACM)
Pages	1741-1758
Number of pages	18
ISBN (Electronic)	9781611975031
DOIs	https://doi.org/10.1137/1.9781611975031.114
Publication status	Published - 1 Jan 2018
Event	ACM-SIAM Symposium on Discrete Algorithms, 2018 - New Orleans, United States of America Duration: 7 Jan 2018 → 10 Jan 2018 Conference number: 29th

Conference

Conference	ACM-SIAM Symposium on Discrete Algorithms, 2018
Abbreviated title	SODA 2018
Country/Territory	United States of America
City	New Orleans
Period	7/01/18 → 10/01/18
Other	This 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.

Access to Document

10.1137/1.9781611975031.114

252783983-oaFinal published version, 505 KB

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 = jan,

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",

note = "ACM-SIAM Symposium on Discrete Algorithms, 2018, SODA 2018 ; Conference date: 07-01-2018 Through 10-01-2018",

}

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 proceeding › Conference Paper › Research

TY - GEN

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

AU - Gao, Pu

AU - Wormald, Nicholas

N1 - Conference code: 29th

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

AN - SCOPUS:85045545375

SP - 1741

EP - 1758

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

A2 - Czumaj, Artur

PB - Association for Computing Machinery (ACM)

T2 - ACM-SIAM Symposium on Discrete Algorithms, 2018

Y2 - 7 January 2018 through 10 January 2018

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 doi: 10.1137/1.9781611975031.114

Uniform generation of random graphs with power-law degree sequences

Abstract

Conference

Access to Document

Other files and links

New approaches to the random generation of combinatorial objects

Cite this

Uniform generation of random graphs with power-law degree sequences

Abstract

Conference

Access to Document

Other files and links

Projects

New approaches to the random generation of combinatorial objects

Cite this