Document Open Access Logo

Brief Announcement: Rapid Mixing of Local Dynamics on Graphs

Authors Laurent Massoulié, Rémi Varloot

PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.59.pdf
  • Filesize: 323 kB
  • 3 pages

Document Identifiers

Author Details

Laurent Massoulié
Rémi Varloot

Cite As Get BibTex

Laurent Massoulié and Rémi Varloot. Brief Announcement: Rapid Mixing of Local Dynamics on Graphs. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 59:1-59:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.DISC.2017.59

Abstract

In peer-to-peer networks, it is desirable that the logical topology of connections between the constituting nodes make a well-connected graph, i.e., a graph with low diameter and high expansion. At the same time, this graph should evolve only through local modifications. These requirements prompt the following question: are there local graph dynamics that i) create a well-connected graph in equilibrium, and ii) converge rapidly to this equilibrium?

In this paper we provide an affirmative answer by exhibiting a local graph dynamic that mixes provably fast. Specifically, for a graph on N nodes, mixing has occurred after each node has performed O(polylog(N)) operations. This is in contrast with previous results, which required at least Omega(N polylog(N)) operations per node before the graph had properly mixed.

Subject Classification

Keywords
  • Markov chains
  • Mixing time
  • Dynamic graphs
  • Local dynamics

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Réka Albert and Albert lászló Barabási. Statistical mechanics of complex networks. Rev. Mod. Phys, page 2002. Google Scholar
  2. Zeyuan Allen Zhu, Aditya Bhaskara, Silvio Lattanzi, Vahab S. Mirrokni, and Lorenzo Orecchia. Expanders via local edge flips. CoRR, abs/1510.07768, 2015. Google Scholar
  3. N. Berestycki. Mixing times of markov chains: Techniques and examples. Alea-Latin American Journal of Probability and Mathematical Statistics, 2016. URL: http://www.statslab.cam.ac.uk/~beresty/teach/Mixing/mixing3.pdf.
  4. Shankar Bhamidi, Guy Bresler, and Allan Sly. Mixing time of exponential random graphs. The Annals of Applied Probability, 21(6):2146-2170, 12 2011. Google Scholar
  5. Colin Cooper, Martin Dyer, and Andrew J. Handley. The flip markov chain and a randomising p2p protocol. In Proceedings of the 28th ACM Symposium on Principles of Distributed Computing, PODC'09, pages 141-150, New York, NY, USA, 2009. ACM. URL: http://dx.doi.org/10.1145/1582716.1582742.
  6. Colin Cooper, Ralf Klasing, and Tomasz Radzik. A randomized algorithm for the joining protocol in dynamic distributed networks. Technical Report RR-5376, INRIA, November 2004. URL: https://hal.inria.fr/inria-00070627.
  7. Rick Durrett. Random Graph Dynamics. Cambridge University Press, Cambridge, 2007. URL: http://www.math.cornell.edu/~durrett/RGD/RGD.html.
  8. Tomas Feder, Adam Guetz, Milena Mihail, and Amin Saberi. A local switch markov chain on given degree graphs with application in connectivity of peer-to-peer networks. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS'06, pages 69-76, Washington, DC, USA, 2006. IEEE Computer Society. URL: http://dx.doi.org/10.1109/FOCS.2006.5.
  9. Riko Jacob, Andrea Richa, Christian Scheideler, Stefan Schmid, and Hanjo Täubig. A distributed polylogarithmic time algorithm for self-stabilizing skip graphs. In Proceedings of the 28th ACM Symposium on Principles of Distributed Computing, PODC'09, pages 131-140, New York, NY, USA, 2009. ACM. URL: http://dx.doi.org/10.1145/1582716.1582741.
  10. M. Jerrum and Alistair Sinclair. Approximating the permanent. SIAM J. Comput., 18(6):1149-1178, dec 1989. Google Scholar
  11. Johan Jonasson. Mixing times for the interchange process. Alea-Latin American Journal of Probability and Mathematical Statistics, 9(2):667-683, 2012. Google Scholar
  12. Minkyu Kim and Muriel Medard. Robustness in large-scale random networks. INFOCOM, 2004. Google Scholar
  13. Manos Papagelis. Refining social graph connectivity via shortcut edge addition. ACM Trans. Knowl. Discov. Data, 10(2):12:1-12:35, oct 2015. Google Scholar
  14. Jason Schweinsberg. An o(n2) bound for the relaxation time of a markov chain on cladograms. Random Struct. Algorithms, 20(1):59-70, jan 2002. Google Scholar
  15. Lingsheng Shi and Nicholas Wormald. Models of random regular graphs. In IN SURVEYS IN COMBINATORICS, pages 239-298. University Press, 1999. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact