### 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 | |

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

### Cite this

*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

}

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

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

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 -