• Login
    View Item 
    •   SMARTech Home
    • College of Computing (CoC)
    • Algorithms and Randomness Center (ARC)
    • ARC Talks and Events
    • View Item
    •   SMARTech Home
    • College of Computing (CoC)
    • Algorithms and Randomness Center (ARC)
    • ARC Talks and Events
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Random Walks on Small World Networks

    Thumbnail
    View/Open
    galanis.mp4 (433.1Mb)
    galanis_videostream.html (985bytes)
    Date
    2017-09-21
    Author
    Galanis, Andreas
    Metadata
    Show full item record
    Abstract
    We study the mixing time of random walks on small-world networks modelled as follows: starting with the 2-dimensional periodic grid, each pair of vertices {u,v} with distance d>1 is added as a "long-range" edge with probability proportional to d^(-r), where r>=0 is a parameter of the model. Kleinberg studied a close variant of this network model and proved that the decentralised routing time is O((logn)^2) when r=2 and n^Ω(1) when r\neq 2. Here, we prove that the random walk also undergoes a phase transition at r=2, but in this case the phase transition is of a different form. We establish that the mixing time is Θ(logn) for r<2, O((logn)^4) for r=2 and n^{Ω(1)} for r>2. Joint work with Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, and Eric Vigoda.
    URI
    http://hdl.handle.net/1853/58793
    Collections
    • ARC Talks and Events [84]

    Browse

    All of SMARTechCommunities & CollectionsDatesAuthorsTitlesSubjectsTypesThis CollectionDatesAuthorsTitlesSubjectsTypes

    My SMARTech

    Login

    Statistics

    View Usage StatisticsView Google Analytics Statistics
    facebook instagram twitter youtube
    • My Account
    • Contact us
    • Directory
    • Campus Map
    • Support/Give
    • Library Accessibility
      • About SMARTech
      • SMARTech Terms of Use
    Georgia Tech Library266 4th Street NW, Atlanta, GA 30332
    404.894.4500
    • Emergency Information
    • Legal and Privacy Information
    • Human Trafficking Notice
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    © 2020 Georgia Institute of Technology