Influences of degree inhomogeneity on average path length and random walks in disassortative scale-free networks

FAST SOLVER FOR DIFFUSIVE TRANSPORT TIMES ON DYNAMIC INTRACELLULAR NETWORKS

The transport of particles in cells is influenced by the properties of intracellular networks they traverse while searching for localized target regions or reaction partners. Moreover, given the rapid turnover in many intracellular structures, it is crucial to understand how temporal changes in the network structure affect diffusive transport. In this work, we use network theory to characterize complex intracellular biological environments across scales. We develop an efficient computational method to compute the mean first passage times for simulating a particle diffusing along two-dimensional planar networks extracted from fluorescence microscopy imaging. We first benchmark this methodology in the context of synthetic networks, and subsequently apply it to live-cell data from endoplasmic reticulum tubular 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.

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.

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.

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.

Exact encounter times for many random walkers on regular and complex networks

The exact mean time between encounters of a given particle in a system consisting of many particles undergoing random walks in discrete time is calculated, on both regular and complex networks. Analytical results are obtained both for independent walkers, where any number of walkers can occupy the same site, and for walkers with an exclusion interaction, when no site can contain more than one walker. These analytical results are then compared with numerical simulations, showing very good agreement.

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.