Analytic expression for the mean time to absorption for a random walker on the Sierpinski gasket

Mean trapping time for an arbitrary trap site on a class of fractal scale-free trees

Fractals are ubiquitous in nature and random walks on fractals have attracted lots of scientific attention in the past several years. In this work, we consider discrete random walks on a class of fractal scale-free trees (FST), whose topologies are controlled by two integer parameters (i.e., u≥2 and v≥1) and exhibit a wide range of topological properties by suitably varying the parameters u and v. The mean trapping time (MTT), referred to as T_{y}, which is the mean time it takes the walker to be absorbed by the trap fixed at site y of the FST, is addressed analytically on the FST, and the effects of the trap location y on the MTT for the FST and for the general trees are also analyzed. First, a method, which is based on the connection between the MTT and the effective resistances, to derive analytically T_{y} for an arbitrary site y of the FST is presented, and some examples are provided to show the effectiveness of the method. Then, we compare T_{y} for all the possible site y of the trees, and find the sites where T_{y} achieves the minimum (or maximum) on the FST. Finally, we analyze the effects of trap location on the MTT in general trees and find that the average path length (APL) from an arbitrary site to the trap is the decisive factor which dominates the difference in the MTTs for different trap locations on general trees. We find, for any tree, the MTT obtains the minimum (or maximum) at sites where the APL achieves the minimum (or maximum).

Optimizing the First-Passage Process on a Class of Fractal Scale-Free Trees

First-passage processes on fractals are of particular importance since fractals are ubiquitous in nature, and first-passage processes are fundamental dynamic processes that have wide applications. The global mean first-passage time (GMFPT), which is the expected time for a walker (or a particle) to first reach the given target site while the probability distribution for the position of target site is uniform, is a useful indicator for the transport efficiency of the whole network. The smaller the GMFPT, the faster the mass is transported on the network. In this work, we consider the first-passage process on a class of fractal scale-free trees (FSTs), aiming at speeding up the first-passage process on the FSTs. Firstly, we analyze the global mean first-passage time (GMFPT) for unbiased random walks on the FSTs. Then we introduce proper weight, dominated by a parameter w (w > 0), to each edge of the FSTs and construct a biased random walks strategy based on these weights. Next, we analytically evaluated the GMFPT for biased random walks on the FSTs. The exact results of the GMFPT for unbiased and biased random walks on the FSTs are both obtained. Finally, we view the GMFPT as a function of parameter w and find the point where the GMFPT achieves its minimum. The exact result is obtained and a way to optimize and speed up the first-passage process on the FSTs is presented.

Average trapping time on weighted directed Koch network

Numerous recent studies have focused on random walks on undirected binary scale-free networks. However, random walks with a given target node on weighted directed networks remain less understood. In this paper, we first introduce directed weighted Koch networks, in which any pair of nodes is linked by two edges with opposite directions, and weights of edges are controlled by a parameter θ . Then, to evaluate the transportation efficiency of random walk, we derive an exact solution for the average trapping time (ATT), which agrees well with the corresponding numerical solution. We show that leading behaviour of ATT is function of the weight parameter θ and that the ATT can grow sub-linearly, linearly and super-linearly with varying θ . Finally, we introduce a delay parameter p to modify the transition probability of random walk, and provide a closed-form solution for ATT, which still coincides with numerical solution. We show that in the closed-form solution, the delay parameter p can change the coefficient of ATT, but cannot change the leading behavior. We also show that desired ATT or trapping efficiency can be obtained by setting appropriate weight parameter and delay parameter simultaneously. Thereby, this work advance the understanding of random walks on directed weighted scale-free networks.

First-passage properties of mortal random walks: Ballistic behavior, effective reduction of dimensionality, and scaling functions for hierarchical graphs

We consider a mortal random walker on a family of hierarchical graphs in the presence of some trap sites. The configuration comprising the graph, the starting point of the walk, and the locations of the trap sites is taken to be exactly self-similar as one goes from one generation of the family to the next. Under these circumstances, the total probability that the walker hits a trap is determined exactly as a function of the single-step survival probability q of the mortal walker. On the nth generation graph of the family, this probability is shown to be given by the nth iterate of a certain scaling function or map q→f(q). The properties of the map then determine, in each case, the behavior of the trapping probability, the mean time to trapping, the temporal scaling factor governing the random walk dimension on the graph, and other related properties. The formalism is illustrated for the cases of a linear hierarchical lattice and the Sierpinski graphs in two and three Euclidean dimensions. We find an effective reduction of the random walk dimensionality due to the ballistic behavior of the surviving particles induced by the mortality constraint. The relevance of this finding for experiments involving travel times of particles in diffusion-decay systems is discussed.

