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

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

Avatar for Nobutaka Shimizu Nobutaka Shimizu
July 05, 2022
Research
0
110

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

slide at SODA2021
Avatar for Nobutaka Shimizu

Nobutaka Shimizu

July 05, 2022
Tweet

More Decks by Nobutaka Shimizu

See All by Nobutaka Shimizu
Planted Clique Conjectures are Equivalent
Avatar for Nobutaka Shimizu nobushimi
0
140
理論計算機科学における 数学の応用: 擬似ランダムネス
Avatar for Nobutaka Shimizu nobushimi
1
420
Hardness Self-Amplification: Simplified, Optimized, and Unified
Avatar for Nobutaka Shimizu nobushimi
0
260
Hardness Self-Amplification from Feasible Hard-Core Sets
Avatar for Nobutaka Shimizu nobushimi
0
190
Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH
Avatar for Nobutaka Shimizu nobushimi
0
130
Quasi-majority Functional Voting on Expander Graphs
Avatar for Nobutaka Shimizu nobushimi
0
60
Phase Transitions of Best-of-Two and Best-of-Three on Stochastic Block Models
Avatar for Nobutaka Shimizu nobushimi
0
110

Other Decks in Research

See All in Research
Batch Processing Algorithm for Elliptic Curve Operations and Its AVX-512 Implementation
Avatar for herumi herumi
0
150
3D Gaussian Splattingによる高効率な新規視点合成技術とその応用
Avatar for Hide Matsuki muskie82
0
560
[輪講] Transformer Layers as Painters
Avatar for Naoki Kato nk35jk
4
760
Intrinsic Self-Supervision for Data Quality Audits
Avatar for Fabian Gröger fabiangroeger
0
500
SatCLIP: Global, General-Purpose Location Embeddings with Satellite Imagery
Avatar for SatAI.challenge satai
3
130
RapidPen: AIエージェントによるペネトレーションテスト 初期侵入全自動化の研究
Avatar for Sho Nakatani laysakura
0
410
90 分で学ぶ P 対 NP 問題
Avatar for E869120 e869120
15
6.8k
Self-supervised audiovisual representation learning for remote sensing data
Avatar for SatAI.challenge satai
3
130
TRIPOD+AI Expandedチェックリスト 有志翻訳による日本語版 version.1.1
Avatar for Shuntaro Sato shuntaros
0
130
LLM-as-a-Judge: 文章をLLMで評価する@教育機関DXシンポ
Avatar for Kouta Nakayama k141303
3
710
Vision Language Modelと完全自動運転AIの最新動向
Avatar for Tsubasa Takahashi tsubasashi
2
420
Security, Privacy, and Trust in Generative AI
Avatar for Tsubasa Takahashi tsubasashi
0
110

Featured

See All Featured
Stop Working from a Prison Cell
Avatar for Chris Michel hatefulcrawdad
268
20k
It's Worth the Effort
Avatar for 3n 3n
184
28k
Fontdeck: Realign not Redesign
Avatar for Paul Robert Lloyd paulrobertlloyd
84
5.5k
Chrome DevTools: State of the Union 2024 - Debugging React & Beyond
Avatar for Addy Osmani addyosmani
5
590
How STYLIGHT went responsive
Avatar for nonsquared nonsquared
100
5.5k
Building Better People: How to give real-time feedback that sticks.
Avatar for Will Jessup wjessup
367
19k
Git: the NoSQL Database
Avatar for Brandon Keepers bkeepers
PRO
430
65k
A better future with KSS
Avatar for Kyle Neath kneath
239
17k
RailsConf 2023
Avatar for Aaron Patterson tenderlove
30
1.1k
Templates, Plugins, & Blocks: Oh My! Creating the theme that thinks of everything
Avatar for Michelle Schulp Hunt marktimemedia
30
2.3k
Save Time (by Creating Custom Rails Generators)
Avatar for Garrett Dimon garrettdimon
PRO
31
1.2k
XXLCSS - How to scale CSS and keep your sanity
Avatar for Zaharenia Atzitzikaki sugarenia
248
1.3M

Transcript

  1. )PXNBOZWFSUJDFTEPFTBSBOEPN XBMLNJTTJOBOFUXPSLXJUINPEFSBUFMZ JODSFBTJOHUIFOVNCFSPGWFSUJDFT 4IVKJ,JKJNB/PCVUBLB4IJNJ[V5BLFIBSV4IJSBHB ,ZVTIV6OJWFSTJUZ 5IF6OJWFSTJUZPG5PLZP $IVP6OJWFSTJUZ

  2. /28 2 3BOEPN8BML w #BTJD.BSLPWDIBJOPOBHSBQI w TJNQMFBOEMPXNFNPSZˠBQQMJDBUJPOJOOFUXPSLBOBMZTJT FH 1BHF3BOL .$.$

    DMVTUFSJOH FUD

  3. /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]

  4. /28 4 38PO%ZOBNJD(SBQIT 3FBMXPSMEOFUXPSLTDIBOHFUIFJSTUSVDUVSFPWFSUJNF FH 888 TPDJBMOFUXPSL DIFNJDBMOFUXPSL ʜ [Yu,

    McCann, 2016] 8FDBOBOBMZ[FEZOBNJDOFUXPSLTVTJOH38

  5. /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 , …

  6. /28 6 5IJT8PSL ɾ8FDPOTJEFS38POBHSPXJOHHSBQI G1 G2 G3 G4 Gn 6

  7. /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

  8. /28 8 4JNVMBUJPO7JEFP 8 (SPXJOHDPNQMFUFHSBQI (SPXJOHQBUI

  9. /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 → ∞

  10. /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))

  11. /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))

  12. /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

  13. /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

  14. /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γ)

  15. /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)

  16. /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 □

  17. /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 □

  18. /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

  19. /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

  20. /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

  21. /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 π

  22. /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] 😓 😄

  23. /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)

  24. /28 24 #FIBWJPSPG38 24 0OBTUBUJDHSBQI  EJTUSJCVUJPOPG38 → π π

    [0,1]V EJTUPGXt t → ∞ 0OBEZOBNJDHSBQI  DIBOHFTPWFSUJNF π π(i) EJTUPGXt t → ∞ π(i+1)

  25. /28 25 #FIBWJPSPG38 25 0OBTUBUJDHSBQI  EJTUSJCVUJPOPG38 → π π

    [0,1]V EJTUPGXt t → ∞ 0OBEZOBNJDHSBQI  DIBOHFTPWFSUJNF π π(i) EJTUPGXt t → ∞ π(i+1) *G DIBOHFTNPEFSBUFMZ  XFDBOCPVOEUIFEJTUBODF π

  26. /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]

  27. /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)

  28. /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]