Exact scaling for the mean first-passage time of random walks on a generalized Koch network with a trap

In this paper, we study the scaling for the mean first-passage time (MFPT) of the random walks on a generalized Koch network with a trap. Through the network construction, where the initial state is transformed from a triangle to a polygon, we obtain the exact scaling for the MFPT. We show that the MFPT grows linearly with the number of nodes and the dimensions of the polygon in the large limit of the network order. In addition, we determine the exponents of scaling efficiency characterizing the random walks. Our results are the generalizations of those derived for the Koch network, which shed light on the analysis of random walks over various fractal networks.     

Impact of degree heterogeneity on the behavior of trapping in Koch networks

Previous work shows that the mean first-passage time (MFPT) for random walks to a given hub node (node with maximum degree) in uncorrelated random scale-free networks is closely related to the exponent γ of power-law degree distribution P(k) ～ k(-γ), which describes the extent of heterogeneity of scale-free network structure. However, extensive empirical research indicates that real networked systems also display ubiquitous degree correlations. In this paper, we address the trapping issue on the Koch networks, which is a special random walk with one trap fixed at a hub node. The Koch networks are power-law with the characteristic exponent γ in the range between 2 and 3, they are either assortative or disassortative. We calculate exactly the MFPT that is the average of first-passage time from all other nodes to the trap. The obtained explicit solution shows that in large networks the MFPT varies lineally with node number N, which is obviously independent of γ and is sharp contrast to the scaling behavior of MFPT observed for uncorrelated random scale-free networks, where γ influences qualitatively the MFPT of trapping problem.     

Scaling of mean first-passage time as efficiency measure of nodes sending information on scale-free Koch networks

Random walks on complex networks, especially scale-free networks, have attracted considerable interest in the past few years. A lot of previous work showed that the average receiving time (ART), i.e., the average of mean first-passage time (MFPT) for random walks to a given hub node (node with maximum degree) averaged over all starting points in scale-free small-world networks exhibits a sublinear or linear dependence on network order N (number of nodes), which indicates that hub nodes are very efficient in receiving information if one looks upon the random walker as an information messenger. Thus far, the efficiency of a hub node sending information on scale-free small-world networks has not been addressed yet. In this paper, we study random walks on the class of Koch networks with scale-free behavior and small-world effect. We derive some basic properties for random walks on the Koch network family, based on which we calculate analytically the average sending time (AST) defined as the average of MFPTs from a hub node to all other nodes, excluding the hub itself. The obtained closed-form expression displays that in large networks the AST grows with network order as N ln N, which is larger than the linear scaling of ART to the hub from other nodes. On the other hand, we also address the case with the information sender distributed uniformly among the Koch networks, and derive analytically the global mean first-passage time, namely, the average of MFPTs between all couples of nodes, the leading scaling of which is identical to that of AST. From the obtained results, we present that although hub nodes are more efficient for receiving information than other nodes, they display a qualitatively similar speed for sending information as non-hub nodes. Moreover, we show that that AST from a starting point (sender) to all possible targets is not sensitively affected by the sender’s location. The present findings are helpful for better understanding random walks performed on scale-free small-world networks.     

Random walks in generalized delayed recursive trees

Recently a great deal of effort has been made to explicitly determine the mean first-passage time （MFPT） between two nodes averaged over all pairs of nodes on a fractal network. In this paper, we first propose a family of generalized delayed recursive trees characterized by two parameters, where the existing nodes have a time delay to produce new nodes. We then study the MFPT of random walks on this kind of recursive tree and investigate the effect of the time delay on the MFPT. By relating random walks to electrical networks, we obtain an exact formula for the MFPT and verify it by numerical calculations. Based on the obtained results, we further show that the MFPT of delayed recursive trees is much shorter, implying that the efficiency of random walks is much higher compared with the non-delayed counterpart. Our study provides a deeper understanding of random walks on delayed fractal networks.     

Random walks on complex networks

We investigate random walks on complex networks and derive an exact expression for the mean first-passage time (MFPT) between two nodes. We introduce for each node the random walk centrality C, which is the ratio between its coordination number and a characteristic relaxation time, and show that it determines essentially the MFPT. The centrality of a node determines the relative speed by which a node can receive and spread information over the network in a random process. Numerical simulations of an ensemble of random walkers moving on paradigmatic network models confirm this analytical prediction.     

Mean first-passage time for random walks on undirected networks

In this paper, by using two different techniques we derive an explicit formula for the mean first-passage time (MFPT) between any pair of nodes on a general undirected network, which is expressed in terms of eigenvalues and eigenvectors of an associated matrix similar to the transition matrix. We then apply the formula to derive a lower bound for the MFPT to arrive at a given node with the starting point chosen from the stationary distribution over the set of nodes. We show that for a correlated scale-free network of size N with a degree distribution P(d) ∼ d ^−γ , the scaling of the lower bound is N ^1−1/γ . Also, we provide a simple derivation for an eigentime identity. Our work leads to a comprehensive understanding of recent results about random walks on complex networks, especially on scale-free networks.     

Mean first-passage time of quantum transition processes

In this paper, we consider the problem of mean first-passage time (MFPT) in quantum mechanics; the MFPT is the average time of the transition from a given initial state, passing through some intermediate states, to a given final state for the first time. We apply the method developed in statistical mechanics for calculating the MFPT of random walks to calculate the MFPT of a transition process. As applications, we (1) calculate the MFPT for multiple-state systems, (2) discuss transition processes occurring in an environmental background, (3) consider a roundabout transition in a hydrogen atom, and (4) apply the approach to laser theory.     

Mixing search on complex networks

In this article, we derive the first passage time (FPT) distribution and the mean first passage time (MFPT) of random walks from multiple sources on networks. On the basis of analysis and simulation, we find that the MFPT drops substantially when particle number increases at the first stage, and converges to the shortest distance between the sources and the destination when particle number tends to infinite. Given the fact that a Brownian particle from a high-degree node often needs a large number of steps to reach an expected low-degree node, which is the bottleneck for a single random walk, we propose a mixing search model to improve the efficiency of search processes by using random walks from multiple sources to continue the searches from high-degree nodes to destinations. We compare our model with the mixing navigation model proposed by Zhou on complex networks and find that our model converges much faster with lower hardware cost than Zhou’s model. Moreover, simulations on scale-free networks show that the search efficiency of our model is much higher than that of a single random walk, and comparable to that of multiple random walks which have much higher hardware cost than our model. Finally, we discuss the traffic cost of our model, and propose an absorption strategy for our model to recover the additional walkers in networks. Simulations indicate that this strategy reduces the traffic cost of our model effectively.     

Average weighted receiving time in recursive weighted Koch networks

Motivated by the empirical observation in airport networks and metabolic networks, we introduce the model of the recursive weighted Koch networks created by the recursive division method. As a fundamental dynamical process, random walks have received considerable interest in the scientific community. Then, we study the recursive weighted Koch networks on random walk i.e., the walker, at each step, starting from its current node, moves uniformly to any of its neighbours. In order to study the model more conveniently, we use recursive division method again to calculate the sum of the mean weighted first-passing times for all nodes to absorption at the trap located in the merging node. It is showed that in a large network, the average weighted receiving time grows sublinearly with the network order.     

Exact solution of the 1D Hubbard model with NN and NNN interactions in the narrow-band limit

In this paper, we propose a family of weighted extended Koch networks based on a class of extended Koch networks. They originate from a r-complete graph, and each node in each r-complete graph of current generation produces mr-complete graphs whose weighted edges are scaled by factor h in subsequent evolutionary step. We study the structural properties of these networks and random walks on them. In more detail, we calculate exactly the average weighted shortest path length (AWSP), average receiving time (ART) and average sending time (AST). Besides, the technique of resistor network is employed to uncover the relationship between ART and AST on networks with unit weight. In the infinite network order limit, the average weighted shortest path lengths stay bounded with growing network order (0 < h < 1). The closed form expression of ART shows that it exhibits a sub-linear dependence (0 < h < 1) or linear dependence (h = 1) on network order. On the contrary, the AST behaves super-linearly with the network order. Collectively, all the obtained results show that the efficiency of message transportation on weighted extended Koch networks has close relation to the network parameters h, m and r. All these findings could shed light on the structure and random walks of general weighted networks.     

Zero constant formula for first-passage observables in bounded domains

In this Letter, we develop an analytical approach which provides an explicit determination of mean first-passage times (MFPTs) for random walks in bounded domains for a wide class of transport processes. In particular, we derive for the first time explicit expressions of MFPTs for emblematic models of transport in complex media, such as diffusion on deterministic and random fractals. This approach relies on a scale-invariance hypothesis and a large volume expansion of the MFPT, which actually proves to be very accurate even for small system sizes as shown by numerical simulations. This explicit determination of MFPTs can be straightforwardly generalized to further useful first-passage observables such as occupation times and splitting probabilities.     

Scaling of average receiving time and average weighted shortest path on weighted Koch networks

In this paper we present weighted Koch networks based on classic Koch networks. A new method is used to determine the average receiving time (ART), whose key step is to write the sum of mean first-passage times (MFPTs) for all nodes to absorption at the trap located at a hub node as a recursive relation. We show that the ART exhibits a sublinear or linear dependence on network order. Thus, the weighted Koch networks are more efficient than classic Koch networks in receiving information. Moreover, average weighted shortest path (AWSP) is calculated. In the infinite network order limit, the AWSP depends on the scaling factor. The weighted Koch network grows unbounded but with the logarithm of the network size, while the weighted shortest paths stay bounded.     

Random walks on dual Sierpinski gaskets

We study an unbiased random walk on dual Sierpinski gaskets embedded in d-dimensional Euclidean spaces. We first determine the mean first-passage time (MFPT) between a particular pair of nodes based on the connection between the MFPTs and the effective resistance. Then, by using the Laplacian spectra, we evaluate analytically the global MFPT (GMFPT), i.e., MFPT between two nodes averaged over all node pairs. Concerning these two quantities, we obtain explicit solutions and show how they vary with the number of network nodes. Finally, we relate our results for the case of d = 2 to the well-known Hanoi Towers problem.     

Active biopolymers confer fast reorganization kinetics

Many cytoskeletal biopolymers are "active," consuming energy in large quantities. In this Letter, we identify a fundamental difference between active polymers and passive, equilibrium polymers: for equal mean lengths, active polymers can reorganize faster than equilibrium polymers. We show that equilibrium polymers are intrinsically limited to linear scaling between mean lifetime (or mean first-passage time, or MFPT) and mean length, MFPT～, by analogy to 1D Potts models. By contrast, we present a simple active-polymer model that improves upon this scaling, such that MFPT～(1/2). Since, to be biologically useful, structural biopolymers must typically be many monomers long yet respond dynamically to the needs of the cell, the difference in reorganization kinetics may help to justify the active polymers' greater energy cost.     

Space use by foragers consuming renewable resources

Through the analysis of unbiased random walks on fractal trees and continuous time random walks, we show that even if a process is characterized by a mean square displacement (MSD) growing linearly with time (standard behaviour) its diffusion properties can be not trivial. In particular, we show that the following scenarios are consistent with a linear increase of MSD with time: (i) the high-order moments, ?x(t) ^q ? for q > 2 and the probability density of the process exhibit multiscaling; (ii) the random walk on certain fractal graphs, with non integer spectral dimension, can display a fully standard diffusion; (iii) positive order moments satisfying standard scaling does not imply an exact scaling property of the probability density.     

Scaling Analysis for the Adsorption Transition in a Watermelon Network of n Directed Non-Intersecting Walks

The partition function for the problem of n directed non-intersecting walks interacting via contact potentials with a wall parallel to the direction of the walks has previously been calculated as an n×n determinant. Here, we describe how to analyse the scaling behaviour of this problem using alternative representations of the solution. In doing so we derive the asymptotics of the partition function of a watermelon network of n such walks for all temperatures, and so calculate the associated network exponents in the three regimes: desorbed, adsorbed, and at the adsorption transition. Furthermore, we derive the full scaling function around the adsorption transition for all n. At the adsorption transition we also derive a simple product form for the partition function. These results have, in part, been derived using recurrence relations satisfied by the original determinantal solution.     

Biased trapping issue on weighted hierarchical networks

In this paper, we present trapping issues of weight-dependent walks on weighted hierarchical networks which are based on the classic scale-free hierarchical networks. Assuming that edge’s weight is used as local information by a random walker, we introduce a biased walk. The biased walk is that a walker, at each step, chooses one of its neighbours with a probability proportional to the weight of the edge. We focus on a particular case with the immobile trap positioned at the hub node which has the largest degree in the weighted hierarchical networks. Using a method based on generating functions, we determine explicitly the mean first-passage time (MFPT) for the trapping issue. Let parameter a (0 < a < 1) be the weight factor. We show that the efficiency of the trapping process depends on the parameter a; the smaller the value of a, the more efficient is the trapping process.     

Continuity and Anomalous Fluctuations in Random Walks in Dynamic Random Environments: Numerics,Phase Diagrams and Conjectures

We perform simulations for one dimensional continuous-time random walks in two dynamic random environments with fast (independent spin-flips) and slow (simple symmetric exclusion) decay of space-time correlations, respectively. We focus on the asymptotic speeds and the scaling limits of such random walks. We observe different behaviors depending on the dynamics of the underlying random environment and the ratio between the jump rate of the random walk and the one of the environment. We compare our data with well known results for static random environment. We observe that the non-diffusive regime known so far only for the static case can occur in the dynamical setup too. Such anomalous fluctuations give rise to a new phase diagram. Further we discuss possible consequences for more general static and dynamic random environments.     

Localization transition of biased random walks on random networks

We study random walks on large random graphs that are biased towards a randomly chosen but fixed target node. We show that a critical bias strength bc exists such that most walks find the target within a finite time when b > bc. For b < bc, a finite fraction of walks drift off to infinity before hitting the target. The phase transition at b=bc is a critical point in the sense that quantities such as the return probability P(t) show power laws, but finite-size behavior is complex and does not obey the usual finite-size scaling ansatz. By extending rigorous results for biased walks on Galton-Watson trees, we give the exact analytical value for bc and verify it by large scale simulations.     

Langevin Picture of Lévy Walks and Their Extensions

In this paper we derive Langevin picture of Lévy walks. Applying recent advances in the theory of coupled continuous time random walks we find a limiting process of the properly scaled Lévy walk. Next, we introduce extensions of Levy walks, in which jump sizes are some functions of waiting times. We prove that under proper scaling conditions, such generalized Lévy walks converge in distribution to the appropriate limiting processes. We also derive the corresponding fractional diffusion equations and investigate behavior of the mean square displacements of the limiting processes, showing that different coupling functions lead to various types of anomalous diffusion.