Exact calculations of first-passage quantities on recursive networks

First-passage times to a fractal boundary: Local persistence exponent and its log-periodic oscillations

We investigate the statistics of the first-passage time (FPT) to a fractal self-similar boundary of the Koch snowflake. When the starting position is fixed near the absorbing boundary, the FPT distribution exhibits an apparent power-law decay over a broad range of timescales, culminated by an exponential cutoff. By extensive Monte Carlo simulations, we compute the local persistence exponent of the survival probability and reveal its log-periodic oscillations in time due to self-similarity of the boundary. The effect of the starting point on this behavior is analyzed in depth. Theoretical bounds on the survival probability are derived from the analysis of diffusion in a circular sector. Physical rationales for the refined structure of the survival probability are presented.

Random walks on scale-free flowers with stochastic resetting

This study explores the impact of stochastic resetting on the random walk dynamics within scale-free (u,v)-flowers. Utilizing the generating function technique, we develop a recursive relationship for the generating function of the first passage time and establish a connection between the mean first passage time with and without resetting. Our investigation spans multiple scenarios, with the random walker starting from various positions and aiming to reach different target nodes, allowing us to identify the optimal resetting probability that minimizes the mean first passage time for each case. We demonstrate that stochastic resetting significantly improves search efficiency, especially in larger networks. These findings underscore the effectiveness of stochastic resetting as a strategy for optimizing search algorithms in complex networks, offering valuable applications in domains such as biological transport, data networks, and search processes where rapid and efficient exploration is vital.

Controlling and optimizing the transport (search) efficiency with local information on a class of scale-free trees

The scale-free trees are fundamental dynamics networks with extensive applications in material and engineering fields owing to their high reliability and low power consumption characteristics. Controlling and optimizing transport (search) efficiency on scale-free trees has attracted much attention. In this paper, we first introduce degree-dependent weighted tree by assigning each edge (x,y) a weight wxy=(dxdy)θ, with dx and dy being the degree of nodes x and y, and θ being a controllable parameter. Then, we design a parameterized biased random walk strategy with the transition probability depending on the local information (the degree of neighboring nodes) and a parameter θ. Finally, we evaluate analytically the global mean first-passage time, which is an important indicator for measuring the transport (search) efficiency on the underlying networks, and find the interval for parameter θ where transport (search) efficiency can be improved on a class of scale-free trees. We also analyze the (transfinite) walk dimension for our biased random walk on the scale-free trees and find one can obtain arbitrary transfinite walk dimension in an interval by properly tuning the biased parameter θ. The results obtained here would shed light on controlling and optimizing transport (search) efficiency on objects with scale-free tree structures.

First-passage properties of bundled networks

Bundled networks, obtained by attaching a copy of a fiber structure to each node on the base structure, serve as important realistic models for the geometry and dynamics of nontranslationally invariant systems in condensed matter physics. Here, we analyze the first-passage properties, including the mean first-passage time, the mean-trapping time, the global-mean first-passage time (GFPT), and the stationary distribution, of a biased random walk within such networks, in which a random walker moves to a neighbor on base with probability γ and to a neighbor on fiber with probability 1-γ when the walker at a node on base. We reveal the primary properties of both the base and fiber structure, which govern the first-passage characteristics of the bundled network. Explicit expressions between these quantities in the bundled networks and the related quantities in the component structures are presented. GFPT serves as a crucial indicator for evaluating network transport efficiency. Unexpectedly, bases and fibers with similar scaling of GFPT can construct bundled networks exhibiting different scaling behaviors of GFPT. Therefore, bundled networks can be tailored to accommodate specific dynamic property requirements by choosing a suitable base and fiber structure. These findings contribute to advancing the design and optimization of network structures.

Constructing efficient strategies for the process optimization by restart

Optimization of the mean completion time of random processes by restart is a subject of active theoretical research in statistical physics and has long found practical application in computer science. Meanwhile, one of the key issues remains largely unsolved: how to construct a restart strategy for a process whose detailed statistics are unknown to ensure that the expected completion time will reduce? Addressing this query here we propose several constructive criteria for the effectiveness of various protocols of noninstantaneous restart in the mean completion time problem and in the success probability problem. Being expressed in terms of a small number of easily estimated statistical characteristics of the original process (MAD, median completion time, low-order statistical moments of completion time), these criteria allow informed restart decision based on partial information.

From Maximum of Inter-Visit Times to Starving Random Walks

