Hostname: page-component-74656f9884-6grmk Total loading time: 0 Render date: 2026-11-05T22:36:54.724Z Has data issue: false hasContentIssue false
  • English
  • Français

Sampling Regular Graphs and a Peer-to-Peer Network

Published online by Cambridge University Press:  01 July 2007

COLIN COOPER ,
MARTIN DYER  and
CATHERINE GREENHILL
COLIN COOPER
Affiliation:
Department of Computer Science, Kings College, London WC2R 2LS, UK (e-mail: ccooper@dcs.kcl.ac.uk)
MARTIN DYER
Affiliation:
School of Computing, University of Leeds, Leeds LS2 9JT, UK (e-mail: dyer@comp.leeds.ac.uk)
CATHERINE GREENHILL
Affiliation:
School of Mathematics, The University of New South Wales, Sydney NSW 2052, Australia (e-mail: csg@unsw.edu.au)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

This paper has two parts. In the first part we consider a simple Markov chain for d-regular graphs on n vertices, where d = d(n) may grow with n. We show that the mixing time of this Markov chain is bounded above by a polynomial in n and d. In the second part of the paper, a related Markov chain for d-regular graphs on a varying number of vertices is introduced, for even constant d. This is a model for a certain peer-to-peer network. We prove that the related chain has mixing time which is bounded above by a polynomial in N, the expected number of vertices, provided certain assumptions are met about the rate of arrival and departure of vertices.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 4 , July 2007 , pp. 557 - 593
Copyright
Copyright © Cambridge University Press 2006

References

[1]Bender, E. and Canfield, E. (1978) The asymptotic number of labeled graphs with given degree sequences. J. Combin. Theory Ser. A 24 296–307.CrossRefGoogle Scholar
[2]Bezáková, I., Bhatnagar, N. and Vigoda, E. (2006) Sampling binary contingency tables with a greedy start. SODA 2006, submitted to Random Structures and Algorithms.CrossRefGoogle Scholar
[3]Bollobás, B. (1980) A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Eur. J. Combin. 1 311–316.CrossRefGoogle Scholar
[4]Bourassa, V. and Holt, F. (2003) SWAN: Small-world wide area networks. In Proc. International Conference on Advances in Infrastructure, L'Aquila, Italy (SSGRR 2003w), paper # 64. Available at http://www.panthesis.com/content/swan_white_paper.pdfGoogle Scholar
[5]Chartrand, G. and Lesniak, L. (1996) Graphs and Digraphs, 3rd edn, Chapman and Hall, London.Google Scholar
[6]Cooper, C., Klasing, R. and Radzik, T. A randomized algorithm for the joining protocol in dynamic distributed networks. Theoret. Comput. Sci., to appear. Also available as INRIA research report RR-5376 (CNRS report I3S/RR-2004-39-FR).Google Scholar
[7]Feller, W. (1968) An Introduction to Probability Theory and its Applications, Vol. I, 3rd edn, Wiley, New York.Google Scholar
[8]Frieze, A. (1988) On random regular graphs with non-constant degree. Research report 88-2, Department of Mathematics, Carnegie-Mellon University.Google Scholar
[9]Gkantsidis, C., Mihail, M. and Saberi, A. (2004) On the Random Walk Method in Peer-to-Peer Networks, INFOCOM 04.Google Scholar
[10]Goldberg, L. and Jerrum, M. (2004) Private communication.Google Scholar
[11]Holt, F. B., Bourassa, V., Bosnjakovic, A. M. and Popovic, J. (2005) SWAN: Highly reliable and efficient networks of true peers. In Handbook on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless, and Peer-to-Peer Networks (Wu, J., ed.), CRC Press, Boca Raton, Florida, pp. 799–824.Google Scholar
[12]Hu, J., Macdonald, A. H. and McKay, B. D. (1994) Correlations in two-dimensional vortex liquids. Phys. Review B 49 15263–15270.CrossRefGoogle ScholarPubMed
[13]Jerrum, M. and Sinclair, A. (1990) Fast uniform generation of regular graphs. Theoret. Comput. Sci. 73 91–100.CrossRefGoogle Scholar
[14]Jerrum, M., Sinclair, A. and McKay, B. (1992) When is a graphical sequence stable? In Random Graphs, Vol. 2 (Poznań 1989), Wiley, New York, pp. 101–115.Google Scholar
[15]Jerrum, M., Sinclair, A. and Vigoda, E. (2004) A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. J. Assoc. Comput. Mach. 51 671–697.CrossRefGoogle Scholar
[16]Jerrum, M., Son, J.-B., Tetali, P. and Vigoda, E. (2004) Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains. Ann. Appl. Math. 14 1741–1765.Google Scholar
[17]Kannan, R., Tetali, P. and Vempala, S. (1999) Simple Markov-chain algorithms for generating bipartite graphs and tournaments. Random Struct. Alg. 14 293–308.3.0.CO;2-G>CrossRefGoogle Scholar
[18]Kim, J. H. and Vu, V. H. (2003) Generating random regular graphs. In Proc. 35th Symposium on Theory of Computing, ACM Press, New York, pp. 213–222.Google Scholar
[19]Law, C. and Siu, K.-Y. (2003) Distributed construction of random expander networks. In Proc. INFOCOM 2003, IEEE.Google Scholar
[20]McKay, B. and Wormald, N. (1990) Uniform generation of random regular graphs of moderate degree. J. Algorithms 11 52–67.CrossRefGoogle Scholar
[21]Martin, R. A. and Randall, D. (2000) Sampling adsorbing staircase walks using a new Markov chain decomposition method. In Proc. 41st Symposium on Foundations of Computer Science, IEEE, Los Alamitos, pp. 492–502.CrossRefGoogle Scholar
[22]Pandurangan, G., Raghavan, P. and Upfal, E. (2003) Building low-diameter peer-to-peer networks. IEEE J. Selected Areas in Communications 26 995–1002.CrossRefGoogle Scholar
[23]Robinson, R. W. and Wormald, N. C. (1994) Almost all regular graphs are Hamiltonian. Random Struct. Alg. 5 363–374.CrossRefGoogle Scholar
[24]Sinclair, A. (1992) Improved bounds for mixing rates of Markov chains and multicommodity flow. Combin. Probab. Comput. 1 351–370.CrossRefGoogle Scholar
[25]Steger, A. and Wormald, N. (1999) Generating random regular graphs quickly. Combin. Probab. Comput. 8 377–396.CrossRefGoogle Scholar
[26]Tinhofer, G. (1979) On the generation of random graphs with given properties and known distribution. Appl. Comput. Sci. Ber. Prakt. Inf. 13 265–297.Google Scholar
[27]Tutte, W. (1954) A short proof of the factor theorem for finite graphs. Canadian J. Math. 6 347–352.CrossRefGoogle Scholar
[28]Wormald, N. (1978) Some problems in the enumeration of labelled graphs. PhD thesis, University of Newcastle.Google Scholar