Generating random graphs with large girth

ABSTRACT

We present a simple and efficient algorithm for randomly generating simple graphs without small cycles. These graphs can be used to design high performance Low-Density Parity-Check (LDPC) codes. For any constant k, α ≤ 1/2k(k + 3) and m = O(n^1+α), our algorithm generates an asymptotically uniform random graph with n vertices, m edges, and girth larger than k in polynomial time. To the best of our knowledge this is the first polynomial algorithm for the problem.

Our algorithm generates a graph by sequentially adding m edges to an empty graph with n vertices. Recently, this type of sequential process has been very successful for efficiently counting and generating random graphs [35, 18, 11, 7, 5, 6].

REFERENCES

• 1: D. Alderson, J. Doyle, and W. Willinger, "Toward and Optimization-Driven Framework for Designing and Generating Realistic Internet Topologies", HotNets, 2002.
• 2: N. Alon and J. Spencer, "The Probabilistic Method", Wiley, NY, 1992.
• 3: A. Amraoui, A. Montanari and R. Urbanke, "How to Find Good Finite-Length Codes: From Art Towards Science", Eur. Trans. Telecomm. 18 (2007), 491--508
• 4: M. Bayati, A. Montanari and A. Saberi, Generating Random Graphs with Large Girth, (2008) arXiv.
• 5: Mohsen Bayati , Jeong Han Kim , Amin Saberi, A Sequential Algorithm for Generating Random Graphs, Proceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques, August 20-22, 2007, Princeton, NJ, USA [doi>10.1007/978-3-540-74208-1_24]
• 6: J. Blanchet, "Efficient Importance Sampling for Binary Contingency Tables", preprint, 2007.
• 7: J. Blitzstein and P. Diaconis, "A sequential importance sampling algorithm for generating random graphs with prescribed degrees", preprint, 2006.
• 8: B. Bollobás, and O. Riordan, "Constrained graph processes", Electronic Journal of Combinatorics, 7, 2000.
• 9: B. Bollobás, Random Graphs, Cambrdige University Press, 2001.
• 10: T. Bu and D. Towsley, "On Distinguishing between Internet Power Law Topology Generator", INFOCOM, 2002.
• 11: Y. Chen, P. Diaconis, S. Holmes and J. S. Liu, "Sequential Monte Carlo methods for statistical analysis of tables", Journal of the American Statistical Association 100, 109--120, 2005.
• 12: S. Y. Chung, G. D. Forney, Jr., T. Richardson and R. Urbanke, "On the design of low-density parity-check codes within 0.0045 dB of the Shannon limit," IEEE Comm. Lett. 5 (2001), 58--60
• 13: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 14: X. Hu, E. Eleftheriou and D. Arnold, "Progressive Edge-Growth Tanner Graphs", Proc. of GLOBECOM 01, San Antonio, USA, Nov 2001
• 15: X. Hu, E. Eleftheriou and D. Arnold, "Regular and irregular progressive edge-growth Tanner graphs", IEEE Trans. on Inform. Theory, 51 (2005), 386--398
• 16: Paul Erdős , Stephen Suen , Peter Winkler, On the size of a random maximal graph, Random Structures & Algorithms, v.6 n.2-3, p.309-318, March-May 1995
• 17: S. Janson, T. Łuczak, and A. Rucinski, "Random Graphs", Wiley-Interscience, 2000.
• 18: Jeong Han Kim , Van H. Vu, Generating random regular graphs, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780576]
• 19: D. Knuth, "Mathematics and computer science: coping with finiteness", Science 194(4271):1235--1242, 1976.
• 20: R. Koetter and P. Vontobel, "Graph covers and iterative decoding of finite-lenght codes," Int. Conf. on Turbo codes and Rel. Topics, Brest, France, September 2003.
• 21: Michael G. Luby , Michael Mitzenmacher , M. Amin Shokrollahi , Daniel A. Spielman , Volker Stemann, Practical loss-resilient codes, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.150-159, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258573]
• 22: D. J. MacKay and M. S. Postol, "Weaknesses of Margulis and Ramanujan-Margulis Low-Density Parity-Check Codes", Elec. Notes in Theor. Comp. Science 74 (2003)
• 23: Alberto Medina , Ibrahim Matta , John Byers, On the origin of power laws in Internet topologies, ACM SIGCOMM Computer Communication Review, v.30 n.2, April 2000 [doi>10.1145/505680.505683]
• 24: R. Milo, S. ShenOrr, S. Itzkovitz, N. Kashtan, D. Chklovskii and U. Alon, "Network motifs: Simple building blocks of complex networks", Science 298, 824--827, 2002.
• 25: A. Montanari, "The asymptotic error floor of LDPC ensembles under BP decoding," 44rd Allerton Conference on Comm. Control and Comp., Monticello, IL, Sep 2006
• 26: J. M. F. Moura and J. Lu and H. Zhang "Structured low-density parity-check codes", IEEE Sign. Proc. Mag., 21 (2004), 42--55
• 27: Deryk Osthus , Anusch Taraz, Random maximal H-free graphs, Random Structures & Algorithms, v.18 n.1, p.61-82, Jan. 2001 [doi>10.1002/1098-2418(200101)18:1<61::AID-RSA5>3.0.CO;2-T]
• 28: C. Di, D. Proietti, I. E. Teletar, T. J. Richardson and R. Urbanke, "Finite-length analysis of low-density parity-check codes on the binary erasure channel", IEEE Trans. Inform. Theory, 46 (2002) 1570--1579
• 29: A. Ramamoorthy and R. Wesel, "Construction of short block length irregular low-density parity-check codes" IEEE Intern. Conf. on Comm., Paris, June 2004
• 30: T. Richardson, "Error floors of LDPC codes", 41st Allerton Conference on Comm. Control and Comp., Monticello, IL, Sep 2003
• 31: T. Richardson and R. Urbanke, Modern Coding Theory, Cambridge University Press, Cambridge 2008
• 32: J. Rosenthal and P. O. Vontobel, "Constructions of regular and irregular LDPC codes using Ramanujan graphs and ideas from Margulis", IEEE Symp. on Inform. Theory, Washington, June 2001
• 33: A. Rucinski, and N. Wormald, "Random graph processes with degree restrictions", Combin. Prob. Comput. 1, pp 169--180, 1992.
• 34: Alistair Sinclair, Algorithms for random generation and counting: a Markov chain approach, Birkhauser Verlag, Basel, Switzerland, 1993
• 35: A. Steger , N. C. Wormald, Generating Random Regular Graphs Quickly, Combinatorics, Probability and Computing, v.8 n.4, p.377-396, July 1999 [doi>10.1017/S0963548399003867]
• 36: Angelika Steger, On the Evolution of Triangle-Free Graphs, Combinatorics, Probability and Computing, v.14 n.1, p.211-224, January 2005 [doi>10.1017/S0963548304006613]
• 37: Joel Spencer, Counting extensions, Journal of Combinatorial Theory Series A, v.55 n.2, p.247-255, Nov. 1990 [doi>10.1016/0097-3165(90)90070-D]
• 38: J. Spencer, "Maximal triangle-free graphs and Ramsey R(3, t)", unpublished manuscript, 1995.
• 39: M. G. Stepanov, V. Y. Chernyak and M. Chertkov, "Diagnosis of weaknesses in modern error correction codes: a physics approach", Phys Rev. Lett. 95 (2005) 228701--228704
• 40: Hongsuda Tangmunarunkit , Ramesh Govindan , Sugih Jamin , Scott Shenker , Walter Willinger, Network topology generators: degree-based vs. structural, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 41: N. C. Wormald, "Models of random regular graphs", Surveys in combinatorics (Canterbury) London Math. Soc. Lecture Notes Ser., Vol 265. Cambridge Univ. Press, Cambridge, 239--298, 1999.
• 42: H. Xiao and A. H. Banihashemi, "Improved progressive-edge-growth (PEG) construction of LDPC codes", Proc. of GLOBECOM 04, Dallas, USA, Nov 2004

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory