Sampling regular graphs and a peer-to-peer network

ABSTRACT

We consider a simple Markov chain for d-regular graphs on n vertices, and show that the mixing time of this Markov chain is bounded above by a polynomial in n and d. A related Markov chain for d-regular graphs on a varying number of vertices is introduced, for even degree d. We use this to model a certain peer-to-peer network structure. We prove that the related chain has mixing time which is bounded by a polynomial in N, the expected number of vertices, under reasonable assumptions about the arrival and departure process.

REFERENCES

• 1: B. Bollobás, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, European Journal of Combinatorics 1 (1980), 311--316.
• 2: V. Bourassa and F. Holt, SWAN: Small-world wide area networks, in Proc. International Conference on Advances in Infrastructure (SSGRR 2003w), L'Aquila, Italy, 2003, paper #64. Available at http://www.panthesis.com/content/swan_white_paper.pdf
• 3: C. Cooper, M. Dyer and C. Greenhill, Sampling regular graphs and a peer-to-peer network, pre-print of full paper, 2004. Available from http://www.maths.unsw.edu.au/~csg/papers/cdg-preprint.pdf
• 4: C. Cooper, R. Klasing and T. Radzik, Self maintaining networks, pre-print, 2004.
• 5: A. Frieze, On random regular graphs with non-constant degree, Research report 88-2, Department of Mathematics, Carnegie-Mellon University, 1988.
• 6: L. Goldberg and M. Jerrum, Private communication, 2004.
• 7: S. Janson, T. Luczak and A. Ruciński, Random Graphs, Wiley and Sons, New York, 2000.
• 8: M. Jerrum, A. Sinclair and B. McKay, When is a graphical sequence stable?, in Random Graphs, Vol. 2 (Poznań, 1989), Wiley, New York, 1992, pp. 101--115.
• 9: M. Jerrum , A. Sinclair, Fast uniform generation of regular graphs, Theoretical Computer Science, v.73 n.1, p.91-100, June 1990 [doi>10.1016/0304-3975(90)90164-D]
• 10: Mark Jerrum , Alistair Sinclair , Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.712-721, July 2001, Hersonissos, Greece [doi>10.1145/380752.380877]
• 11: Ravi Kannan , Prasad Tetali , Santosh Vempala, Simple Markov-chain algorithms for generating bipartite graphs and tournaments, Random Structures & Algorithms, v.14 n.4, p.293-308, July 1999 [doi>10.1002/(SICI)1098-2418(199907)14:4<293::AID-RSA1>3.0.CO;2-G]
• 12: Brendan D. McKay , Nicholas C. Wormald, Uniform generation of random regular graphs of moderate degree, Journal of Algorithms, v.11 n.1, p.52-67, Mar. 1990 [doi>10.1016/0196-6774(90)90029-E]
• 13: G. Pandurangan, P. Raghavan and E. Upfal, Building low-diameter peer-to-peer networks, IEEE Journal on Selected Areas in Communications 26 (2003), 995--1002.
• 14: A. Sinclair, Improved bounds for mixing rates of Markov chains and multicommodity flow, Combinatorics, Probability and Computing 1 (1992), 351--370.
• 15: 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]
• 16: G. Tinhofer, On the generation of random graphs with given properties and known distribution, Applied Computer Science Berichte zur Praktische Informatik 13 (1979), 265--297.
• 17: N. Wormald, Models of random regular graphs, in Surveys in Combinatorics, 1999 (J. Lamb and D. Preece eds.), London Math. Soc. Lecture Notes Series 267, CUP, 1999, pp. 239--298.