Generation of fractals as Duffing equation orbits

Dynamics are constructed for fractals utilizing the motion associated with Duffing equation. Using the paradigm of Fatou-Julia iteration, we develop iterations to map fractals accompanied with a criterion to ensure that the image is again a fractal. Because of the close link between mappings, differential equations and dynamical systems, one can introduce dynamics for fractals through differential equations such that they become points of the solution trajectory. There is no doubt that the differential equations have a distinct role for studying chaos. Therefore, characterization of fractals as trajectory points is an important step toward a better understanding of the link between chaos and fractal geometry. Moreover, it would be helpful to enhance and widen the scope of their applications in physics and engineering.

The trapping problem of the weighted scale-free treelike networks for two kinds of biased walks

It has been recently reported that trapping problem can characterize various dynamical processes taking place on complex networks. However, most works focused on the case of binary networks, and dynamical processes on weighted networks are poorly understood. In this paper, we study two kinds of biased walks including standard weight-dependent walk and mixed weight-dependent walk on the weighted scale-free treelike networks with a trap at the central node. Mixed weight-dependent walk including non-nearest neighbor jump appears in many real situations, but related studies are much less. By the construction of studied networks in this paper, we determine all the eigenvalues of the fundamental matrix for two kinds of biased walks and show that the largest eigenvalue has an identical dominant scaling as that of the average trapping time (ATT). Thus, we can obtain the leading scaling of ATT by a more convenient method and avoid the tedious calculation. The obtained results show that the weight factor has a significant effect on the ATT, and the smaller the value of the weight factor, the more efficient the trapping process is. Comparing the standard weight-dependent walk with mixed weight-dependent walk, although next-nearest-neighbor jumps have no main effect on the trapping process, they can modify the coefficient of the dominant term for the ATT.

Navigation by anomalous random walks on complex networks

Anomalous random walks having long-range jumps are a critical branch of dynamical processes on networks, which can model a number of search and transport processes. However, traditional measurements based on mean first passage time are not useful as they fail to characterize the cost associated with each jump. Here we introduce a new concept of mean first traverse distance (MFTD) to characterize anomalous random walks that represents the expected traverse distance taken by walkers searching from source node to target node, and we provide a procedure for calculating the MFTD between two nodes. We use Lévy walks on networks as an example, and demonstrate that the proposed approach can unravel the interplay between diffusion dynamics of Lévy walks and the underlying network structure. Moreover, applying our framework to the famous PageRank search, we show how to inform the optimality of the PageRank search. The framework for analyzing anomalous random walks on complex networks offers a useful new paradigm to understand the dynamics of anomalous diffusion processes, and provides a unified scheme to characterize search and transport processes on networks.

Extended Vicsek fractals: Laplacian spectra and their applications

Extended Vicsek fractals (EVF) are the structures constructed by introducing linear spacers into traditional Vicsek fractals. Here we study the Laplacian spectra of the EVF. In particularly, the recurrence relations for the Laplacian spectra allow us to obtain an analytic expression for the sum of all inverse nonvanishing Laplacian eigenvalues. This quantity characterizes the large-scale properties, such as the gyration radius of the polymeric structures, or the global mean-first passage time for the random walk processes. Introduction of the linear spacers leads to local heterogeneities, which reveal themselves, for example, in the dynamics of EVF under external forces.

Spectra of weighted scale-free networks

Much information about the structure and dynamics of a network is encoded in the eigenvalues of its transition matrix. In this paper, we present a first study on the transition matrix of a family of weight driven networks, whose degree, strength, and edge weight obey power-law distributions, as observed in diverse real networks. We analytically obtain all the eigenvalues, as well as their multiplicities. We then apply the obtained eigenvalues to derive a closed-form expression for the random target access time for biased random walks occurring on the studied weighted networks. Moreover, using the connection between the eigenvalues of the transition matrix of a network and its weighted spanning trees, we validate the obtained eigenvalues and their multiplicities. We show that the power-law weight distribution has a strong effect on the behavior of random walks.

Anomalous behavior of trapping in extended dendrimers with a perfect trap

Compact and extended dendrimers are two important classes of dendritic polymers. The impact of the underlying structure of compact dendrimers on dynamical processes has been much studied, yet the relation between the dynamical and structural properties of extended dendrimers remains not well understood. In this paper, we study the trapping problem in extended dendrimers with generation-dependent segment lengths, which is different from that of compact dendrimers where the length of the linear segments is fixed. We first consider a particular case that the deep trap is located at the central node, and derive an exact formula for the average trapping time (ATT) defined as the average of the source-to-trap mean first passage time over all starting points. Then, using the obtained result we deduce a closed-form expression for the ATT to an arbitrary trap node, based on which we further obtain an explicit solution to the ATT corresponding to the trapping issue with the trap uniformly distributed in the polymer systems. We show that the trap location has a substantial influence on the trapping efficiency measured by the ATT, which increases with the shortest distance from the trap to the central node, a phenomenon similar to that for compact dendrimers. In contrast to this resemblance, the leading terms of ATTs for the three trapping problems differ drastically between extended and compact dendrimers, with the trapping processes in the extended dendrimers being less efficient than in compact dendrimers.

Exact calculations of first-passage properties on the pseudofractal scale-free web

In this paper, we consider discrete time random walks on the pseudofractal scale-free web (PSFW) and we study analytically the related first passage properties. First, we classify the nodes of the PSFW into different levels and propose a method to derive the generation function of the first passage probability from an arbitrary starting node to the absorbing domain, which is located at one or more nodes of low-level (i.e., nodes with large degree). Then, we calculate exactly the first passage probability, the survival probability, the mean, and the variance of first passage time by using the generating functions as a tool. Finally, for some illustrative examples corresponding to given choices of starting node and absorbing domain, we derive exact and explicit results for such first passage properties. The method we propose can as well address the cases where the absorbing domain is located at one or more nodes of high-level on the PSFW, and it can also be used to calculate the first passage properties on other networks with self-similar structure, such as (u, v) flowers and recursive scale-free trees.

Spectrum of walk matrix for Koch network and its application

Various structural and dynamical properties of a network are encoded in the eigenvalues of walk matrix describing random walks on the network. In this paper, we study the spectra of walk matrix of the Koch network, which displays the prominent scale-free and small-world features. Utilizing the particular architecture of the network, we obtain all the eigenvalues and their corresponding multiplicities. Based on the link between the eigenvalues of walk matrix and random target access time defined as the expected time for a walker going from an arbitrary node to another one selected randomly according to the steady-state distribution, we then derive an explicit solution to the random target access time for random walks on the Koch network. Finally, we corroborate our computation for the eigenvalues by enumerating spanning trees in the Koch network, using the connection governing eigenvalues and spanning trees, where a spanning tree of a network is a subgraph of the network, that is, a tree containing all the nodes.

Hitting and trapping times on branched structures

In this work we consider a simple random walk embedded in a generic branched structure and we find a close-form formula to calculate the hitting time H(i,f) between two arbitrary nodes i and j. We then use this formula to obtain the set of hitting times {H(i,f)} for combs and their expectation values, namely, the mean first-passage time, where the average is performed over the initial node while the final node f is given, and the global mean first-passage time, where the average is performed over both the initial and the final node. Finally, we discuss applications in the context of reaction-diffusion problems.

Controlling the efficiency of trapping in a scale-free small-world network

Designing appropriate techniques to effectively control the trapping process in complex systems towards desirable efficiency is of paramount importance in the study of trapping problem. In this paper, we present three different methods guiding trapping process in a scale-free small-world network with a deep trap positioned at an initial node. All the proposed approaches dominate the trapping process by varying the transition probability of random walks. In the first two techniques, the transition probability is modified by an introduced weight parameter and a stochastic parameter, respectively. And the third scheme is a combination of the first two approaches, controlled by both parameters synchronously. For all the three control strategies, we derive both analytically and numerically the average trapping time (ATT) as the measure of the trapping efficiency, with the obtained explicit expressions being in good agreement with their corresponding exact numerical solutions. Our results indicate that the weight parameter changes simultaneously the dominating scaling of ATT and its prefactor. Different from the weight parameter, the stochastic parameter only modifies the prefactor, keeping the leading scaling unchanged. Finally, compared with the first two manners, the third strategy is a fine control, possessing the advantages of the first two ones. This work deepens the understanding of controlling trapping process in complex systems.

Mean first-passage time for maximal-entropy random walks in complex networks

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 explicit 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.

Lattice statistical theory of random walks on a fractal-like geometry

We have designed a two-dimensional, fractal-like lattice and explored, both numerically and analytically, the differences between random walks on this lattice and a regular, square-planar Euclidean lattice. We study the efficiency of diffusion-controlled processes for flows from external sites to a centrosymmetric reaction center and, conversely, for flows from a centrosymmetric source to boundary sites. In both cases, we find that analytic expressions derived for the mean walk length on the fractal-like lattice have an algebraic dependence on system size, whereas for regular Euclidean lattices the dependence can be transcendental. These expressions are compared with those derived in the continuum limit using classical diffusion theory. Our analysis and the numerical results quantify the extent to which one paradigmatic class of spatial inhomogeneities can compromise the efficiency of adatom diffusion on solid supports and of surface-assisted self-assembly in metal-organic materials.

