Multitarget search on complex networks: A logarithmic growth of global mean random cover time

Tongfeng Weng; Ji Yang; Bijarbooneh, Farshid Hassani; Pan Hui; Jie Zhang; Small, Michael
September 2017
Chaos;2017, Vol. 27 Issue 9, p1
Academic Journal
We investigate multitarget search on complex networks and derive an exact expression for the mean random cover time that quantifies the expected time a walker needs to visit multiple targets. Based on this, we recover and extend some interesting results of multitarget search on networks. Specifically, we observe the logarithmic increase of the global mean random cover time with the target number for a broad range of random search processes, including generic random walks, biased random walks, and maximal entropy random walks. We show that the logarithmic growth pattern is a universal feature of multi-target search on networks by using the annealed network approach and the Sherman-Morrison formula. Moreover, we find that for biased random walks, the global mean random cover time can be minimized, and that the corresponding optimal parameter also minimizes the global mean first passage time, pointing towards its robustness. Our findings further confirm that the logarithmic growth pattern is a universal law governing multitarget search in confined media.


Related Articles

  • Fleming-Viot processes: two explicit examples. Cloez, Bertrand; Thai, Marie-Noémie // ALEA. Latin American Journal of Probability & Mathematical Stati;2016, Vol. 13, p337 

    The purpose of this paper is to extend the investigation of the Fleming- Viot process in discrete space started in a previous work to two specific examples. The first one corresponds to a random walk on the complete graph. Due to its geometry, we establish several explicit and optimal formulas...

  • Occupation time Markov property for countable Markov chains with respect to several states. Vorotov, A. A. // Vestnik Sankt-Peterburgskogo universiteta, Seriia 7: Geologia, G;2013, Issue 4, p30 

    No abstract available.

  • Occupation time Markov property for countable Markov chains with respect to several states. Vorotov, A. A. // Vestnik Sankt-Peterburgskogo universiteta, Seriia 7: Geologia, G;2013, Issue 4, p160 

    No abstract available.

  • Random walks on free products of cyclic groups. Mairesse, Jean; Mathéus, Frédéric // Journal of the London Mathematical Society;2007, Vol. 75 Issue 1, p47 

    Let G be a free product of a finite family of finite groups, with the set of generators being formed by the union of the finite groups. We consider a transient nearest-neighbour random walk on G. We give a new proof of the fact that the harmonic measure is a special Markovian measure entirely...

  • Entropy-Driven Cutoff Phenomena. Lancia, Carlo; Nardi, Francesca; Scoppola, Benedetto // Journal of Statistical Physics;Oct2012, Vol. 149 Issue 1, p108 

    In this paper we present, in the context of Diaconis' paradigm, a general method to detect the cutoff phenomenon. We use this method to prove cutoff in a variety of models, some already known and others not yet appeared in literature, including a non-reversible random walk on a cylindrical...

  • A random environment for linearly edge-reinforced random walks on infinite graphs. Merkl, Franz; Rolles, Silke W. W. // Probability Theory & Related Fields;May2007, Vol. 138 Issue 1/2, p157 

    We consider linearly edge-reinforced random walk on an arbitrary locally finite connected graph. It is shown that the process has the same distribution as a mixture of reversible Markov chains, determined by time-independent strictly positive weights on the edges. Furthermore, we prove bounds...

  • Total progeny in killed branching random walk. Addario-Berry, L.; Broutin, N. // Probability Theory & Related Fields;Jul2011, Vol. 151 Issue 1/2, p265 

    We consider a branching random walk for which the maximum position of a particle in the n'th generation, R, has zero speed on the linear scale: R/ n → 0 as n → ∞. We further remove ('kill') any particle whose displacement is negative, together with its entire descendence. The...

  • Infinite volume limit of the Abelian sandpile model in dimensions d ≥ 3. Járai, Antal A.; Redig, Frank // Probability Theory & Related Fields;May2008, Vol. 141 Issue 1/2, p181 

    We study the Abelian sandpile model on $${\mathbb{Z}}^{d}$$ . In d ≥ 3 we prove existence of the infinite volume addition operator, almost surely with respect to the infinite volume limit μ of the uniform measures on recurrent configurations. We prove the existence of a Markov process...

  • Random walks systems on complete graphs. Alves, Oswaldo S. M.; Lebensztayn, Elcio; Machado, Fábio; Martinez, Mauricio // Bulletin of the Brazilian Mathematical Society;Dec2006, Vol. 37 Issue 4, p571 

    We study two versions of random walks systems on complete graphs. In the first one, the random walks have geometrically distributed lifetimes so we define and identify a non-trivial critical parameter related to the proportion of visited vertices before the process dies out. In the second...

  • COVER TIMES AND GENERIC CHAINING. LEHEC, JOSEPH // Journal of Applied Probability;Mar2014, Vol. 51 Issue 1, p247 

    A recent result of Ding, Lee and Peres (2012) expressed the cover time of the random walk on a graph in terms of generic chaining for the commute distance. Their argument is based on Dynkin's isomorphism theorem. The purpose of this article is to present an alternative approach to this problem,...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics