Hostname: page-component-745bb68f8f-mzp66 Total loading time: 0 Render date: 2025-01-12T12:53:37.015Z 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: [email protected])
MARTIN DYER
Affiliation:
School of Computing, University of Leeds, Leeds LS2 9JT, UK (e-mail: [email protected])
CATHERINE GREENHILL
Affiliation:
School of Mathematics, The University of New South Wales, Sydney NSW 2052, Australia (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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