Random walks in unweighted and weighted modular scale-free networks with a perfect trap

Designing optimal structure favorable to diffusion and effectively controlling the trapping process are crucial in the study of trapping problem--random walks with a single trap. In this paper, we study the trapping problem occurring on unweighted and weighted networks, respectively. The networks under consideration display the striking scale-free, small-world, and modular properties, as observed in diverse real-world systems. For binary networks, we concentrate on three cases of trapping problems with the trap located at a peripheral node, a neighbor of the root with the least connectivity, and a farthest node, respectively. For weighted networks with edge weights controlled by a parameter, we also study three trapping problems, in which the trap is placed separately at the root, a neighbor of the root with the least degree, and a farthest node. For all the trapping problems, we obtain the analytical formulas for the average trapping time (ATT) measuring the efficiency of the trapping process, as well as the leading scaling of ATT. We show that for all the trapping problems in the binary networks with a trap located at different nodes, the dominating scalings of ATT reach the possible minimum scalings, implying that the networks have optimal structure that is advantageous to efficient trapping. Furthermore, we show that for trapping in the weighted networks, the ATT is controlled by the weight parameter, through modifying which, the ATT can behave superlinearly, linearly, sublinearly, or logarithmically with the system size. This work could help improving the design of systems with efficient trapping process and offers new insight into control of trapping in complex systems.

Analytic expression for the mean time to absorption for a random walker on the Sierpinski fractal. III. The effect of non-nearest-neighbor jumps

We present exact, analytic results for the mean time to trapping of a random walker on the class of deterministic Sierpinski graphs embedded in d≥2 Euclidean dimensions, when both nearest-neighbor (NN) and next-nearest-neighbor (NNN) jumps are included. Mean first-passage times are shown to be modified significantly as a consequence of the fact that NNN transitions connect fractals of two consecutive generations.

Random walks on non-homogenous weighted Koch networks

In this paper, we introduce new models of non-homogenous weighted Koch networks on real traffic systems depending on the three scaling factors r1,r2,r3∈(0,1). Inspired by the definition of the average weighted shortest path (AWSP), we define the average weighted receiving time (AWRT). Assuming that the walker, at each step, starting from its current node, moves uniformly to any of its neighbors, we show that in large network, the AWRT grows as power-law function of the network order with the exponent, represented by θ(r1,r2,r3)=log4(1+r1+r2+r3). Moreover, the AWSP, in the infinite network order limit, only depends on the sum of scaling factors r1,r2,r3.

Random walks in weighted networks with a perfect trap: an application of Laplacian spectra

Trapping processes constitute a primary problem of random walks, which characterize various other dynamical processes taking place on networks. Most previous works focused on the case of binary networks, while there is much less related research about weighted networks. In this paper, we propose a general framework for the trapping problem on a weighted network with a perfect trap fixed at an arbitrary node. By utilizing the spectral graph theory, we provide an exact formula for mean first-passage time (MFPT) from one node to another, based on which we deduce an explicit expression for average trapping time (ATT) in terms of the eigenvalues and eigenvectors of the Laplacian matrix associated with the weighted graph, where ATT is the average of MFPTs to the trap over all source nodes. We then further derive a sharp lower bound for the ATT in terms of only the local information of the trap node, which can be obtained in some graphs. Moreover, we deduce the ATT when the trap is distributed uniformly in the whole network. Our results show that network weights play a significant role in the trapping process. To apply our framework, we use the obtained formulas to study random walks on two specific networks: trapping in weighted uncorrelated networks with a deep trap, the weights of which are characterized by a parameter, and Lévy random walks in a connected binary network with a trap distributed uniformly, which can be looked on as random walks on a weighted network. For weighted uncorrelated networks we show that the ATT to any target node depends on the weight parameter, that is, the ATT to any node can change drastically by modifying the parameter, a phenomenon that is in contrast to that for trapping in binary networks. For Lévy random walks in any connected network, by using their equivalence to random walks on a weighted complete network, we obtain the optimal exponent characterizing Lévy random walks, which have the minimal average of ATTs taken over all target nodes.

Random walks on weighted networks

Random walks constitute a fundamental mechanism for a large set of dynamics taking place on networks. In this article, we study random walks on weighted networks with an arbitrary degree distribution, where the weight of an edge between two nodes has a tunable parameter. By using the spectral graph theory, we derive analytical expressions for the stationary distribution, mean first-passage time (MFPT), average trapping time (ATT), and lower bound of the ATT, which is defined as the average MFPT to a given node over every starting point chosen from the stationary distribution. All these results depend on the weight parameter, indicating a significant role of network weights on random walks. For the case of uncorrelated networks, we provide explicit formulas for the stationary distribution as well as ATT. Particularly, for uncorrelated scale-free networks, when the target is placed on a node with the highest degree, we show that ATT can display various scalings of network size, depending also on the same parameter. Our findings could pave a way to delicately controlling random-walk dynamics on complex networks.

Optimal and suboptimal networks for efficient navigation measured by mean-first passage time of random walks

For a random walk on a network, the mean first-passage time from a node i to another node j chosen stochastically, according to the equilibrium distribution of Markov chain representing the random walk is called the Kemeny constant, which is closely related to the navigability on the network. Thus, the configuration of a network that provides optimal or suboptimal navigation efficiency is a question of interest. It has been proved that complete graphs have the exact minimum Kemeny constant over all graphs. In this paper, by using another method we first prove that complete graphs are the optimal networks with a minimum Kemeny constant, which grows linearly with the network size. Then, we study the Kemeny constant of a class of sparse networks that exhibit remarkable scale-free and fractal features as observed in many real-life networks, which cannot be described by complete graphs. To this end, we determine the closed-form solutions to all eigenvalues and their degeneracies of the networks. Employing these eigenvalues, we derive the exact solution to the Kemeny constant, which also behaves linearly with the network size for some particular cases of networks. We further use the eigenvalue spectra to determine the number of spanning trees in the networks under consideration, which is in complete agreement with previously reported results. Our work demonstrates that scale-free and fractal properties are favorable for efficient navigation, which could be considered when designing networks with high navigation efficiency.

Exact calculations of first-passage quantities on recursive networks

We present general methods to exactly calculate mean first-passage quantities on self-similar networks defined recursively. In particular, we calculate the mean first-passage time and the splitting probabilities associated to a source and one or several targets; averaged quantities over a given set of sources (e.g., same-connectivity nodes) are also derived. The exact estimate of such quantities highlights the dependency of first-passage processes with respect to the source-target distance, which has recently revealed to be a key parameter in characterizing transport in complex media. We explicitly perform calculations for different classes of recursive networks [finitely ramified fractals, scale-free (trans)fractals, nonfractals, mixtures between fractals and nonfractals, nondecimable hierarchical graphs] of arbitrary size. Our approach unifies and significantly extends the available results in the field.

Random walks in modular scale-free networks with multiple traps

Extensive empirical investigation has shown that a plethora of real networks synchronously exhibit scale-free and modular structure and it is thus of great importance to uncover the effects of these two striking properties on various dynamical processes occurring on such networks. In this paper, we examine two cases of random walks performed on a class of modular scale-free networks with multiple traps located at several given nodes. We first derive a formula of the mean first-passage time (MFPT) for a general network, which is the mean of the expected time to absorption originating from a specific node, averaged over all nontrap starting nodes. Although the computation is complex, the expression of the formula is exact; moreover, the computational approach and procedure are independent of the number and position of the traps. We then determine analytically the MFPT for the two random walks being considered. The obtained analytical results are in complete agreement with the numerical ones. Our results show that the number and location of traps play an important role in the behavior of the MFPT, since for both cases the MFPT grows as a power-law function of the number of nodes, but their exponents are quite different. We demonstrate that the root of the difference in the behavior of MFPT is attributed to the modular and scale-free topologies of the networks. This work can deepen the understanding of diffusion on networks with modular and scale-free architecture and motivate relevant studies for random walks running on complex random networks with multiple traps.

Close or connected: distance and connectivity effects on transport in networks

We develop an analytical approach that provides the dependence of the mean first-passage time (MFPT) for random walks on complex networks both on the target connectivity and on the source-target distance. Our approach puts forward two strongly different behaviors depending on the type-compact or non compact-of the random walk. In the case of non compact exploration, we show that the MFPT scales linearly with the inverse connectivity of the target and is largely independent of the starting point. On the contrary, in the compact case, the MFPT is controlled by the source-target distance, and we find that unexpectedly the target connectivity becomes irrelevant for remote targets.

Universality classes of first-passage-time distribution in confined media

We study the first-passage time (FPT) distribution to a target site for a random walker evolving in a bounded domain. We show that in the limit of large volume of the confining domain, this distribution falls into universality classes indexed by the walk dimension d(w) and the fractal dimension d(f) of the medium, which have been recently identified previously [Bénichou et al., Nat. Chem. 2, 472 (2010)]. We present in this paper a complete derivation of these universal distributions, discuss extensively the range of applicability of the results, and extend the method to continuous-time random walks. This analysis puts forward the importance of the geometry, and in particular the position of the starting point, in first-passage statistics. Analytical results are validated by numerical simulations, applied to various models of transport in disordered media, which illustrate the universality classes of the FPT distribution.

