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

References

• [1] Aldous DJ (1983) On the time taken by random walks on finite groups to visit every state. Z. Wahrscheinlichkeitstheorie Verw. Gebiete 62:361–374.Crossref, Google Scholar
• [2] Aldous DJ, Fill JA (2002) Reversible Markov chains and random walks on graphs, https://www.stat.berkeley.edu/users/aldous/RWG/book.html.Google Scholar
• [3] Aleliunas R, Karp RM, Lipton RJ, Lovász L, Rackoff C (1979) Random walks, universal traversal sequences, and the complexity of maze problems. Proc. 20th Annual Sympos. Foundations Comput. Sci. (FOCS) (IEEE, New York), 218–223.Google Scholar
• [4] Augustine J, Pandurangan G, Robinson P (2016) Distributed algorithmic foundations of dynamic networks. ACM SIGACT News 47(1):69–98.Crossref, Google Scholar
• [5] Avin C, Koucký M, Lotker Z (2008) How to explore a fast-changing world (cover time of a simple random walk on evolving graphs). Aceto L, Damgård I, Goldberg LA, Halldórsson MM, Ingólfsdóttir A, Walukiewicz I, eds. Proc. 35th Internat. Colloquium Automata Languages Programming (ICALP) (Springer, Berlin), 121–132.Google Scholar
• [6] Avin C, Koucký M, Lotker Z (2018) Cover time and mixing time of random walks on dynamic graphs. Random Structures Algorithms 52(4):576–596.Crossref, Google Scholar
• [7] Barabási AL, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509–512.Crossref, Google Scholar
• [8] Berenbrink P, Giakkoupis G, Kermarrec AM, Mallmann-Trenn F (2016) Bounds on the voter model in dynamic networks. Chatzigiannakis I, Mitzenmacher M, Rabani Y, Sangiorgi D, eds. Proc 43rd Internat. Colloquium Automata Languages Programming (ICALP) (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 146:1–146:15.Google Scholar
• [9] Cai L, Sauerwald T, Zanetti L (2020) Random walks on randomly evolving graphs. Richa AW, Scheideler C, eds. Proc. 27th Internat. Colloquium Structural Inform. Comm. Complexity (SIROCCO) (Springer-Verlag, Berlin), 111–128.Google Scholar
• [10] Clementi A, Silvestri R, Trevisan L (2015) Information spreading in dynamic graphs. Distributed Comput. 28:55–73.Crossref, Google Scholar
• [11] Cooper C (2011) Random walks, interacting particles, dynamic networks: Randomness can be helpful. Kosowski A, Yamashita M, eds. Proc. 18th Internat. Colloquium Structural Inform. Comm. Complexity (SIROCCO) (Springer, Berlin), 1–14.Google Scholar
• [12] Cooper C, Frieze A (2004) Crawling on simple models of web graphs. Internet Math. 1(1):57–90.Crossref, Google Scholar
• [13] David R, Feige U (2017) Random walks with the minimum degree local rule have O(N2) cover time. Proc. 28th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 1839–1848.Google Scholar
• [14] David R, Feige U (2018) Random walks with the minimum degree local rule have O(n2) cover time. SIAM J. Comput. 47(3):755–768.Crossref, Google Scholar
• [15] Denysyuk O, Rodrigues L (2014) Random walks on evolving graphs with recurring topologies. Kuhn F, ed. Distributed Comput. DISC 2014 (Springer, Berlin), 333–345.Google Scholar
• [16] Doerr B, Neumann F, eds. (2020) Theory of Evolutionary Computation: Recent Developments in Discrete Optimization (Springer International Publishing, Cham, Switzerland).Crossref, Google Scholar
• [17] Doyle PG, Snell JL (1984) Random Walks and Electric Networks (Mathematical Association of America, Washington, DC).Crossref, Google Scholar
• [18] Durrett R (2019) Probability: Theory and Examples (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [19] Feige U (1995) A tight lower bound on the cover time for random walks on graphs. Random Structures Algorithms 6(4):433–438.Crossref, Google Scholar
• [20] Feige U (1995) A tight upper bound on the cover time for random walks on graphs. Random Structures Algorithms 6(1):51–54.Crossref, Google Scholar
• [21] Ikeda S, Kubo I, Yamashita M (2009) The hitting and cover times of random walks on finite graphs using local degree information. Theoret. Comput. Sci. 410(1):94–100.Crossref, Google Scholar
• [22] Ikeda S, Kubo I, Okumoto N, Yamashita M (2003) Impact of local topological information on random walks on finite graphs. Baeten JCM, Lenstra JK, Parrow J, Woeginger GJ, eds. Proc. 30th Internat. Colloquium Automata Languages Programming (ICALP) (Springer, Berlin), 1054–1067.Google Scholar
• [23] Kanade V, Mallmann-Trenn F, Sauerwald T (2019) On coalescence time in graphs: When is coalescing as fast as meeting? Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 956–965.Google Scholar
• [24] Kijima S, Shimizu N, Shiraga T (2021) How many vertices does a random walk miss in a network with moderately increasing the number of vertices? Proc. 32nd Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 106–122.Google Scholar
• [25] Kuhn F, Oshman R (2011) Dynamic networks: Models and algorithms. SIGACT News 42(1):82–96.Crossref, Google Scholar
• [26] Lamprou I, Martin R, Spirakis P (2018) Cover time in edge-uniform stochastically-evolving graphs. Algorithms 11(10):149.Crossref, Google Scholar
• [27] Levin DA, Peres Y (2017) Markov Chain and Mixing Times, 2nd ed. (The American Mathematical Society, Providence, RI).Crossref, Google Scholar
• [28] Matthews P (1988) Covering problems for Markov chains. Ann. Probab. 16(3):1215–1228.Crossref, Google Scholar
• [29] Michail O (2016) An introduction to temporal graphs: An algorithmic perspective. Internet Math. 12(4):239–280.Crossref, Google Scholar
• [30] Michail O, Spirakis PG (2018) Elements of the theory of dynamic networks. Comm. ACM 61(2):72–81.Crossref, Google Scholar
• [31] Mihail M, Papadimitriou C, Saberi A (2006) On certain connectivity properties of the internet topology. J. Comput. System Sci. 72(2):239–251.Crossref, Google Scholar
• [32] Nonaka Y, Ono H, Sadakane K, Yamashita M (2010) The hitting and cover times of metropolis walks. Theoret. Comput. Sci. 411(16–18):1889–1894.Crossref, Google Scholar
• [33] Oliveira RI, Peres Y (2019) Random walks on graphs: New bounds on hitting, meeting, coalescing and returning. Proc. 16th Workshop Anal. Algorithmics Combinatorics (ANALCO), 119–126.Google Scholar
• [34] Saloff-Coste L, Zúñiga J (2009) Merging for time inhomogeneous finite Markov chains. Part I: Singular values and stability. Electronic J. Probab. 14(49):1456–1494.Google Scholar
• [35] Saloff-Coste L, Zúñiga J (2011) Merging for inhomogeneous finite Markov chains. Part II: Nash and log-Sobolev inequalities. Ann. Probab. 39(3):1161–1203.Crossref, Google Scholar
• [36] Sarma AD, Molla AR, Pandurangan G (2015) Distributed computation in dynamic networks via random walks. Theoret. Comput. Sci. 581:45–66.Crossref, Google Scholar
• [37] Sauerwald T, Zanetti L (2019) Random walks on dynamic graphs: Mixing times, hitting times, and return probabilities. Baier C, Chatzigiannakis I, Flocchini P, Leonardi S, eds. Proc. 46th Internat. Colloquium Automata Languages Programming (ICALP) (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 93:1–93:15.Google Scholar
• [38] Watts DJ, Strogatz SH (1998) Collective dynamics of ‘small-world’ networks. Nature 393:440–442.Crossref, Google Scholar
• [39] Yu W, McCann JA (2016) Random walk with restart over dynamic graphs. Proc. IEEE 16th Internat. Conf. Data Mining (ICDM) (IEEE, New York), 589–598.Google Scholar