Upgrade to Pro — share decks privately, control downloads, hide ads and more …

How Many Vertices Does a Random Walk Miss in a ...

How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?

slide at SODA2021

Nobutaka Shimizu

July 05, 2022
Tweet

More Decks by Nobutaka Shimizu

Other Decks in Research

Transcript

  1. /28 3 )JUUJOH5JNFBOE$PWFS5JNF w )PXGBTUEPFTB38TQSFBET  w IJUUJOHUJNF  

    w DPWFSUJNF  w .BOZQSFWJPVTXPSLTTUVEZJOH38POTUBUJDHSBQIT thit max u,v E[38IJUTvTUBSUJOHGSPNV] tcov = max u E[38WJTJUTBMMWFSUJDFTTUBSUJOHGSPNu] [Aleliunas, Karp, Lipton, Lovász, Rackoff, 1979] [Feige, 1995] [Feige, 1995] [Matthews, 1988]
  2. /28 5 38PO%ZOBNJD(SBQIT ɾ TFRVFODF PGHSBQITTU  ɾ*GBMM BSF SFHVMBS

      ɾ38POSFDVSSJOHGBNJMZ TQFDJ fi DUZQFPG  ɾ"MM BSFSBOEPNHSBQI ∃ (Gt ) tcov = 2Ω(n) Gt d thit = O(n2) Gt Gt [Avin, Kousky, Lotler, 2008] [Sauerwald, Zanetti, 2019] [Oksana and Luís, 2014] [Cai, Sauerwald, Zanetti, 2020] Most previous works consider the case of a static vertex set (i.e., for all ) V(Gt ) = V t Consider RW on a sequence of graphs. G0 , G1 , …
  3. /28 7 0VS'SBNFXPSL ɾ8FGPDVTPONPEFSBUFMZHSPXJOHHSBQIT ɾLet be a function (duration ɾLet

    be graphs s.t. ɾ is obtained by adding a vertex and edges to . 𝔡 : ℕ → ℕ (G(i))i∈ℕ V(G(i)) = {v1 , …, vi } G(i+1) G(i) 7 ɾ PGVOWJTJUFEWFSUJDFTBGUFS38PO 5IFO  U = Un = Gn E[U] = ? SPVOE ɾ'PSFBDI QFSGPSN38PGMFOHUI POFBDI  i 𝔡 (i) G(i) *OUIJTTFUUJOH XFDBOBQQMZBOBMZTJTUFDIOJRVFTPG38
  4. /28 3FMBUFE8PSL w .PTUQSFWJPVTXPSLTTUVEJFEB38POBTUBUJDWFSUFYTFU 9 [Avin, Kousky, Lotler, 2008] [Sauerwald,

    Zanetti, 2019] [Oksana and Luís, 2014] [Cai, Sauerwald, Zanetti, 2020] ɾ5IFPOMZFYDFQUJPOJT[Cooper, Frieze, 2002] XIPDPOTJEFSFE38POHSPXJOH QSFGFSFOUJBMBUUBDINFOUNPEFMXJUIDPOTUBOU 5IFZQSPWFEUIBU  BT 𝔡 (i) E[U]/n → const n → ∞
  5. /28 10 0CTFSWBUJPOT ɾ*G UIFO UIF38WJTJUTBMMWFSUJDFTBUFBDISPVOE 𝔡 (i) ≫ tcov

    (G(i)) 10 ɾ4VQQPTF GPSBMM 5IFO 𝔡 (i) ≥ (1 + ϵ)thit (G(i)) i E[U] = n ∑ i=1 Pr[vi JTVOWJTJUFE] = O(1) . Pr[vi JTVOWJTJUFE] = Pr ⋀ j≥i {vi JTVOWJTJUFEBUjUISPVOE} UIBSSJWBMWFSUFY JF  i V(Gi )∖V(Gi−1 ) ≤ (1 + ϵ)−(n−i+1) 5IFSFGPSF ɾ)PXBCPVU  𝔡 (i) ≪ thit (G(i))
  6. /28 11 3FTVMUT 11 Theorem 1 Consider a lazy and

    reversible RW on a moderately growing graph. If , then . 𝔡 (i) ≥ 3Cthit (G(i)) N + 2tmix (G(i)) E[U] ≤ 8N + 32 ɾ3FTVMUGPSHSBQITXJUI  FH FYQBOEFSHSBQIT thit (G(i)) ≫ tmix (G(i)) ɾ8FDBOOPUBQQMZ5IFPSFNJG  FH QBUI thit (G(i)) ≈ tmix (G(i)) ɾ"UFBDISPVOE 38NJYFTFOPVHITJODF 𝔡 (i) ≥ 2tmix (G(i))
  7. /28 12 3FTVMUT 12 Theorem 2 (informal) Consider a lazy

    simple RW on a growing graph. Suppose that and Then, . |E(G(i))| |E(G(i−1))| ≤ 1 + O(i−1) 𝔡 (i) ≥ Ω ( thit (Gi ) iγ ) E[U] = O(nγ) ɾ8FDBOBQQMZ5IFPSFNJGUIFFEHFTNPEFSBUFMZJODSFBTF FH QBUI
  8. /28 13 &YBNQMF 13 5IFSFJTBDPOTU TVDIUIBU GPSBOZ C > 0

    γ ∈ [0,1] 0OBHSPXJOHDPNQMFUFHSBQI  ɾ  ɾ 𝔡 (i) ≥ Ci1−γ ⇒ E[U] = O(nγ) 𝔡 (i) ≤ Ci1−γ ⇒ E[U] = Ω(nγ) 0OBHSPXJOHQBUI ɾ  ɾ 𝔡 (i) ≥ Ci2−γ ⇒ E[U] = O(nγ) 𝔡 (i) ≤ Ci2−γ ⇒ E[U] = Ω(nγ) ˎ-PXFSCPVOETBSFTIPXOCZBOBEIPDXBZ
  9. /28 14 *EFBPG1SPPG 14  "TBXBSNVQ DPOTJEFSBHSPXJOHDPNQMFUFHSBQI  8FFYUFOEUIFBSHVNFOUUPUIFHFOFSBMDBTF Theorem

    2 (reminder) Consider a lazy simple RW on a growing graph. Suppose that and Then, . |E(G(i))| |E(G(i−1))| ≤ 1 + O(i−1) 𝔡 (i) ≥ Ω ( thit (Gi ) iγ ) E[U] = O(nγ)
  10. /28 15 8BSN6Q$PNQMFUF(SBQI 15 ɾ4VQQPTF IBTBTFMGMPPQPOFBDIWFSUFY G(i) = Ki 38WJTJU

    XQ v ∈ V(G(i)) 1/i ɾPr[vJTVOWJTJUFEEVSJOHSPVOEi] = (1 − 1 i ) (i) Pr[vi JTVOWJTJUFEBMMUIFUJNF] = n ∏ j=i (1 − 1 j ) (j) E[U] = n ∑ i=1 n ∏ j=i (1 − 1 j ) 𝔡 (j)
  11. /28 16 8BSN6Q$PNQMFUF(SBQI 16 ɾ6QQFSCPVOE 𝔡 (i) ≥ Ci1−γ ⇒

    E[U] = O(nγ) &WBMVBUFE[U] = n ∑ i=1 n ∏ j=i (1 − 1 j ) 𝔡 (j) n ∏ j=i (1 − 1 j ) 𝔡 (i) ≤ exp − n ∑ j=i C jγ ≤ exp (−(n − i + 1) C nγ ) . E[U] ≤ n ∑ i=1 exp (−(n − i + 1) C nγ ) = O(nγ) . )FODF □
  12. /28 17 8BSN6Q$PNQMFUF(SBQI 17 ɾ-PXFSCPVOE 𝔡 (i) ≤ Ci1−γ ⇒

    E[U] = Ω(nγ) &WBMVBUFE[U] = n ∑ i=1 n ∏ j=i (1 − 1 j ) 𝔡 (j) n ∏ j=i (1 − 1 j ) 𝔡 (i) ≥ n ∏ j=i (1 − 1 j ) Cn1−γ = ( i − 1 n ) Cn1−γ . E[U] ≥ n ∑ i=1 ( i − 1 n ) Cn1−γ = Ω(nγ) )FODF □
  13. /28 18 &YUFOEUP(FOFSBM(SBQI 18 E[U] = n ∑ i=1 n

    ∏ j=i (1 − 1 j ) 𝔡 (j) 0O GPSBOZ BOE  Ki u, v ∈ V(Ki ) t Pr[τu,v > t] = (1 − 1 i ) t ˎ UJNFGPS38UPWJTJU TUBSUJOHGSPN τu,v v u
  14. /28 19 &YUFOEUP(FOFSBM(SBQI 19 E[U] = n ∑ i=1 n

    ∏ j=i (1 − 1 j ) 𝔡 (j) 0O GPSBOZ BOE  Ki u, v ∈ V(Ki ) t Pr[τu,v > t] = (1 − 1 i ) t ˎ UJNFGPS38UPWJTJU TUBSUJOHGSPN τu,v v u ˎ-B[Z JSSFEVDJCMF BOEMB[Z38 ˎ JTUIFTUBUJPOBSZEJTU π ∈ [0,1]V [Aldous, Fill, 2002], [Oliveira, Peres, 2019] HFOFSBMJ[F 'PSBOZ BOE  v ∈ V(G) t Pr u∼π [τu,v > t] ≤ ( 1 − 1 thit ) t
  15. /28 20 &YUFOEUP(FOFSBM(SBQI 20 E[U] = n ∑ i=1 n

    ∏ j=i (1 − 1 j ) 𝔡 (j) 0O GPSBOZ BOE  Ki u, v ∈ V(Ki ) t Pr[τu,v > t] = (1 − 1 i ) t ˎ UJNFGPS38UPWJTJU TUBSUJOHGSPN τu,v v u ˎ-B[Z JSSFEVDJCMF BOEMB[Z38 ˎ JTUIFTUBUJPOBSZEJTU π ∈ [0,1]V [Aldous, Fill, 2002], [Oliveira, Peres, 2019] E[U] ≤ n ∑ i=1 n ∏ j=i ( 1 − 1 thit (G(j))) 𝔡 (j) 🤔 HFOFSBMJ[F 'PSBOZ BOE  v ∈ V(G) t Pr u∼π [τu,v > t] ≤ ( 1 − 1 thit ) t
  16. /28 E[U] ≤ n ∑ i=1 n ∏ j=i (

    1 − 1 thit (G(j))) 𝔡 (j) 21 &YUFOEUP(FOFSBM(SBQI 21 E[U] = n ∑ i=1 n ∏ j=i (1 − 1 j ) 𝔡 (j) 0O GPSBOZ BOE  Ki u, v ∈ V(Ki ) t Pr[τu,v > t] = (1 − 1 i ) t ˎ UJNFGPS38UPWJTJU TUBSUJOHGSPN τu,v v u ˎ-B[Z JSSFEVDJCMF BOEMB[Z38 ˎ JTUIFTUBUJPOBSZEJTU π ∈ [0,1]V [Aldous, Fill, 2002], [Oliveira, Peres, 2019] 😓 HFOFSBMJ[F 'PSBOZ BOE  v ∈ V(G) t Pr u∼π [τu,v > t] ≤ ( 1 − 1 thit ) t 0VSHSBQIJTEZOBNJD DIBOHFTPWFSUJNF π
  17. /28 22 &YUFOEUP(FOFSBM(SBQI 22 E[U] ≤ n ∑ i=1 n

    ∏ j=i ( 1 − 1 thit (G(j))) 𝔡 (j) Lemma E[U] ≤ O(1) ⋅ n ∑ i=1 n ∏ j=i max v∈V(G(j)) π(j−1)(v) π(j)(v) ( 1 − 1 thit (G(j))) (j) JTTUBUJPOBSZEJTUPG π(j) G(j) *G DIBOHFTNPEFSBUFMZ UIFOXFDBOFWBMVBUF  π(i) E[U] 😓 😄
  18. /28 23 1SPPG4LFUDI 23  Pr[vi JTVOWJTJUFE] ≈ ∏ j≥i

    SBUJPCFUXFFO BOE   Xt π(j) × Pr u∼π [τu,v > t] *G  UIJTUFSN  𝔡 (j) ≥ tmix (G(j)) ≈ 1 [Aldous, Fill, 2002], [Oliveira, Peres, 2019] 'PSBOZ BOE  v ∈ V(G) t Pr u∼π [τu,v > t] ≤ ( 1 − 1 thit ) t ˎ DBOCFNVDIMFTTUIBOUIFNJYJOHUJNF😓 𝔡 (j) ˎ JTTUBUJPOBSZEJTUPG π(j) G(j)
  19. /28 24 #FIBWJPSPG38 24 0OBTUBUJDHSBQI  EJTUSJCVUJPOPG38 → π π

    [0,1]V EJTUPGXt t → ∞ 0OBEZOBNJDHSBQI  DIBOHFTPWFSUJNF π π(i) EJTUPGXt t → ∞ π(i+1)
  20. /28 25 #FIBWJPSPG38 25 0OBTUBUJDHSBQI  EJTUSJCVUJPOPG38 → π π

    [0,1]V EJTUPGXt t → ∞ 0OBEZOBNJDHSBQI  DIBOHFTPWFSUJNF π π(i) EJTUPGXt t → ∞ π(i+1) *G DIBOHFTNPEFSBUFMZ  XFDBOCPVOEUIFEJTUBODF π
  21. /28 26 &YUFOEUP(FOFSBM(SBQI 26 Lemma E[U] ≤ O(1) ⋅ n

    ∑ i=1 n ∏ j=i max v∈V(G(j)) π(j−1)(v) π(j)(v) ( 1 − 1 thit (G(j))) (j) JTTUBUJPOBSZEJTUPG π(j) G(j) *G DIBOHFTNPEFSBUFMZ UIFOXFDBOFWBMVBUF  π(i) E[U]
  22. /28 27 1SPPGWJB-FNNB 27 'SPNBTTVNQUJPO Theorem 2 (reminder) Consider a

    lazy simple RW on a growing graph. Suppose that and . Then, . |E(G(i))| |E(G(i−1))| ≤ 1 + O(i−1) 𝔡 (i) ≥ Ω ( thit (Gi ) iγ ) E[U] = O(nγ) π(i−1)(v) π(i)(v) = deg(i−1)(v) 2|E(G(i−1))| ⋅ 2|E(G(i))| deg(i)(v) ≤ |E(G(i))| |E(G(i−1) | ≤ 1 + O(i−1) 5IFO max v∈V(G(j)) π(j−1)(v) π(j)(v) ( 1 − 1 thit (G(j))) 𝔡 (j) ≤ ( 1 − 1 thit (G(j))) (j)−O( thit(G(j)) j ) ≈ ( 1 − 1 thit (G(j))) (j) )FODF E[U] ≤ O(1) ⋅ n ∑ i=1 n ∏ j=i ( 1 − 1 thit (G(j))) 𝔡 (j)
  23. /28 28 $PODMVTJPO 28 ɾ8FJOUSPEVDF38POHSPXJOHHSBQIT ɾ"OBMZTJTJTUSBDUBCMF*G DIBOHFTNPEFSBUFMZ π ɾ$BOXFBQQMZUFDIOJRVFTPGQSFWJPVTXPSLTUPUIFHSPXJOHTFUUJOH 'VUVSF%JSFDUJPO

    ɾ)JUUJOHUJNF NJYJOHUJNF FUDPOHSPXJOHHSBQIT [Avin, Kousky, Lotler, 2008] [Sauerwald, Zanetti, 2019] [Oksana and Luís, 2014] [Cai, Sauerwald, Zanetti, 2020]