Deterministic Random Walks for Network Exploration and Cover Time Analysis
Explore the concept of deterministic random walks in network exploration. Understand the cover time and its significance in traversing graphs efficiently. Discover the simplicity and robustness of random walks in navigating through connected graphs.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
The Cover Time of Deterministic Random Walks for General Transition Probabilities Takeharu Shiraga* *Kyushu University, Japan wikipedia
2 Network exploration by random walks This work is corresponding to the network exploration by random walks and deterministic random walks Random walks are well studied for an approach to the network exploration, since its simplicity, locality, and robustness to change in graphs.
3 Simple random walks on a graph Simple random walk on ? ? = ?,? : undirected connected graph ?0 ?: initial position of an agent (token) At each time step, a token chooses a neighboring vertex u.a.r., and move to it, repeatedly. t=0 t=1 t=2 t=3
4 Cover time Cover time ?cover: Expected time until every vertex has been visited by the token
5 The cover time of simple random walks ?cover?,?0: cover time of SRW on ? starting at ?0 ?cover? max ?cover?,?0 ?0 Theorem. [Feige 95],[Feige 95] 4 27?? 4 27?? ?, 1 ? 1 ????? ? ? 1 + ? 1 1 ? 1 ????? ?cover? 1 + ? 1 Complete graph ?? Lollipop graph ?? ?cover?? = ?3 ?cover?? = ?log?
6 The cover time of simple random walks Theorem. [Matthews 88] ?cover ?hitlog? ?,? ?? ?,? hitting time ? ?,? : expected number of transitions from x to y ?hit max x y
7 Summary (so far) Simple RW k=1 ?3 ?hitlog?
8 k-simple random walks on a graph k-simple random walks : k-independent parallel simple random walks ?0 ?: initial configuration of ? agents (tokens) At each time step, each token random walks independently. t=0 t=1 t=2 t=3
9 Cover time of k-simple random walks ?cover?,?0: cover time of k-SRWs on ? starting from ?0 ?0?cover?,?0 ?cover? max Theorem. [Elasser & Sauerwald 10] ?cover? = ?mix+?hitlog? ?,? ? ? k times speed up for small k ? ?? ?mix min ? 0 ? ???,? 1 2 1 log?min 1 ?2 ? = ?mix= D: diameter of G
10 Summary (so far) Simple RW k=1 ?3 ?hitlog? k 1 ?mix+?hitlog? ?
11 Deterministic random walk From the view point of the deterministic graph exploration, the rotor-router model is well studied recently Rotor-router model [Propp 2000] : deterministic analogy of a simple random walk
12 Idea of the rotor-router model Rotor-router : we define arbitrary ordering, tokens move by the ordering SRW : each token moves randomly 1 3 2
13 Rotor-router model Rotor-router model on ? with ? = ?? ? ? ? = ?,? : undirected graph ??= ??0 ,??1 , ,??? ? 1 : ordering of neighboring vertices of ? 1 1 2 4 3 2 3 1 2 1 4 1 1 2 3 4 1 3 2 2 3 2 1 3 1 1 2 3 2 2
14 Rotor-router model Rotor-router model on ? with ? = ?? ? ? ?0 ?: initial configuration of ? tokens over ? At each time step, each token moves according to rotor-router t=0 1 1 2 4 3 2 3 1 2 1 4 1 1 2 3 4 1 3 2 2 3 2 1 3 1 1 2 3 2 2
15 Rotor-router model At each time step, each token moves according to rotor-router t=0 t=1 t=2 t=3 t=4 1 2 1 4 3 2 1 3 2 1 4 1 1 3 4 1 2 3 2 2 3 2 1 3 1 1 2 3 2 2
16 The cover time of rotor-router models (k=1) ?cover?,?,?0: cover time of the RRM ?,? with ?0 Theorem. [Yaknowski et al. 03] ? = 1, ?,?,?0 ?cover?,?,? = ?? m=|E|, D: diameter Theorem. [Bampas et al. 09] ? = 1, ?,?0, ? s.t. ?cover?,?,? = ??
17 The cover time of rotor-router models (k 1) Theorem. [Kosowski & Pajak 14] = ?mix+ ? ??mix ?,?,?0 ?cover?,?,?0 ? k times speed up for small k ?: maximum degree/ minimum degree ?: number of edges ? ?? ?mix min ? 0 ? ???,? 1 2 1 log?min 1 ?2 ? = ?mix=
18 Summary (so far) Det.simple RW (RRM) Simple RW k=1 k=1 ?3 ?? ?hitlog? k 1 k 1 ?mix+ ? ??mix ?mix+?hitlog? ? ?
20 General transition probabilities Transition probabilities are uniform (simple) so far [Ikeda et al. 03] took an approach for speeding up, which uses modified transition probabilities (not simple RW). weighted RW v P(v,c) P(v,a) 1/3 1/3 1/3 P(v,b) a c b
21 General (not simple) random walks Random walk according to P ? ? ?: transition matrix on ? ? ?,? : transition probability from ? to ? Eg. transition matrix of the simple RW on G ??? (? ? ? ) otherwise ??? ?,? = 1 ? ? 0 1/3 1/3 1/3
22 General (not simple) random walks ?cover?,?0: Cover time of the RW according to ? with ?0 ?0?cover?,?0 ?cover? = max Theorem. [Ikeda et al. 03] = ?2log? ? = 1, ? ?cover ??? transition matrix of the ?-RW on ? ? ? 1 2 ? ? ? ? ? ?? ? 1 0 ??? ?,? 2 otherwise
23 Summary (so far) Det.simple RW (RRM) Simple RW k=1 k=1 ?3 ?? ?hitlog? k 1 k 1 ?mix+ ? ??mix ?mix+?hitlog? ? ? Not simple RW ?2log? ?-RW
24 Det. RWs for general transition probabilities Rotor-router model [Propp 2000] : deterministic analogy of simple random walks Deterministic analogy of general random walks Stack walk [Holroyd & Propp 10] SRT-router model, Billiard router model [S. et al. 13]
25 Billiard sequence ??: billiard sequence of ? ? ?: probability distribution on V a, b, c Eg. ? = 1 2, 1 3, 1 6 ? ? ? ? a ?/?= ? ? ?/?= ? ? ?/?= ? b c ??= a,b,a,a,b,c,a,b,a,
26 Billiard sequence ??: billiard sequence of ? ? ?: probability distribution ? ?: probability distribution ??: billiard sequence of ? Eg. ? = 1 3, 1 3, 1 3 ? ? ? ? a ?/?= ? ? ?/?= ? ? ?/?= ? b c ??= a,b,c,a,b,c,a,b,c, Billiard sequence of the uniform distribution is rotor-router
27 Billiard-router model Billiard-router model according to ? with ? = ?? ? ? ? ? ?: transition matrix on ? ??= ?? ?, : ordering of the neighboring vertices defined by billiard sequence of ? ?, At each time round, each token moves by billiard-router 1 2, 1 3, ? ?, = 1 6 v ??= a,b,a,a,b,c,a,b,a, 1/2 1/6 1/3 a c b
28 Motivation and our result Nothing is known about the cover time of the deterministic random walks for general transition probabilities Results We obtain the first result of an upper bound of the cover time for the deterministic random walks for general transition probabilities Our upper bound improves the previous results of the rotor-router model
29 Summary (so far) Det.simple RW (RRM) Simple RW k=1 k=1 ?3 ?? ?hitlog? k 1 k 1 ?mix+ ? ??mix ?mix+?hitlog? ? ? Not simple RW Not simple det.RW (BRM) ?2log? ?-RW ???
30 Our result Det.simple RW (RRM) Simple RW k=1 k=1 ?3 ?? ?hitlog? k 1 k 1 ?mix+ ? ??mix ? ?mix+?hitlog? ? ? ????+????? ? Not simple RW Not simple det.RW (BRM) ??mix ?min ? ?2log? ?-RW ? ? ?mix+
32 Main result Main theorem [Cover time of billiard-router models] reversible ?, ?,?0 ? ? ? ? ?mix ? ?cover?,?,?0 = ?mix+ max ? ?: stationary distribution of P (?? = ?) Reversible P: ?,? ?? ? ? ?,? = ? ? ? ?,? 1 ? ? =? ? log?min 1 ?2 for simple RWs ? = ?mix= 2?
33 Main result Main theorem [Cover time of billiard-router models] reversible ?, ?,?0 ? ? ? ? ?mix ? ?cover?,?,?0 = ?mix+ max ? We obtain the first upper bound for deterministic random walks for general transition probabilities ! This upper bound also holds for stack walks, SRT-router
34 Corollary Main theorem [Cover time of billiard-router models] reversible ?, ?,?0 ? ? ? ? ?mix ? ?cover?,?,?0 = ?mix+ max ? ? ? =? ? 2? for simple RWs Corollary. [Cover time of rotor-router models] = ?mix+??mix ?,?,?0 ?cover?,?,?0 ?
35 Upper bound for the rotor-router Corollary. [Cover time of rotor-router models] = ?mix+??mix ?,?,?0 ?cover?,?,?0 ? Theorem. [Kosowski & Pajak 14] = ?mix+? ? ??mix ?cover?,?,?0 ?,?,?0 ? ?: maximum degree/ minimum degree Our theorem improves the previous result of the rotor-router !
36 Our result Det.simple RW (RRM) Simple RW k=1 k=1 ?3 ?? ?hitlog? k 1 k 1 ?mix+ ? ??mix ? ?mix+?hitlog? ? ? ????+????? ? Not simple RW Not simple det.RW (BRM) ??mix ?min ? ?2log? ?-RW ? ? ?mix+
38 Idea of the proof Discrepancy between the visit frequency of det. RW and the expected visit frequency of RM Cover time of det. RWs
39 Visit frequency ?: Total number of times that tokens visited vertex ? by ?? time ? in deterministic RWs (visit frequency) ?: Expected visit frequency of corresponding RWs ?? Lemma reversible ?,?,?0, ? ?, ? 1, ? ? ?? ? ?? ? ?? = ???mixmax ? ? Constant for ? and ?
40 Intuition of the visit frequency lemma 10000 v 10 3333 10000/3 3334 4 3 v 10/3 10000/3 10/3 3 10/3 3333 10000/3 |4-10/3|<1 |3334-10000/3|<1 |3-10/3|<1 |3333-10000/3|<1 |Det. flow expected flow|<c for any number of tokens and time. |Det. visit frequency expected visit frequency|<c
41 Visit frequency and the cover time Lemma reversible ?,?,?0, ? ?, ? 1, ? ? ?? ? ?? ? ?? = ???mixmax ? ? ? ? ?? Const. ? ???mixmax ? ? ???? 2?mix ? ?? ? Const. ?? Const. 4 Property of random walks ? ?? ???? 2?mix 4
42 Visit frequency and the cover time ? ???? 2?mix ?? Const. 4 ???? 2?mix 4 ?> 0 ?? Const.> 0 ? > 2?mix+4Const. ? 1 ?? ?? ? (?? ? )
43 Visit frequency and the cover time ? > 2?mix+4Const. ? 1 ?? ?? ? w has been visited ! Main theorem [Cover time of billiard-router models] ?mix ?min ? ?cover?,?,?0 = ?mix+ We obtain the upper bound of the cover time if the discrepancy between visit frequencies is upper bounded.
45 Summary of this talk Det.simple RW (RRM) Simple RW k=1 k=1 ?3 ?? ?hitlog? k 1 k 1 ?mix+ ? ??mix ? ?mix+?hitlog? ? ? ????+????? ? Not simple RW Not simple det.RW (BRM) ??mix ?min ? ?2log? ?-RW ? ? ?mix+
46 Future works Better bound for the cover time (visit frequency) Derandomize ?-random walk ?cover??? ,? = ?? = ?3 ?cover??? = ?3 ?cover??? ,? = ?2log? ?? ?cover ??? = ?2log?
Thank you for the attention ! The Cover Time of Deterministic Random Walks for General Transition Probabilities Takeharu Shiraga* *Kyushu University, Japan
48 Summary of this talk Det.simple RW (RRM) Simple RW k=1 k=1 ?3 ?? ?hitlog? k 1 k 1 ?mix+ ? ??mix ? ?mix+?hitlog? ? ? ????+????? ? Not simple RW Not simple det.RW (BRM) ??mix ?min ? ?2log? ?-RW ? ? ?mix+
50 Hitting time and cover time ?? min ? 0 ??= ? ? ?,? = ???? ?cover min ? 0 ?0,?1, ,?? = ? ? ?,?1 ?, ,?? ? ?cover min ? 0 ??0 = ?