Facilitated diffusion of proteins on chromatin

We present a theoretical model of facilitated diffusion of proteins in the cell nucleus. This model, which takes into account the successive binding and unbinding events of proteins to DNA, relies on a fractal description of the chromatin which has been recently evidenced experimentally. Facilitated diffusion is shown quantitatively to be favorable for a fast localization of a target locus by a transcription factor and even to enable the minimization of the search time by tuning the affinity of the transcription factor with DNA. This study shows the robustness of the facilitated diffusion mechanism, invoked so far only for linear conformations of DNA.

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.

Random walks on Sierpinski gaskets of different dimensions

We study random walks (RWs) on classical and dual Sierpinski gaskets (SG and DSG), naturally embedded in d-dimensional Euclidian spaces (ESs). For large d the spectral dimension d(s) approaches 2, the marginal RW dimension. In contrast to RW over two-dimensional ES, RWs over SG and DSG show a very rich behavior. First, the time discrete scale invariance leads to logarithmic-periodic (log-periodic) oscillations in the RW properties monitored, which increase in amplitude with d. Second, the asymptotic approach to the theoretically predicted RW power laws is significantly altered depending on d and on the variant of the fractal (SG or DSG) under study. In addition, we discuss the suitability of standard RW properties to determine d(s), a question of great practical relevance.

Determining mean first-passage time on a class of treelike regular fractals

Relatively general techniques for computing mean first-passage time (MFPT) of random walks on networks with a specific property are very useful since a universal method for calculating MFPT on general graphs is not available because of their complexity and diversity. In this paper, we present techniques for explicitly determining the partial mean first-passage time (PMFPT), i.e., the average of MFPTs to a given target averaged over all possible starting positions, and the entire mean first-passage time (EMFPT), which is the average of MFPTs over all pairs of nodes on regular treelike fractals. We describe the processes with a family of regular fractals with treelike structure. The proposed fractals include the T fractal and the Peano basin fractal as their special cases. We provide a formula for MFPT between two directly connected nodes in general trees on the basis of which we derive an exact expression for PMFPT to the central node in the fractals. Moreover, we give a technique for calculating EMFPT, which is based on the relationship between characteristic polynomials of the fractals at different generations and avoids the computation of eigenvalues of the characteristic polynomials. Making use of the proposed methods, we obtain analytically the closed-form solutions to PMFPT and EMFPT on the fractals and show how they scale with the number of nodes. In addition, to exhibit the generality of our methods, we also apply them to the Vicsek fractals and the iterative scale-free fractal tree and recover the results previously obtained.

Effective target arrangement in a deterministic scale-free graph

We study the random-walk problem on a deterministic scale-free network, in the presence of a set of static, identical targets; due to the strong inhomogeneity of the underlying structure the mean first-passage time (MFPT), meant as a measure of transport efficiency, is expected to depend sensitively on the position of targets. We consider several spatial arrangements for targets and we calculate, mainly rigorously, the related MFPT, where the average is taken over all possible starting points and over all possible paths. For all the cases studied, the MFPT asymptotically scales like ∼Nθ, being N the volume of the substrate and θ ranging from 1-log 2/log 3, for central target(s), to 1, for a single peripheral target.

Analytic expression for the mean time to absorption for a random walker on the Sierpinski gasket. II. The eigenvalue spectrum

We continue the study of a particle (atom, molecule) undergoing an unbiased random walk on the Sierpinski gasket, and obtain for the gasket and tower the eigenvalue spectrum of the associated stochastic master equation. Analytic expressions for recurrence relations among the eigenvalues are derived. The recurrence relations obtained are compared with those determined for two Euclidean lattices, the closed chain with an absorbing site and a finite chain with an absorbing site at one end. We check and confirm the internal consistency between the smallest eigenvalue and the mean walklength in each of the cases studied. Attention is drawn to the relevance of the results obtained to a problem of electron transfer in proteins.

Mean first-passage time for random walks on generalized deterministic recursive trees

We describe a technique that allows the exact analytical computation of the mean first passage time (MFPT) for infinite families of trees using their recursive properties. The method is based in the relationship between the MFPT and the eigenvalues of the Laplacian matrix of the trees but avoids their explicit computation. We apply this technique to find the MFPT for a family of generalized deterministic recursive trees. The method, however, can be adapted to other self-similar tree families.

