Cover time and mixing time of random walks on dynamic graphs

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10387271" target="_blank" >RIV/00216208:11320/18:10387271 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1002/rsa.20752" target="_blank" >https://doi.org/10.1002/rsa.20752</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1002/rsa.20752" target="_blank" >10.1002/rsa.20752</a>

Result language

angličtina

Original language name

Cover time and mixing time of random walks on dynamic graphs

Original language description

The application of simple random walks on graphs is a powerful tool that is useful in many algorithmic settings such as network exploration, sampling, information spreading, and distributed computing. This is due to the reliance of a simple random walk on only local data, its negligible memory requirements, and its distributed nature. It is well known that for static graphs the cover time, that is, the expected time to visit every node of the graph, and the mixing time, that is, the time to sample a node according to the stationary distribution, are at most polynomial relative to the size of the graph. Motivated by real world networks, such as peer-to-peer and wireless networks, the conference version of this paper was the first to study random walks on arbitrary dynamic networks. We study the most general model in which an oblivious adversary is permitted to change the graph after every step of the random walk. In contrast to static graphs, and somewhat counter-intuitively, we show that there are adversary strategies that force the expected cover time and the mixing time of the simple random walk on dynamic graphs to be exponentially long, even when at each time step the network is well connected and rapidly mixing. To resolve this, we propose a simple strategy, the lazy random walk, which guarantees, under minor conditions, polynomial cover time and polynomial mixing time regardless of the changes made by the adversary.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2018

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Random Structures and Algorithms

ISSN

1042-9832

e-ISSN

—

Volume of the periodical

52

Issue of the periodical within the volume

4

Country of publishing house

US - UNITED STATES

Number of pages

21

Pages from-to

576-596

UT code for WoS article

000438011100003

EID of the result in the Scopus database

2-s2.0-85039167104