Do you want to publish a course? Click here

On recurrence of random walks with long-range steps generated by fractional Laplacian matrices on regular networks and simple cubic lattices

58   0   0.0 ( 0 )
 Added by Thomas Michelitsch
 Publication date 2017
  fields Physics
and research's language is English




Ask ChatGPT about the research

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.



rate research

Read More

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.
In this paper, we study nonlocal random walk strategies generated with the fractional Laplacian matrix of directed networks. We present a general approach to analyzing these strategies by defining the dynamics as a discrete-time Markovian process with transition probabilities between nodes expressed in terms of powers of the Laplacian matrix. We analyze the elements of the transition matrices and their respective eigenvalues and eigenvectors, the mean first passage times and global times to characterize the random walk strategies. We apply this approach to the study of particular local and nonlocal ergodic random walks on different directed networks; we explore circulant networks, the biased transport on rings and the dynamics on random networks. We study the efficiency of a fractional random walker with bias on these structures. Effects of ergodicity loss which occur when a directed network is not any more strongly connected are also discussed.
We consider reversible random walks in random environment obtained from symmetric long--range jump rates on a random point process. We prove almost sure transience and recurrence results under suitable assumptions on the point process and the jump rate function. For recurrent models we obtain almost sure estimates on effective resistances in finite boxes. For transient models we construct explicit fluxes with finite energy on the associated electrical network.
In recent years, protocols that are based on the properties of random walks on graphs have found many applications in communication and information networks, such as wireless networks, peer-to-peer networks and the Web. For wireless networks (and other networks), graphs are actually not the correct model of the communication; instead hyper-graphs better capture the communication over a wireless shared channel. Motivated by this example, we study in this paper random walks on hyper-graphs. First, we formalize the random walk process on hyper-graphs and generalize key notions from random walks on graphs. We then give the novel definition of radio cover time, namely, the expected time of a random walk to be heard (as opposed to visit) by all nodes. We then provide some basic bounds on the radio cover, in particular, we show that while on graphs the radio cover time is O(mn), in hyper-graphs it is O(mnr) where n, m and r are the number of nodes, the number of edges and the rank of the hyper-graph, respectively. In addition, we define radio hitting times and give a polynomial algorithm to compute them. We conclude the paper with results on specific hyper-graphs that model wireless networks in one and two dimensions.
258 - N. Lemke , I. A. Campbell 2011
Diffusion on a diluted hypercube has been proposed as a model for glassy relaxation and is an example of the more general class of stochastic processes on graphs. In this article we determine numerically through large scale simulations the eigenvalue spectra for this stochastic process and calculate explicitly the time evolution for the autocorrelation function and for the return probability, all at criticality, with hypercube dimensions $N$ up to N=28. We show that at long times both relaxation functions can be described by stretched exponentials with exponent 1/3 and a characteristic relaxation time which grows exponentially with dimension $N$. The numerical eigenvalue spectra are consistent with analytic predictions for a generic sparse network model.
comments
Fetching comments Fetching comments
Sign in to be able to follow your search criteria
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا