Fast generation of random connected graphs with prescribed degreesReportar como inadecuado

Fast generation of random connected graphs with prescribed degrees - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 LIAFA - Laboratoire d-informatique Algorithmique : Fondements et Applications 2 LIP6 - Laboratoire d-Informatique de Paris 6

Abstract : We address here the problem of generating random graphs uniformly from the set of simple connected graphs having a prescribed degree sequence. Our goal is to provide an algorithm designed for practical use both because of its ability to generate very large graphs efficiency and because it is easy to implement simplicity. We focus on a family of heuristics for which we prove optimality conditions, and show how this optimality can be reached in practice. We then propose a different approach, specifically designed for typical real-world degree distributions, which outperforms the first one. Assuming a conjecture which we state and argue rigorously, we finally obtain an log-linear algorithm, which, in spite of being very simple, improves the best known complexity.

Keywords : Connectivity Generation Model Graphs Random Graphs

Autor: Fabien Viger - Matthieu Latapy -



Documentos relacionados