Very recently, a fundamental observable has been introduced and analyzed to quantify the exploration of random walks: the time τ_{k} required for a random walk to find a site that it never visited previously, when the walk has already visited k distinct sites. Here, we tackle the natural issue of the statistics of M_{n}, the longest duration out of τ_{0},…,τ_{n-1}. This problem belongs to the active field of extreme value statistics, with the difficulty that the random variables τ_{k} are both correlated and nonidentically distributed. Beyond this fundamental aspect, we show that the asymptotic determination of the statistics of M_{n} finds explicit applications in foraging theory and allows us to solve the open d-dimensional starving random walk problem, in which each site of a lattice initially contains one food unit, consumed upon visit by the random walker, which can travel S steps without food before starving. Processes of diverse nature, including regular diffusion, anomalous diffusion, and diffusion in disordered media and fractals, share common properties within the same universality classes.

Optimizing search processes with stochastic resetting on the pseudofractal scale-free web

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.

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

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.

Exact results for the first-passage properties in a class of fractal networks

In this work, we consider a class of recursively grown fractal networks G_n(t) whose topology is controlled by two integer parameters, t and n. We first analyse the structural properties of G_n(t) (including fractal dimension, modularity, and clustering coefficient), and then we move to its transport properties. The latter are studied in terms of first-passage quantities (including the mean trapping time, the global mean first-passage time, and Kemeny's constant), and we highlight that their asymptotic behavior is controlled by the network's size and diameter. Remarkably, if we tune n (or, analogously, t) while keeping the network size fixed, as n increases (t decreases) the network gets more and more clustered and modular while its diameter is reduced, implying, ultimately, a better transport performance. The connection between this class of networks and models for polymer architectures is also discussed.

Topology-dependent density optima for efficient simultaneous network exploration

A random search process in a networked environment is governed by the time it takes to visit every node, termed the cover time. Often, a networked process does not proceed in isolation but competes with many instances of itself within the same environment. A key unanswered question is how to optimize this process: How many concurrent searchers can a topology support before the benefits of parallelism are outweighed by competition for space? Here, we introduce the searcher-averaged parallel cover time (APCT) to quantify these economies of scale. We show that the APCT of the networked symmetric exclusion process is optimized at a searcher density that is well predicted by the spectral gap. Furthermore, we find that nonequilibrium processes, realized through the addition of bias, can support significantly increased density optima. Our results suggest alternative hybrid strategies of serial and parallel search for efficient information gathering in social interaction and biological transport networks.

Analysis of fluctuations in the first return times of random walks on regular branched networks

The first return time (FRT) is the time it takes a random walker to first return to its original site, and the global first passage time (GFPT) is the first passage time for a random walker to move from a randomly selected site to a given site. We find that in finite networks, the variance of FRT, Var(FRT), can be expressed as Var(FRT) = 2⟨FRT⟩⟨GFPT⟩ - ⟨FRT⟩² - ⟨FRT⟩, where ⟨·⟩ is the mean of the random variable. Therefore a method of calculating the variance of FRT on general finite networks is presented. We then calculate Var(FRT) and analyze the fluctuation of FRT on regular branched networks (i.e., Cayley tree) by using Var(FRT) and its variant as the metric. We find that the results differ from those in such other networks as Sierpinski gaskets, Vicsek fractals, T-graphs, pseudofractal scale-free webs, (u, v) flowers, and fractal and non-fractal scale-free trees.

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

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

Scaling laws for diffusion on (trans)fractal scale-free networks

Fractal (or transfractal) features are common in real-life networks and are known to influence the dynamic processes taking place in the network itself. Here, we consider a class of scale-free deterministic networks, called (u, v)-flowers, whose topological properties can be controlled by tuning the parameters u and v; in particular, for u > 1, they are fractals endowed with a fractal dimension df, while for u = 1, they are transfractal endowed with a transfractal dimension d̃_f. In this work, we investigate dynamic processes (i.e., random walks) and topological properties (i.e., the Laplacian spectrum) and we show that, under proper conditions, the same scalings (ruled by the related dimensions) emerge for both fractal and transfractal dimensions.

Local orientational mobility in regular hyperbranched polymers

We study the dynamics of local bond orientation in regular hyperbranched polymers modeled by Vicsek fractals. The local dynamics is investigated through the temporal autocorrelation functions of single bonds and the corresponding relaxation forms of the complex dielectric susceptibility. We show that the dynamic behavior of single segments depends on their remoteness from the periphery rather than on the size of the whole macromolecule. Remarkably, the dynamics of the core segments (which are most remote from the periphery) shows a scaling behavior that differs from the dynamics obtained after structural average. We analyze the most relevant processes of single segment motion and provide an analytic approximation for the corresponding relaxation times. Furthermore, we describe an iterative method to calculate the orientational dynamics in the case of very large macromolecular sizes.

Contact Kinetics in Fractal Macromolecules

We consider the kinetics of first contact between two monomers of the same macromolecule. Relying on a fractal description of the macromolecule, we develop an analytical method to compute the mean first contact time for various molecular sizes. In our theoretical description, the non-Markovian feature of monomer motion, arising from the interactions with the other monomers, is captured by accounting for the nonequilibrium conformations of the macromolecule at the very instant of first contact. This analysis reveals a simple scaling relation for the mean first contact time between two monomers, which involves only their equilibrium distance and the spectral dimension of the macromolecule, independently of its microscopic details. Our theoretical predictions are in excellent agreement with numerical stochastic simulations.

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.

Mixed random walks with a trap in scale-free networks including nearest-neighbor and next-nearest-neighbor jumps

Random walks including non-nearest-neighbor jumps appear in many real situations such as the diffusion of adatoms and have found numerous applications including PageRank search algorithm; however, related theoretical results are much less for this dynamical process. In this paper, we present a study of mixed random walks in a family of fractal scale-free networks, where both nearest-neighbor and next-nearest-neighbor jumps are included. We focus on trapping problem in the network family, which is a particular case of random walks with a perfect trap fixed at the central high-degree node. We derive analytical expressions for the average trapping time (ATT), a quantitative indicator measuring the efficiency of the trapping process, by using two different methods, the results of which are consistent with each other. Furthermore, we analytically determine all the eigenvalues and their multiplicities for the fundamental matrix characterizing the dynamical process. Our results show that although next-nearest-neighbor jumps have no effect on the leading scaling of the trapping efficiency, they can strongly affect the prefactor of ATT, providing insight into better understanding of random-walk process in complex systems.

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.

Effects of reciprocity on random walks in weighted networks

It has been recently reported that the reciprocity of real-life weighted networks is very pronounced, however its impact on dynamical processes is poorly understood. In this paper, we study random walks in a scale-free directed weighted network with a trap at the central hub node, where the weight of each directed edge is dominated by a parameter controlling the extent of network reciprocity. We derive two expressions for the mean first passage time (MFPT) to the trap, by using two different techniques, the results of which agree well with each other. We also analytically determine all the eigenvalues as well as their multiplicities for the fundamental matrix of the dynamical process, and show that the largest eigenvalue has an identical dominant scaling as that of the MFPT.We find that the weight parameter has a substantial effect on the MFPT, which behaves as a power-law function of the system size with the power exponent dependent on the parameter, signaling the crucial role of reciprocity in random walks occurring in weighted networks.

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.

Slow encounters of particle pairs in branched structures

On infinite homogeneous structures, two random walkers meet with certainty if and only if the structure is recurrent; i.e., a single random walker returns to its starting point with probability 1. However, on general inhomogeneous structures this property does not hold, and, although a single random walker will certainly return to its starting point, two moving particles may never meet. This striking property has been shown to hold, for instance, on infinite combs. Due to the huge variety of natural phenomena which can be modeled in terms of encounters between two (or more) particles diffusing in comblike structures, it is fundamental to investigate if and, if so, to what extent similar effects may take place in finite structures. By means of numerical simulations we provide evidence that, indeed, even on finite structures, the topological inhomogeneity can qualitatively affect the two-particle problem. In particular, the mean encounter time can be polynomially larger than the time expected from the related one-particle problem.

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.

Characteristic times of biased random walks on complex networks

We consider degree-biased random walkers whose probability to move from a node to one of its neighbors of degree k is proportional to k(α), where α is a tuning parameter. We study both numerically and analytically three types of characteristic times, namely (i) the time the walker needs to come back to the starting node, (ii) the time it takes to visit a given node for the first time, and (iii) the time it takes to visit all the nodes of the network. We consider a large data set of real-world networks and we show that the value of α which minimizes the three characteristic times differs from the value α(min)=-1 analytically found for uncorrelated networks in the mean-field approximation. In addition to this, we found that assortative networks have preferentially a value of α(min) in the range [-1,-0.5], while disassortative networks have α(min) in the range [-0.5,0]. We derive an analytical relation between the degree correlation exponent ν and the optimal bias value α(min), which works well for real-world assortative networks. When only local information is available, degree-biased random walks can guarantee smaller characteristic times than the classical unbiased random walks by means of an appropriate tuning of the motion bias.

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

Origin of the hub spectral dimension in scale-free networks

The return-to-origin probability and the first-passage-time distribution are essential quantities for understanding transport phenomena in diverse systems. The behaviors of these quantities typically depend on the spectral dimension d(s). However, it was recently revealed that in scale-free networks these quantities show a crossover between two power-law regimes characterized by d(s) and the so-called hub spectral dimension d(s)((hub)) due to the heterogeneity of connectivities of each node. To understand the origin of d(s)((hub)) from a theoretical perspective, we study a random walk problem on hierarchical scale-free networks by using the renormalization group (RG) approach. Under the RG transformation, not only the system size but also the degree of each node changes due to the scale-free nature of the degree distribution. We show that the anomalous behavior of random walks involving the hub spectral dimension d(s)((hub)) is induced by the conservation of the power-law degree distribution under the RG transformation.

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.