Geometry-controlled kinetics

It has long been appreciated that the transport properties of molecules can control reaction kinetics. This effect can be characterized by the time it takes a diffusing molecule to reach a target-the first-passage time (FPT). Determining the FPT distribution in realistic confined geometries has until now, however, seemed intractable. Here, we calculate this FPT distribution analytically and show that transport processes as varied as regular diffusion, anomalous diffusion, and diffusion in disordered media and fractals, fall into the same universality classes. Beyond the theoretical aspect, this result changes our views on standard reaction kinetics and we introduce the concept of 'geometry-controlled kinetics'. More precisely, we argue that geometry-and in particular the initial distance between reactants in 'compact' systems-can become a key parameter. These findings could help explain the crucial role that the spatial organization of genes has in transcription kinetics, and more generally the impact of geometry on diffusion-limited reactions.

Determining global mean-first-passage time of random walks on Vicsek fractals using eigenvalues of Laplacian matrices

The family of Vicsek fractals is one of the most important and frequently studied regular fractal classes, and it is of considerable interest to understand the dynamical processes on this treelike fractal family. In this paper, we investigate discrete random walks on the Vicsek fractals, with the aim to obtain the exact solutions to the global mean-first-passage time (GMFPT), defined as the average of first-passage time (FPT) between two nodes over the whole family of fractals. Based on the known connections between FPTs, effective resistance, and the eigenvalues of graph Laplacian, we determine implicitly the GMFPT of the Vicsek fractals, which is corroborated by numerical results. The obtained closed-form solution shows that the GMFPT approximately grows as a power-law function with system size (number of all nodes), with the exponent lies between 1 and 2. We then provide both the upper bound and lower bound for GMFPT of general trees, and show that the leading behavior of the upper bound is the square of system size and the dominating scaling of the lower bound varies linearly with system size. We also show that the upper bound can be achieved in linear chains and the lower bound can be reached in star graphs. This study provides a comprehensive understanding of random walks on the Vicsek fractals and general treelike networks.

Explicit determination of mean first-passage time for random walks on deterministic uniform recursive trees

The determination of mean first-passage time (MFPT) for random walks in networks is a theoretical challenge, and is a topic of considerable recent interest within the physics community. In this paper, according to the known connections between MFPT, effective resistance, and the eigenvalues of graph Laplacian, we first study analytically the MFPT between all node pairs of a class of growing treelike networks, which we term deterministic uniform recursive trees (DURTs), since one of its particular cases is a deterministic version of the famous uniform recursive tree. The interesting quantity is determined exactly through the recursive relation of the Laplacian spectra obtained from the special construction of DURTs. The analytical result shows that the MFPT between all couples of nodes in DURTs varies as N ln N for large networks with node number N. Second, we study trapping on a particular network of DURTs, focusing on a special case with the immobile trap positioned at a node having largest degree. We determine exactly the average trapping time (ATT) that is defined as the average of FPT from all nodes to the trap. In contrast to the scaling of the MFPT, the leading behavior of ATT is a linear function of N. Interestingly, we show that the behavior for ATT of the trapping problem is related to the trapping location, which is in comparison with the phenomenon of trapping on fractal T-graph although both networks exhibit tree structure. Finally, we believe that the methods could open the way to exactly calculate the MFPT and ATT in a wide range of deterministic media.

Lévy-type diffusion on one-dimensional directed Cantor graphs

Lévy-type walks with correlated jumps, induced by the topology of the medium, are studied on a class of one-dimensional deterministic graphs built from generalized Cantor and Smith-Volterra-Cantor sets. The particle performs a standard random walk on the sets but is also allowed to move ballistically throughout the empty regions. Using scaling relations and the mapping onto the electric network problem, we obtain the exact values of the scaling exponents for the asymptotic return probability, the resistivity, and the mean-square displacement as a function of the topological parameters of the sets. Interestingly, the system undergoes a transition from superdiffusive to diffusive behavior as a function of the filling of the fractal. The deterministic topology also allows us to discuss the importance of the choice of the initial condition. In particular, we demonstrate that local and average measurements can display different asymptotic behavior. The analytic results are compared to the numerical solution of the master equation of the process.

Distinct scalings for mean first-passage time of random walks on scale-free networks with the same degree sequence

