1
|
Méndez V, Flaquer-Galmés R, Campos D. First-passage time of a Brownian searcher with stochastic resetting to random positions. Phys Rev E 2024; 109:044134. [PMID: 38755900 DOI: 10.1103/physreve.109.044134] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/04/2024] [Accepted: 03/22/2024] [Indexed: 05/18/2024]
Abstract
We study the effect of a resetting point randomly distributed around the origin on the mean first-passage time of a Brownian searcher moving in one dimension. We compare the search efficiency with that corresponding to reset to the origin and find that the mean first-passage time of the latter can be larger or smaller than the distributed case, depending on whether the resetting points are symmetrically or asymmetrically distributed. In particular, we prove the existence of an optimal reset rate that minimizes the mean first-passage time for distributed resetting to a finite interval if the target is located outside this interval. When the target position belongs to the resetting interval or it is infinite then no optimal reset rate exists, but there is an optimal resetting interval width or resetting characteristic scale which minimizes the mean first-passage time. We also show that the first-passage density averaged over the resetting points depends on its first moment only. As a consequence, there is an equivalent point such that the first-passage problem with resetting to that point is statistically equivalent to the case of distributed resetting. We end our study by analyzing the fluctuations of the first-passage times for these cases. All our analytical results are verified through numerical simulations.
Collapse
Affiliation(s)
- V Méndez
- Grup de Física Estadística, Departament de Física. Facultat de Ciències, Universitat Autònoma de Barcelona, 08193 Barcelona, Spain
| | - R Flaquer-Galmés
- Grup de Física Estadística, Departament de Física. Facultat de Ciències, Universitat Autònoma de Barcelona, 08193 Barcelona, Spain
| | - D Campos
- Grup de Física Estadística, Departament de Física. Facultat de Ciències, Universitat Autònoma de Barcelona, 08193 Barcelona, Spain
| |
Collapse
|
2
|
Julián-Salgado P, Dagdug L, Boyer D. Diffusion with two resetting points. Phys Rev E 2024; 109:024134. [PMID: 38491676 DOI: 10.1103/physreve.109.024134] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/17/2023] [Accepted: 02/02/2024] [Indexed: 03/18/2024]
Abstract
We study the problem of a target search by a Brownian particle subject to stochastic resetting to a pair of sites. The mean search time is minimized by an optimal resetting rate which does not vary smoothly, in contrast with the well-known single site case, but exhibits a discontinuous transition as the position of one resetting site is varied while keeping the initial position of the particle fixed, or vice versa. The discontinuity vanishes at a "liquid-gas" critical point in position space. This critical point exists provided that the relative weight m of the further site is comprised in the interval [2.9028...,8.5603...]. When the initial position is a random variable that follows the resetting point distribution, a discontinuous transition also exists for the optimal rate as the distance between the resetting points is varied, provided that m exceeds the critical value m_{c}=6.6008.... This setup can be mapped onto an intermittent search problem with switching diffusion coefficients and represents a minimal model for the study of distributed resetting.
Collapse
Affiliation(s)
- Pedro Julián-Salgado
- Basic Sciences and Engineering, Universidad Autónoma Metropolitana, Apartado Postal 55-534, Mexico City 09340, Mexico
| | - Leonardo Dagdug
- Basic Sciences and Engineering, Universidad Autónoma Metropolitana, Apartado Postal 55-534, Mexico City 09340, Mexico
| | - Denis Boyer
- Instituto de Física, Universidad Nacional Autónoma de México, Mexico City 04510, Mexico
| |
Collapse
|
3
|
Chen Y, Yuan Z, Gao L, Peng J. Optimizing search processes with stochastic resetting on the pseudofractal scale-free web. Phys Rev E 2023; 108:064109. [PMID: 38243504 DOI: 10.1103/physreve.108.064109] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/04/2023] [Accepted: 11/15/2023] [Indexed: 01/21/2024]
Abstract
The pseudofractal scale-free web (PSFW) is a well-known model for a scale-free network with small-world characteristics. Understanding the dynamic properties of this network can provide valuable insights into dynamic processes occurring in general scale-free and small-world networks. In this study we investigate search processes using discrete-time random walks on the PSFW to reveal the impact of the resetting position on optimizing search efficiency, as measured by the mean first-passage time (MFPT). At each step the walker has two options: with a probability of 1-γ, it moves to one of the neighboring sites, and with a probability of γ, it resets to the predefined resetting position. We explore various choices for the resetting position, present rigorous results for the MFPT to a given node of the network, determine the optimal resetting probability γ^{*} where the MFPT reaches its minimum, and evaluate the ratio of the minimum for MFPT to the MFPT without resetting for each case. Results show that, in large PSFWs, both the degree of the resetting position and the distance between the target and the resetting position significantly affect the search efficiency. A higher degree of the resetting position leads to a slower convergence of the walker to the target, while a greater distance between the target and the resetting position also results in a slower convergence. Additionally, we observe that resetting to a vertex randomly selected from the stationary distribution can significantly expedite the process of the walker reaching the target. The findings presented in this study shed light on optimizing stochastic search processes on large networks, offering valuable insights into improving search efficiency in real-world applications, where the target node's location is unknown.
Collapse
Affiliation(s)
- Yongjin Chen
- School of Mathematics and Information Science, Guangzhou University, Guangzhou 510006, China; Guangdong Provincial Key Laboratory of Information Security Technology, Guangzhou University, Guangzhou 510006, China; and Guangzhou Center for Applied Mathematics, Guangzhou University, Guangzhou 510006, China
| | - Zhenhua Yuan
- School of Mathematics and Information Science, Guangzhou University, Guangzhou 510006, China; Guangdong Provincial Key Laboratory of Information Security Technology, Guangzhou University, Guangzhou 510006, China; and Guangzhou Center for Applied Mathematics, Guangzhou University, Guangzhou 510006, China
| | - Long Gao
- School of Mathematics and Information Science, Guangzhou University, Guangzhou 510006, China; Guangdong Provincial Key Laboratory of Information Security Technology, Guangzhou University, Guangzhou 510006, China; and Guangzhou Center for Applied Mathematics, Guangzhou University, Guangzhou 510006, China
| | - Junhao Peng
- School of Mathematics and Information Science, Guangzhou University, Guangzhou 510006, China; Guangdong Provincial Key Laboratory of Information Security Technology, Guangzhou University, Guangzhou 510006, China; and Guangzhou Center for Applied Mathematics, Guangzhou University, Guangzhou 510006, China
| |
Collapse
|
4
|
Zelenkovski K, Sandev T, Metzler R, Kocarev L, Basnarkov L. Random Walks on Networks with Centrality-Based Stochastic Resetting. ENTROPY (BASEL, SWITZERLAND) 2023; 25:293. [PMID: 36832659 PMCID: PMC9955709 DOI: 10.3390/e25020293] [Citation(s) in RCA: 2] [Impact Index Per Article: 2.0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Figures] [Subscribe] [Scholar Register] [Received: 12/26/2022] [Revised: 01/19/2023] [Accepted: 02/02/2023] [Indexed: 06/18/2023]
Abstract
We introduce a refined way to diffusely explore complex networks with stochastic resetting where the resetting site is derived from node centrality measures. This approach differs from previous ones, since it not only allows the random walker with a certain probability to jump from the current node to a deliberately chosen resetting node, rather it enables the walker to jump to the node that can reach all other nodes faster. Following this strategy, we consider the resetting site to be the geometric center, the node that minimizes the average travel time to all the other nodes. Using the established Markov chain theory, we calculate the Global Mean First Passage Time (GMFPT) to determine the search performance of the random walk with resetting for different resetting node candidates individually. Furthermore, we compare which nodes are better resetting node sites by comparing the GMFPT for each node. We study this approach for different topologies of generic and real-life networks. We show that, for directed networks extracted for real-life relationships, this centrality focused resetting can improve the search to a greater extent than for the generated undirected networks. This resetting to the center advocated here can minimize the average travel time to all other nodes in real networks as well. We also present a relationship between the longest shortest path (the diameter), the average node degree and the GMFPT when the starting node is the center. We show that, for undirected scale-free networks, stochastic resetting is effective only for networks that are extremely sparse with tree-like structures as they have larger diameters and smaller average node degrees. For directed networks, the resetting is beneficial even for networks that have loops. The numerical results are confirmed by analytic solutions. Our study demonstrates that the proposed random walk approach with resetting based on centrality measures reduces the memoryless search time for targets in the examined network topologies.
Collapse
Affiliation(s)
- Kiril Zelenkovski
- Research Center for Computer Science and Information Technologies, Macedonian Academy of Sciences and Arts, Bul. Krste Misirkov 2, 1000 Skopje, Macedonia
| | - Trifce Sandev
- Research Center for Computer Science and Information Technologies, Macedonian Academy of Sciences and Arts, Bul. Krste Misirkov 2, 1000 Skopje, Macedonia
- Institute of Physics, Faculty of Natural Sciences and Mathematics, Ss. Cyril and Methodius University, Arhimedova 3, 1000 Skopje, Macedonia
- Institute of Physics & Astronomy, University of Potsdam, D-14776 Potsdam, Germany
| | - Ralf Metzler
- Institute of Physics & Astronomy, University of Potsdam, D-14776 Potsdam, Germany
- Asia Pacific Center for Theoretical Physics, Pohang 37673, Republic of Korea
| | - Ljupco Kocarev
- Research Center for Computer Science and Information Technologies, Macedonian Academy of Sciences and Arts, Bul. Krste Misirkov 2, 1000 Skopje, Macedonia
- Faculty of Computer Science and Engineering, Ss. Cyril and Methodius University, 1000 Skopje, Macedonia
| | - Lasko Basnarkov
- Research Center for Computer Science and Information Technologies, Macedonian Academy of Sciences and Arts, Bul. Krste Misirkov 2, 1000 Skopje, Macedonia
- Faculty of Computer Science and Engineering, Ss. Cyril and Methodius University, 1000 Skopje, Macedonia
| |
Collapse
|
5
|
Wang Y, Chen H. Entropy rate of random walks on complex networks under stochastic resetting. Phys Rev E 2022; 106:054137. [PMID: 36559349 DOI: 10.1103/physreve.106.054137] [Citation(s) in RCA: 2] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/15/2022] [Accepted: 10/27/2022] [Indexed: 11/16/2022]
Abstract
Stochastic processes under resetting at random times have attracted a lot of attention in recent years and served as illustrations of nontrivial and interesting static and dynamic features of stochastic dynamics. In this paper, we aim to address how the entropy rate is affected by stochastic resetting in discrete-time Markovian processes, and we explore nontrivial effects of the resetting in the mixing properties of a stochastic process. In particular, we consider resetting random walks (RRWs) with a single resetting node on three different types of networks: degree-regular random networks, a finite-size Cayley tree, and a Barabási-Albert (BA) scale-free network, and we compute the entropy rate as a function of the resetting probability γ. Interestingly, for the first two types of networks, the entropy rate shows a nonmonotonic dependence on γ. There exists an optimal value of γ at which the entropy rate reaches a maximum. Such a maximum is larger than that of maximal-entropy random walks (MREWs) and standard random walks (SRWs) on the same topology, while for the BA network the entropy rate of RRWs either shows a unique maximum or decreases monotonically with γ, depending upon the choice of the resetting node. When the maximum entropy rate of RRWs exists, it can be higher or lower than that of MREWs or SRWs. Our study reveals a nontrivial effect of stochastic resetting on nonequilibrium statistical physics.
Collapse
Affiliation(s)
- Yating Wang
- School of Physics and Optoelectronic Engineering, Anhui University, Hefei 230601, China
| | - Hanshuang Chen
- School of Physics and Optoelectronic Engineering, Anhui University, Hefei 230601, China
| |
Collapse
|
6
|
Tal-Friedman O, Roichman Y, Reuveni S. Diffusion with partial resetting. Phys Rev E 2022; 106:054116. [PMID: 36559492 DOI: 10.1103/physreve.106.054116] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/06/2022] [Accepted: 09/23/2022] [Indexed: 11/09/2022]
Abstract
Inspired by many examples in nature, stochastic resetting of random processes has been studied extensively in the past decade. In particular, various models of stochastic particle motion were considered where, upon resetting, the particle is returned to its initial position. Here we generalize the model of diffusion with resetting to account for situations where a particle is returned only a fraction of its distance to the origin, e.g., half way. We show that this model always attains a steady-state distribution which can be written as an infinite sum of independent, but not identical, Laplace random variables. As a result, we find that the steady-state transitions from the known Laplace form which is obtained in the limit of full resetting to a Gaussian form, which is obtained close to the limit of no resetting. A similar transition is shown to be displayed by drift diffusion whose steady state can also be expressed as an infinite sum of independent random variables. Finally, we extend our analysis to capture the temporal evolution of drift diffusion with partial resetting, providing a bottom-up probabilistic construction that yields a closed-form solution for the time-dependent distribution of this process in Fourier-Laplace space. Possible extensions and applications of diffusion with partial resetting are discussed.
Collapse
Affiliation(s)
- Ofir Tal-Friedman
- School of Physics and Astronomy, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 6997801, Israel
| | - Yael Roichman
- School of Physics and Astronomy, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 6997801, Israel.,School of Chemistry, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 6997801, Israel.,Center for the Physics and Chemistry of Living Systems, Tel Aviv University, Tel Aviv 6997801, Israel
| | - Shlomi Reuveni
- School of Chemistry, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 6997801, Israel.,Center for the Physics and Chemistry of Living Systems, Tel Aviv University, Tel Aviv 6997801, Israel.,The Sackler Center for Computational Molecular and Materials Science, Tel Aviv University, Tel Aviv 6997801, Israel
| |
Collapse
|
7
|
Chen H, Ye Y. Random walks on complex networks under time-dependent stochastic resetting. Phys Rev E 2022; 106:044139. [PMID: 36397577 DOI: 10.1103/physreve.106.044139] [Citation(s) in RCA: 2] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/31/2022] [Accepted: 10/05/2022] [Indexed: 06/16/2023]
Abstract
We study discrete-time random walks on networks subject to a time-dependent stochastic resetting, where the walker either hops randomly between neighboring nodes with a probability 1-ϕ(a) or is reset to a given node with a complementary probability ϕ(a). The resetting probability ϕ(a) depends on the time a since the last reset event (also called a, the age of the walker). Using the renewal approach and spectral decomposition of the transition matrix, we formulate the stationary occupation probability of the walker at each node and the mean first passage time between two arbitrary nodes. Concretely, we consider two different time-dependent resetting protocols that are both exactly solvable. One is that ϕ(a) is a step-shaped function of a and the other one is that ϕ(a) is a rational function of a. We demonstrate the theoretical results on several different networks, also validated by numerical simulations, and find that the time-modulated resetting protocols can be more advantageous than the constant-probability resetting in accelerating the completion of a target search process.
Collapse
Affiliation(s)
- Hanshuang Chen
- School of Physics and Optoelectronic Engineering, Anhui University, Hefei 230601, China
| | - Yanfei Ye
- School of Physics and Optoelectronic Engineering, Anhui University, Hefei 230601, China
| |
Collapse
|
8
|
Bae Y, Son G, Jeong H. Unexpected advantages of exploitation for target searches in complex networks. CHAOS (WOODBURY, N.Y.) 2022; 32:083118. [PMID: 36049943 DOI: 10.1063/5.0089155] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 02/23/2022] [Accepted: 07/11/2022] [Indexed: 06/15/2023]
Abstract
Exploitation universally emerges in various decision-making contexts, e.g., animals foraging, web surfing, the evolution of scientists' research topics, and our daily lives. Despite its ubiquity, exploitation, which refers to the behavior of revisiting previous experiences, has often been considered to delay the search process of finding a target. In this paper, we investigate how exploitation affects search performance by applying a non-Markovian random walk model, where a walker randomly revisits a previously visited node using long-term memory. We analytically study two broad forms of network structures, namely, (i) clique-like networks and (ii) lollipop-like networks and find that exploitation can significantly improve search performance in lollipop-like networks, whereas it hinders target search in clique-like networks. Moreover, we numerically verify that exploitation can reduce the time needed to fully explore the underlying networks using 550 diverse real-world networks. Based on the analytic result, we define the lollipop-likeness of a network and observe a positive relationship between the advantage of exploitation and lollipop-likeness.
Collapse
Affiliation(s)
- Youngkyoung Bae
- Department of Physics, Korea Advanced Institute of Science and Technology, Daejeon 34141, South Korea
| | - Gangmin Son
- Department of Physics, Korea Advanced Institute of Science and Technology, Daejeon 34141, South Korea
| | - Hawoong Jeong
- Department of Physics, Korea Advanced Institute of Science and Technology, Daejeon 34141, South Korea
| |
Collapse
|
9
|
Wang W, Cherstvy AG, Kantz H, Metzler R, Sokolov IM. Time averaging and emerging nonergodicity upon resetting of fractional Brownian motion and heterogeneous diffusion processes. Phys Rev E 2021; 104:024105. [PMID: 34525678 DOI: 10.1103/physreve.104.024105] [Citation(s) in RCA: 20] [Impact Index Per Article: 6.7] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/27/2021] [Accepted: 07/14/2021] [Indexed: 12/12/2022]
Abstract
How different are the results of constant-rate resetting of anomalous-diffusion processes in terms of their ensemble-averaged versus time-averaged mean-squared displacements (MSDs versus TAMSDs) and how does stochastic resetting impact nonergodicity? We examine, both analytically and by simulations, the implications of resetting on the MSD- and TAMSD-based spreading dynamics of particles executing fractional Brownian motion (FBM) with a long-time memory, heterogeneous diffusion processes (HDPs) with a power-law space-dependent diffusivity D(x)=D_{0}|x|^{γ} and their "combined" process of HDP-FBM. We find, inter alia, that the resetting dynamics of originally ergodic FBM for superdiffusive Hurst exponents develops disparities in scaling and magnitudes of the MSDs and mean TAMSDs indicating weak ergodicity breaking. For subdiffusive HDPs we also quantify the nonequivalence of the MSD and TAMSD and observe a new trimodal form of the probability density function. For reset FBM, HDPs and HDP-FBM we compute analytically and verify by simulations the short-time MSD and TAMSD asymptotes and long-time plateaus reminiscent of those for processes under confinement. We show that certain characteristics of these reset processes are functionally similar despite a different stochastic nature of their nonreset variants. Importantly, we discover nonmonotonicity of the ergodicity-breaking parameter EB as a function of the resetting rate r. For all reset processes studied we unveil a pronounced resetting-induced nonergodicity with a maximum of EB at intermediate r and EB∼(1/r)-decay at large r. Alongside the emerging MSD-versus-TAMSD disparity, this r-dependence of EB can be an experimentally testable prediction. We conclude by discussing some implications to experimental systems featuring resetting dynamics.
Collapse
Affiliation(s)
- Wei Wang
- Max Planck Institute for the Physics of Complex Systems, Nöthnitzer Straße 38, 01187 Dresden, Germany
| | - Andrey G Cherstvy
- Institute for Physics & Astronomy University of Potsdam, Karl-Liebknecht-Straße 24/25, 14476 Potsdam-Golm, Germany.,Institut für Physik, Humboldt-Universität zu Berlin, Newtonstraße 15, 12489 Berlin, Germany
| | - Holger Kantz
- Max Planck Institute for the Physics of Complex Systems, Nöthnitzer Straße 38, 01187 Dresden, Germany
| | - Ralf Metzler
- Institute for Physics & Astronomy University of Potsdam, Karl-Liebknecht-Straße 24/25, 14476 Potsdam-Golm, Germany
| | - Igor M Sokolov
- Institut für Physik, Humboldt-Universität zu Berlin, Newtonstraße 15, 12489 Berlin, Germany.,IRIS Adlershof, Zum Großen Windkanal 6, 12489 Berlin, Germany
| |
Collapse
|
10
|
Huang F, Chen H. Random walks on complex networks with first-passage resetting. Phys Rev E 2021; 103:062132. [PMID: 34271762 DOI: 10.1103/physreve.103.062132] [Citation(s) in RCA: 8] [Impact Index Per Article: 2.7] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/21/2021] [Accepted: 06/01/2021] [Indexed: 11/07/2022]
Abstract
We study discrete-time random walks on arbitrary networks with first-passage resetting processes. To the end, a set of nodes are chosen as observable nodes, and the walker is reset instantaneously to a given resetting node whenever it hits either of observable nodes. We derive exact expressions of the stationary occupation probability, the average number of resets in the long time, and the mean first-passage time between arbitrary two nonobservable nodes. We show that all the quantities can be expressed in terms of the fundamental matrix Z=(I-Q)^{-1}, where I is the identity matrix and Q is the transition matrix between nonobservable nodes. Finally, we use ring networks, two-dimensional square lattices, barbell networks, and Cayley trees to demonstrate the advantage of first-passage resetting in global search on such networks.
Collapse
Affiliation(s)
- Feng Huang
- Key Laboratory of Advanced Electronic Materials and Devices & School of Mathematics and Physics, Anhui Jianzhu University, Hefei, 230601, China.,Key Laboratory of Architectural Acoustic Environment of Anhui Higher Education Institutes, Hefei, 230601, China
| | - Hanshuang Chen
- Department of Physics, Anhui University, Hefei, 230601, China
| |
Collapse
|