Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRandom walks with long-range steps generated by functions of Laplacian matrices
52
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this paper, we explore different Markovian random walk strategies on networks with transition probabilities between nodes defined in terms of functions of the Laplacian matrix. We generalize random walk strategies with local information in the Laplacian matrix, that describes the connections of a network, to a dynamics determined by functions of this matrix. The resulting processes are non-local allowing transitions of the random walker from one node to nodes beyond its nearest neighbors. We find that only two types of Laplacian functions are admissible with distinct behaviors for long-range steps in the infinite network limit: type (i) functions generate Brownian motions, type (ii) functions Levy flights. For this asymptotic long-range step behavior only the lowest non-vanishing order of the Laplacian function is relevant, namely first order for type (i), and fractional order for type (ii) functions. In the first part, we discuss spectral properties of the Laplacian matrix and a series of relations that are maintained by a particular type of functions that allow to define random walks on any type of undirected connected networks. Once described general properties, we explore characteristics of random walk strategies that emerge from particular cases with functions defined in terms of exponentials, logarithms and powers of the Laplacian as well as relations of these dynamics with non-local strategies like Levy flights and fractional transport. Finally, we analyze the global capacity of these random walk strategies to explore networks like lattices and trees and different types of random and complex networks.
rate research
Read More
We analyze a random walk strategy on undirected regular networks involving power matrix functions of the type $L^{frac{alpha}{2}}$ where $L$ indicates a `simple Laplacian matrix. We refer such walks to as `Fractional Random Walks with admissible interval $0<alpha leq 2$. We deduce for the Fractional Random Walk probability generating functions (network Greens functions). From these analytical results we establish a generalization of Polyas recurrence theorem for Fractional Random Walks on $d$-dimensional infinite lattices: The Fractional Random Walk is transient for dimensions $d > alpha$ (recurrent for $dleqalpha$) of the lattice. As a consequence for $0<alpha< 1$ the Fractional Random Walk is transient for all lattice dimensions $d=1,2,..$ and in the range $1leqalpha < 2$ for dimensions $dgeq 2$. Finally, for $alpha=2$ Polyas classical recurrence theorem is recovered, namely the walk is transient only for lattice dimensions $dgeq 3$. The generalization of Polyas recurrence theorem remains valid for the class of random walks with Levy flight asymptotics for long-range steps. We also analyze for the Fractional Random Walk mean first passage probabilities, mean first passage times, and global mean first passage times (Kemeny constant). For the infinite 1D lattice (infinite ring) we obtain for the transient regime $0<alpha<1$ closed form expressions for the fractional lattice Greens function matrix containing the escape and ever passage probabilities. The ever passage probabilities fulfill Riesz potential power law decay asymptotic behavior for nodes far from the departure node. The non-locality of the Fractional Random Walk is generated by the non-diagonality of the fractional Laplacian matrix with Levy type heavy tailed inverse power law decay for the probability of long-range moves.
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 Levy 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 Levy random walks in any connected network, by using their equivalence to random walks on a weighted complete network, we obtain the optimal exponent characterizing Levy random walks, which have the minimal average of ATTs taken over all target nodes.
We study the kinetics for the search of an immobile target by randomly moving searchers that detect it only upon encounter. The searchers perform intermittent random walks on a one-dimensional lattice. Each searcher can step on a nearest neighbor site with probability alpha, or go off lattice with probability 1 - alpha to move in a random direction until it lands back on the lattice at a fixed distance L away from the departure point. Considering alpha and L as optimization parameters, we seek to enhance the chances of successful detection by minimizing the probability P_N that the target remains undetected up to the maximal search time N. We show that even in this simple model a number of very efficient search strategies can lead to a decrease of P_N by orders of magnitude upon appropriate choices of alpha and L. We demonstrate that, in general, such optimal intermittent strategies are much more efficient than Brownian searches and are as efficient as search algorithms based on random walks with heavy-tailed Cauchy jump-length distributions. In addition, such intermittent strategies appear to be more advantageous than Levy-based ones in that they lead to more thorough exploration of visited regions in space and thus lend themselves to parallelization of the search processes.
We consider dynamic random walks where the nearest neighbour jump rates are determined by an underlying supercritical contact process in equilibrium. This has previously been studied by den Hollander and dos Santos and den Hollander, dos Santos, Sidoravicius. We show the CLT for such a random walk, valid for all supercritical infection rates for the contact process environment.
With the purpose of explaining recent experimental findings, we study the distribution $A(lambda)$ of distances $lambda$ traversed by a block that slides on an inclined plane and stops due to friction. A simple model in which the friction coefficient $mu$ is a random function of position is considered. The problem of finding $A(lambda)$ is equivalent to a First-Passage-Time problem for a one-dimensional random walk with nonzero drift, whose exact solution is well-known. From the exact solution of this problem we conclude that: a) for inclination angles $theta$ less than $theta_c=tan(av{mu})$ the average traversed distance $av{lambda}$ is finite, and diverges when $theta to theta_c^{-}$ as $av{lambda} sim (theta_c-theta)^{-1}$; b) at the critical angle a power-law distribution of slidings is obtained: $A(lambda) sim lambda^{-3/2}$. Our analytical results are confirmed by numerical simulation, and are in partial agreement with the reported experimental results. We discuss the possible reasons for the remaining discrepancies.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