In general, the power-law degree distribution has profound influence on various dynamical processes defined on scale-free networks. In this paper, we will show that power-law degree distribution alone does not suffice to characterize the behavior of trapping problems on scale-free networks, which is an integral major theme of interest for random walks in the presence of an immobile perfect absorber. In order to achieve this goal, we study random walks on a family of one-parameter (denoted by q) scale-free networks with identical degree sequence for the full range of parameter q, in which a trap is located at a fixed site. We obtain analytically or numerically the mean first-passage time (MFPT) for the trapping issue. In the limit of large network order (number of nodes), for the whole class of networks, the MFPT increases asymptotically as a power-law function of network order with the exponent obviously different for different parameter q, which suggests that power-law degree distribution itself is not sufficient to characterize the scaling behavior of MFPT for random walks at least trapping problem, performed on scale-free networks.

Global mean first-passage times of random walks on complex networks

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, 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.

Trapping in scale-free networks with hierarchical organization of modularity

A wide variety of real-life networks share two remarkable generic topological properties: scale-free behavior and modular organization, and it is natural and important to study how these two features affect the dynamical processes taking place on such networks. In this paper, we investigate a simple stochastic process--trapping problem, a random walk with a perfect trap fixed at a given location, performed on a family of hierarchical networks that exhibit simultaneously striking scale-free and modular structure. We focus on a particular case with the immobile trap positioned at the hub node having the largest degree. Using a method based on generating functions, we determine explicitly the mean first-passage time (MFPT) for the trapping problem, which is the mean of the node-to-trap first-passage time over the entire network. The exact expression for the MFPT is calculated through the recurrence relations derived from the special construction of the hierarchical networks. The obtained rigorous formula corroborated by extensive direct numerical calculations exhibits that the MFPT grows algebraically with the network order. Concretely, the MFPT increases as a power-law function of the number of nodes with the exponent much less than 1. We demonstrate that the hierarchical networks under consideration have more efficient structure for transport by diffusion in contrast with other analytically soluble media including some previously studied scale-free networks. We argue that the scale-free and modular topologies are responsible for the high efficiency of the trapping process on the hierarchical networks.

Random walks on deterministic scale-free networks: exact results

We study the random walk problem on a class of deterministic scale-free networks displaying a degree sequence for hubs scaling as a power law with an exponent gamma=log 3/log 2. We find exact results concerning different first-passage phenomena and, in particular, we calculate the probability of first return to the main hub. These results allow to derive the exact analytic expression for the mean time to first reach the main hub, whose leading behavior is given by tau approximately V1-1/gamma, where V denotes the size of the structure, and the mean is over a set of starting points distributed uniformly over all the other sites of the graph. Interestingly, the process turns out to be particularly efficient. We also discuss the thermodynamic limit of the structure and some local topological properties.

Standard random walks and trapping on the Koch network with scale-free behavior and small-world effect

A vast variety of real-life networks display the ubiquitous presence of scale-free phenomenon and small-world effect, both of which play a significant role in the dynamical processes running on networks. Although various dynamical processes have been investigated in scale-free small-world networks, analytical research about random walks on such networks is much less. In this paper, we will study analytically the scaling of the mean first-passage time (MFPT) for random walks on scale-free small-world networks. To this end, we first map the classical Koch fractal to a network, called Koch network. According to this proposed mapping, we present an iterative algorithm for generating the Koch network; based on which we derive closed-form expressions for the relevant topological features, such as degree distribution, clustering coefficient, average path length, and degree correlations. The obtained solutions show that the Koch network exhibits scale-free behavior and small-world effect. Then, we investigate the standard random walks and trapping issue on the Koch network. Through the recurrence relations derived from the structure of the Koch network, we obtain the exact scaling for the MFPT. We show that in the infinite network order limit, the MFPT grows linearly with the number of all nodes in the network. The obtained analytical results are corroborated by direct extensive numerical calculations. In addition, we also determine the scaling efficiency exponents characterizing random walks on the Koch network.

Exact solution for mean first-passage time on a pseudofractal scale-free web

The explicit determinations of the mean first-passage time (MFPT) for trapping problem are limited to some simple structure, e.g., regular lattices and regular geometrical fractals, and determining MFPT for random walks on other media, especially complex real networks, is a theoretical challenge. In this paper, we investigate a simple random walk on the the pseudofractal scale-free web (PSFW) with a perfect trap located at a node with the highest degree, which simultaneously exhibits the remarkable scale-free and small-world properties observed in real networks. We obtain the exact solution for the MFPT that is calculated through the recurrence relations derived from the structure of PSFW. The rigorous solution exhibits that the MFPT approximately increases as a power-law function of the number of nodes, with the exponent less than 1. We confirm the closed-form solution by direct numerical calculations. We show that the structure of PSFW can improve the efficiency of transport by diffusion, compared with some other structure, such as regular lattices, Sierpinski fractals, and T-graph. The analytical method can be applied to other deterministic networks, making the accurate computation of MFPT possible.