اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدGlobal mean first-passage times of random walks on complex networks
141
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We present a general framework, applicable to a broad class of random walks on complex networks, which provides a rigorous lower bound for the mean first-passage time of a random walker to a target site averaged over its starting position, the so-called global mean first-passage time (GMFPT). This bound is simply expressed in terms of the equilibrium distribution at the target, and implies a minimal scaling of the GMFPT with the network size. We show that this minimal scaling, which can be arbitrarily slow for a proper choice of highly connected target, is realized under the simple condition that the random walk is transient at the target site, and independently of the small-world, scale free or fractal properties of the network. Last, we put forward that the GMFPT to a specific target is not a representative property of the network, since the target averaged GMFPT satisfies much more restrictive bounds, which forbid any sublinear scaling with the network size.
قيم البحث
اقرأ أيضاً
We perform an in-depth study for mean first-passage time (MFPT)---a primary quantity for random walks with numerous applications---of maximal-entropy random walks (MERW) performed in complex networks. For MERW in a general network, we derive an expli
cit expression of MFPT in terms of the eigenvalues and eigenvectors of the adjacency matrix associated with the network. For MERW in uncorrelated networks, we also provide a theoretical formula of MFPT at the mean-field level, based on which we further evaluate the dominant scalings of MFPT to different targets for MERW in uncorrelated scale-free networks, and compare the results with those corresponding to traditional unbiased random walks (TURW). We show that the MFPT to a hub node is much lower for MERW than for TURW. However, when the destination is a node with the least degree or a uniformly chosen node, the MFPT is higher for MERW than for TURW. Since MFPT to a uniformly chosen node measures real efficiency of search in networks, our work provides insight into general searching process in complex networks.
We obtain an exact formula for the first-passage time probability distribution for random walks on complex networks using inverse Laplace transform. We write the formula as the summation of finitely many terms with different frequencies corresponding
to the poles of Laplace transformed function and separate the short-term and long-term behavior of the first-passage process. We give a formula of the decay rate $beta$, which is inversely proportional to the characteristic relaxation time $tau$ of the target node. This exact formula for the first-passage probability between two nodes at a given time can be approximately solved in the mean field approximation by estimation of the characteristic relaxation time $tau$. Our theoretical results compare well with numerical simulation on artificial as well as real networks.
An efficient searcher needs to balance properly the tradeoff between the exploration of new spatial areas and the exploitation of nearby resources, an idea which is at the core of scale-free Levy search strategies. Here we study multi-scale random wa
lks as an approximation to the scale- free case and derive the exact expressions for their mean-first passage times in a one-dimensional finite domain. This allows us to provide a complete analytical description of the dynamics driving the asymmetric regime, in which both nearby and faraway targets are available to the searcher. For this regime, we prove that the combination of only two movement scales can be enough to outperform both balistic and Levy strategies. This two-scale strategy involves an optimal discrimination between the nearby and faraway targets, which is only possible by adjusting the range of values of the two movement scales to the typical distances between encounters. So, this optimization necessarily requires some prior information (albeit crude) about targets distances or distributions. Furthermore, we found that the incorporation of additional (three, four, ...) movement scales and its adjustment to target distances does not improve further the search efficiency. This allows us to claim that optimal random search strategies in the asymmetric regime actually arise through the informed combination of only two walk scales (related to the exploitative and the explorative scale, respectively), expanding on the well-known result that optimal strategies in strictly uninformed scenarios are achieved through Levy paths (or, equivalently, through a hierarchical combination of multiple scales).
We study the problem of random search in finite networks with a tree topology, where it is expected that the distribution of the first-passage time F(t) decays exponentially. We show that the slope of the exponential tail is independent of the initia
l conditions of entering the tree in general, and scales exponentially or as a power law with the extent of the tree L, depending on the tendency p to jump toward the target node. It is unfeasible to uniquely determine L and p from measuring the tail slope or the mean first-passage time (MFPT) of an ordinary diffusion along the tree. To unravel the structure, we consider lazy random walkers that take steps with probability m when jumping on the nodes and return with probability q from the leaves. By deriving an exact analytical expression for the MFPT of the intermittent random walk, we verify that the structural information of the tree can be uniquely extracted by measuring the MFPT for two randomly chosen types of tracer particles with distinct experimental parameters m and q. We also address the applicability of our approach in the presence of disorder in the structure of the tree or statistical uncertainty in the experimental parameters.
We present an analytical method for computing the mean cover time of a random walk process on arbitrary, complex networks. The cover time is defined as the time a random walker requires to visit every node in the network at least once. This quantity
is particularly important for random search processes and target localization in network topologies. Based on the global mean first passage time of target nodes we derive an estimate for the cumulative distribution function of the cover time based on first passage time statistics. We show that our result can be applied to various model networks, including ErdH{o}s-Renyi and Barabasi-Albert networks, as well as various real-world networks. Our results reveal an intimate link between first passage and cover time statistics in networks in which structurally induced temporal correlations decay quickly and offer a computationally efficient way for estimating cover times in network related applications.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
