Journal articles: 'Vertex Reinforced Random Walk'

1

Pemantle, Robin. "Vertex-reinforced random walk." Probability Theory and Related Fields 92, no. 1 (March 1992): 117–36. http://dx.doi.org/10.1007/bf01205239.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Volkov, Stanislav. "Vertex-reinforced random walk on arbitrary graphs." Annals of Probability 29, no. 1 (February 2001): 66–91. http://dx.doi.org/10.1214/aop/1008956322.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Pemantle, Robin, and Stanislav Volkov. "Vertex-Reinforced Random Walk on Z Has Finite Range." Annals of Probability 27, no. 3 (July 1999): 1368–88. http://dx.doi.org/10.1214/aop/1022677452.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Benaïm, Michel, and Pierre Tarrès. "Dynamics of vertex-reinforced random walks." Annals of Probability 39, no. 6 (November 2011): 2178–223. http://dx.doi.org/10.1214/10-aop609.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Sabot, Christophe, and Pierre Tarrès. "Edge-reinforced random walk, vertex-reinforced jump process and the supersymmetric hyperbolic sigma model." Journal of the European Mathematical Society 17, no. 9 (2015): 2353–78. http://dx.doi.org/10.4171/jems/559.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Dai, Jack Jie. "Some results regarding vertex-reinforced random walks." Statistics & Probability Letters 66, no. 3 (February 2004): 259–66. http://dx.doi.org/10.1016/j.spl.2003.10.017.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Dai, Jack Jie. "A note on vertex-reinforced random walks." Statistics & Probability Letters 62, no. 3 (April 2003): 275–80. http://dx.doi.org/10.1016/s0167-7152(03)00014-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Tarrès, Pierre. "Vertex-reinforced random walk on ℤ eventually gets stuck on five points." Annals of Probability 32, no. 3B (July 2004): 2650–701. http://dx.doi.org/10.1214/009117907000000694.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Chen, Jun, and Gady Kozma. "Vertex-reinforced random walk on with sub-square-root weights is recurrent." Comptes Rendus Mathematique 352, no. 6 (June 2014): 521–24. http://dx.doi.org/10.1016/j.crma.2014.03.019.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Basdevant, Anne-Laure, Bruno Schapira, and Arvind Singh. "Localization of a vertex reinforced random walk on $$\mathbb{Z }$$ with sub-linear weight." Probability Theory and Related Fields 159, no. 1-2 (April 27, 2013): 75–115. http://dx.doi.org/10.1007/s00440-013-0502-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Benaïm, Michel. "Vertex-reinforced random walks and a conjecture of Pemantle." Annals of Probability 25, no. 1 (January 1997): 361–92. http://dx.doi.org/10.1214/aop/1024404292.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Rosales, Rafael A., Fernando P. A. Prado, and Benito Pires. "Vertex reinforced random walks with exponential interaction on complete graphs." Stochastic Processes and their Applications 148 (June 2022): 353–79. http://dx.doi.org/10.1016/j.spa.2022.03.007.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Cohen, Netta, Jonathan Jordan, and Margaritis Voliotis. "Preferential duplication graphs." Journal of Applied Probability 47, no. 2 (June 2010): 572–85. http://dx.doi.org/10.1239/jap/1276784910.

Full text

Abstract:

We consider a preferential duplication model for growing random graphs, extending previous models of duplication graphs by selecting the vertex to be duplicated with probability proportional to its degree. We show that a special case of this model can be analysed using the same stochastic approximation as for vertex-reinforced random walks, and show that ‘trapping’ behaviour can occur, such that the descendants of a particular group of initial vertices come to dominate the graph.

APA, Harvard, Vancouver, ISO, and other styles

14

Cohen, Netta, Jonathan Jordan, and Margaritis Voliotis. "Preferential duplication graphs." Journal of Applied Probability 47, no. 02 (June 2010): 572–85. http://dx.doi.org/10.1017/s0021900200006823.

Full text

Abstract:

We consider a preferential duplication model for growing random graphs, extending previous models of duplication graphs by selecting the vertex to be duplicated with probability proportional to its degree. We show that a special case of this model can be analysed using the same stochastic approximation as for vertex-reinforced random walks, and show that ‘trapping’ behaviour can occur, such that the descendants of a particular group of initial vertices come to dominate the graph.

APA, Harvard, Vancouver, ISO, and other styles

15

Basdevant, Anne-Laure, Bruno Schapira, and Arvind Singh. "Localization on 4 sites for vertex-reinforced random walks on $\mathbb{Z}$." Annals of Probability 42, no. 2 (March 2014): 527–58. http://dx.doi.org/10.1214/12-aop811.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Cotar, Codina, and Debleena Thacker. "Edge- and vertex-reinforced random walks with super-linear reinforcement on infinite graphs." Annals of Probability 45, no. 4 (July 2017): 2655–706. http://dx.doi.org/10.1214/16-aop1122.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Volkov, Stanislav. "Phase Transition in Vertex-Reinforced Random Walks on $${\mathbb{Z}}$$ with Non-linear Reinforcement." Journal of Theoretical Probability 19, no. 3 (October 17, 2006): 691–700. http://dx.doi.org/10.1007/s10959-006-0033-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

ORENSHTEIN, TAL, and IGOR SHINKAR. "Greedy Random Walk." Combinatorics, Probability and Computing 23, no. 2 (November 20, 2013): 269–89. http://dx.doi.org/10.1017/s0963548313000552.

Full text

Abstract:

We study a discrete time self-interacting random process on graphs, which we call greedy random walk. The walker is located initially at some vertex. As time evolves, each vertex maintains the set of adjacent edges touching it that have not yet been crossed by the walker. At each step, the walker, being at some vertex, picks an adjacent edge among the edges that have not traversed thus far according to some (deterministic or randomized) rule. If all the adjacent edges have already been traversed, then an adjacent edge is chosen uniformly at random. After picking an edge the walker jumps along it to the neighbouring vertex. We show that the expected edge cover time of the greedy random walk is linear in the number of edges for certain natural families of graphs. Examples of such graphs include the complete graph, even degree expanders of logarithmic girth, and the hypercube graph. We also show that GRW is transient in$\mathbb{Z}^d$for alld≥ 3.

APA, Harvard, Vancouver, ISO, and other styles

19

Davis, Burgess. "Reinforced random walk." Probability Theory and Related Fields 84, no. 2 (June 1990): 203–29. http://dx.doi.org/10.1007/bf01197845.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

ALON, NOGA, ITAI BENJAMINI, EYAL LUBETZKY, and SASHA SODIN. "NON-BACKTRACKING RANDOM WALKS MIX FASTER." Communications in Contemporary Mathematics 09, no. 04 (August 2007): 585–603. http://dx.doi.org/10.1142/s0219199707002551.

Full text

Abstract:

We compute the mixing rate of a non-backtracking random walk on a regular expander. Using some properties of Chebyshev polynomials of the second kind, we show that this rate may be up to twice as fast as the mixing rate of the simple random walk. The closer the expander is to a Ramanujan graph, the higher the ratio between the above two mixing rates is. As an application, we show that if G is a high-girth regular expander on n vertices, then a typical non-backtracking random walk of length n on G does not visit a vertex more than [Formula: see text] times, and this result is tight. In this sense, the multi-set of visited vertices is analogous to the result of throwing n balls to n bins uniformly, in contrast to the simple random walk on G, which almost surely visits some vertex Ω( log n) times.

APA, Harvard, Vancouver, ISO, and other styles

21

Bach, Eric. "Random bisection and evolutionary walks." Journal of Applied Probability 38, no. 2 (June 2001): 582–96. http://dx.doi.org/10.1239/jap/996986764.

Full text

Abstract:

As models for molecular evolution, immune response, and local search algorithms, various authors have used a stochastic process called the evolutionary walk, which goes as follows. Assign a random number to each vertex of the infinite N-ary tree, and start with a particle on the root. A step of the process consists of searching for a child with a higher number and moving the particle there; if no such child exists, the process stops. The average number of steps in this process is asymptotic, as N → ∞, to log N, a result first proved by Macken and Perelson. This paper relates the evolutionary walk to a process called random bisection, familiar from combinatorics and number theory, which can be thought of as a transformed Poisson process. We first give a thorough treatment of the exact walk length, computing its distribution, moments and moment generating function. Next we show that the walk length is asymptotically normally distributed. We also treat it as a mixture of Poisson random variables and compute the asymptotic distribution of the Poisson parameter. Finally, we show that in an evolutionary walk with uniform vertex numbers, the ‘jumps’, ordered by size, have the same asymptotic distribution as the normalized cycle lengths in a random permutation.

APA, Harvard, Vancouver, ISO, and other styles

22

Bach, Eric. "Random bisection and evolutionary walks." Journal of Applied Probability 38, no. 02 (June 2001): 582–96. http://dx.doi.org/10.1017/s0021900200020052.

Full text

Abstract:

As models for molecular evolution, immune response, and local search algorithms, various authors have used a stochastic process called the evolutionary walk, which goes as follows. Assign a random number to each vertex of the infinite N-ary tree, and start with a particle on the root. A step of the process consists of searching for a child with a higher number and moving the particle there; if no such child exists, the process stops. The average number of steps in this process is asymptotic, as N → ∞, to log N, a result first proved by Macken and Perelson. This paper relates the evolutionary walk to a process called random bisection, familiar from combinatorics and number theory, which can be thought of as a transformed Poisson process. We first give a thorough treatment of the exact walk length, computing its distribution, moments and moment generating function. Next we show that the walk length is asymptotically normally distributed. We also treat it as a mixture of Poisson random variables and compute the asymptotic distribution of the Poisson parameter. Finally, we show that in an evolutionary walk with uniform vertex numbers, the ‘jumps’, ordered by size, have the same asymptotic distribution as the normalized cycle lengths in a random permutation.

APA, Harvard, Vancouver, ISO, and other styles

23

Roberts, Matthew I. "Cover time for branching random walks on regular trees." Journal of Applied Probability 59, no. 1 (February 9, 2022): 256–77. http://dx.doi.org/10.1017/jpr.2021.46.

Full text

Abstract:

AbstractLet T be the regular tree in which every vertex has exactly $d\ge 3$ neighbours. Run a branching random walk on T, in which at each time step every particle gives birth to a random number of children with mean d and finite variance, and each of these children moves independently to a uniformly chosen neighbour of its parent. We show that, starting with one particle at some vertex 0 and conditionally on survival of the process, the time it takes for every vertex within distance r of 0 to be hit by a particle of the branching random walk is $r + ({2}/{\log(3/2)})\log\log r + {\mathrm{o}}(\log\log r)$ .

APA, Harvard, Vancouver, ISO, and other styles

24

Disertori, Margherita, Christophe Sabot, and Pierre Tarrès. "Transience of Edge-Reinforced Random Walk." Communications in Mathematical Physics 339, no. 1 (June 10, 2015): 121–48. http://dx.doi.org/10.1007/s00220-015-2392-y.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Ghosh, Arka P., Reza Rastegar, and Alexander Roitershtein. "On a directionally reinforced random walk." Proceedings of the American Mathematical Society 142, no. 9 (May 19, 2014): 3269–83. http://dx.doi.org/10.1090/s0002-9939-2014-12030-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Hoyer, Peter, and Zhan Yu. "Analysis of lackadaisical quantum walks." Quantum Information and Computation 20, no. 13&14 (November 2020): 1138–53. http://dx.doi.org/10.26421/qic20.13-14-4.

Full text

Abstract:

The lackadaisical quantum walk is a quantum analogue of the lazy random walk obtained by adding a self-loop to each vertex in the graph. We analytically prove that lackadaisical quantum walks can find a unique marked vertex on any regular locally arc-transitive graph with constant success probability quadratically faster than the hitting time. This result proves several speculations and numerical findings in previous work, including the conjectures that the lackadaisical quantum walk finds a unique marked vertex with constant success probability on the torus, cycle, Johnson graphs, and other classes of vertex-transitive graphs. Our proof establishes and uses a relationship between lackadaisical quantum walks and quantum interpolated walks for any regular locally arc-transitive graph.

APA, Harvard, Vancouver, ISO, and other styles

27

DOERR, BENJAMIN, and TOBIAS FRIEDRICH. "Deterministic Random Walks on the Two-Dimensional Grid." Combinatorics, Probability and Computing 18, no. 1-2 (March 2009): 123–44. http://dx.doi.org/10.1017/s0963548308009589.

Full text

Abstract:

Jim Propp's rotor–router model is a deterministic analogue of a random walk on a graph. Instead of distributing chips randomly, each vertex serves its neighbours in a fixed order. We analyse the difference between the Propp machine and random walk on the infinite two-dimensional grid. It is known that, apart from a technicality, independent of the starting configuration, at each time the number of chips on each vertex in the Propp model deviates from the expected number of chips in the random walk model by at most a constant. We show that this constant is approximately 7.8 if all vertices serve their neighbours in clockwise or order, and 7.3 otherwise. This result in particular shows that the order in which the neighbours are served makes a difference. Our analysis also reveals a number of further unexpected properties of the two-dimensional Propp machine.

APA, Harvard, Vancouver, ISO, and other styles

28

Hu, Shengxiang, Bofeng Zhang, Hehe Lv, Furong Chang, Chenyang Zhou, Liangrui Wu, and Guobing Zou. "Improving Network Representation Learning via Dynamic Random Walk, Self-Attention and Vertex Attributes-Driven Laplacian Space Optimization." Entropy 24, no. 9 (August 30, 2022): 1213. http://dx.doi.org/10.3390/e24091213.

Full text

Abstract:

Network data analysis is a crucial method for mining complicated object interactions. In recent years, random walk and neural-language-model-based network representation learning (NRL) approaches have been widely used for network data analysis. However, these NRL approaches suffer from the following deficiencies: firstly, because the random walk procedure is based on symmetric node similarity and fixed probability distribution, the sampled vertices’ sequences may lose local community structure information; secondly, because the feature extraction capacity of the shallow neural language model is limited, they can only extract the local structural features of networks; and thirdly, these approaches require specially designed mechanisms for different downstream tasks to integrate vertex attributes of various types. We conducted an in-depth investigation to address the aforementioned issues and propose a novel general NRL framework called dynamic structure and vertex attribute fusion network embedding, which firstly defines an asymmetric similarity and h-hop dynamic random walk strategy to guide the random walk process to preserve the network’s local community structure in walked vertex sequences. Next, we train a self-attention-based sequence prediction model on the walked vertex sequences to simultaneously learn the vertices’ local and global structural features. Finally, we introduce an attributes-driven Laplacian space optimization to converge the process of structural feature extraction and attribute feature extraction. The proposed approach is exhaustively evaluated by means of node visualization and classification on multiple benchmark datasets, and achieves superior results compared to baseline approaches.

APA, Harvard, Vancouver, ISO, and other styles

29

Guillotin-Plantard, Nadine. "Gillis' Random Walks on Graphs." Journal of Applied Probability 42, no. 01 (March 2005): 295–301. http://dx.doi.org/10.1017/s0021900200000255.

Full text

Abstract:

We consider a random walker on ad-regular graph. Starting from a fixed vertex, the first step is a unit step in any one of theddirections, with common probability 1/dfor each one. At any later step, the random walker moves in any one of the directions, with probabilityqfor a reversal of direction and probabilitypfor any other direction. This model was introduced and first studied by Gillis (1955), in the case when the graph is ad-dimensional square lattice. We prove that the Gillis random walk on ad-regular graph is recurrent if and only if the simple random walk on the graph is recurrent. The Green function of the Gillis random walk will be also given, in terms of that of the simple random walk.

APA, Harvard, Vancouver, ISO, and other styles

30

Bertacchi, Daniela, and Fabio Zucca. "Approximating Critical Parameters of Branching Random Walks." Journal of Applied Probability 46, no. 2 (June 2009): 463–78. http://dx.doi.org/10.1239/jap/1245676100.

Full text

Abstract:

Given a branching random walk on a graph, we consider two kinds of truncations: either by inhibiting the reproduction outside a subset of vertices or by allowing at most m particles per vertex. We investigate the convergence of weak and strong critical parameters of these truncated branching random walks to the analogous parameters of the original branching random walk. As a corollary, we apply our results to the study of the strong critical parameter of a branching random walk restricted to the cluster of a Bernoulli bond percolation.

APA, Harvard, Vancouver, ISO, and other styles

31

Bertacchi, Daniela, and Fabio Zucca. "Approximating Critical Parameters of Branching Random Walks." Journal of Applied Probability 46, no. 02 (June 2009): 463–78. http://dx.doi.org/10.1017/s0021900200005581.

Full text

Abstract:

Given a branching random walk on a graph, we consider two kinds of truncations: either by inhibiting the reproduction outside a subset of vertices or by allowing at most m particles per vertex. We investigate the convergence of weak and strong critical parameters of these truncated branching random walks to the analogous parameters of the original branching random walk. As a corollary, we apply our results to the study of the strong critical parameter of a branching random walk restricted to the cluster of a Bernoulli bond percolation.

APA, Harvard, Vancouver, ISO, and other styles

32

Sarkar, Jyotirmoy, and Saran Ishika Maiti. "Symmetric Random Walks on Regular Tetrahedra, Octahedra, and Hexahedra." Calcutta Statistical Association Bulletin 69, no. 1 (May 2017): 110–28. http://dx.doi.org/10.1177/0008068317695974.

Full text

Abstract:

We study a symmetric random walk on the vertices of three regular polyhedra. Starting from the origin, at each step the random walk moves, independently of all previous moves, to one of the vertices adjacent to the current vertex with equal probability. We find the distributions, or at least the means and the standard deviations, of the number of steps needed (a) to return to origin, (b) to visit all vertices, and (c) to return to origin after visiting all vertices. We also find the distributions of (i) the number of vertices visited before return to origin, (ii) the last vertex visited, and (iii) the number of vertices visited during return to origin after visiting all vertices.

APA, Harvard, Vancouver, ISO, and other styles

33

Guillotin-Plantard, Nadine. "Gillis' Random Walks on Graphs." Journal of Applied Probability 42, no. 1 (March 2005): 295–301. http://dx.doi.org/10.1239/jap/1110381390.

Full text

Abstract:

We consider a random walker on a d-regular graph. Starting from a fixed vertex, the first step is a unit step in any one of the d directions, with common probability 1/d for each one. At any later step, the random walker moves in any one of the directions, with probability q for a reversal of direction and probability p for any other direction. This model was introduced and first studied by Gillis (1955), in the case when the graph is a d-dimensional square lattice. We prove that the Gillis random walk on a d-regular graph is recurrent if and only if the simple random walk on the graph is recurrent. The Green function of the Gillis random walk will be also given, in terms of that of the simple random walk.

APA, Harvard, Vancouver, ISO, and other styles

34

Haslegrave, John, Thomas Sauerwald, and John Sylvester. "Time Dependent Biased Random Walks." ACM Transactions on Algorithms 18, no. 2 (April 30, 2022): 1–30. http://dx.doi.org/10.1145/3498848.

Full text

Abstract:

We study the biased random walk where at each step of a random walk a “controller” can, with a certain small probability, move the walk to an arbitrary neighbour. This model was introduced by Azar et al. [STOC’1992]; we extend their work to the time dependent setting and consider cover times of this walk. We obtain new bounds on the cover and hitting times. Azar et al. conjectured that the controller can increase the stationary probability of a vertex from p to p 1-ε ; while this conjecture is not true in full generality, we propose a best-possible amended version of this conjecture and confirm it for a broad class of graphs. We also consider the problem of computing an optimal strategy for the controller to minimise the cover time and show that for directed graphs determining the cover time is PSPACE -complete.

APA, Harvard, Vancouver, ISO, and other styles

35

Agliari, E., R. Burioni, and G. Uguzzoni. "The true reinforced random walk with bias." New Journal of Physics 14, no. 6 (June 21, 2012): 063027. http://dx.doi.org/10.1088/1367-2630/14/6/063027.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Rolles, Silke W. W. "How edge-reinforced random walk arises naturally." Probability Theory and Related Fields 126, no. 2 (June 1, 2003): 243–60. http://dx.doi.org/10.1007/s00440-003-0260-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Merkl, Franz, and Silke W. W. Rolles. "Edge-reinforced random walk on a ladder." Annals of Probability 33, no. 6 (November 2005): 2051–93. http://dx.doi.org/10.1214/009117905000000396.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Merkl, Franz, and Silke Rolles. "Correlation Inequalities for Edge-Reinforced Random Walk." Electronic Communications in Probability 16 (2011): 753–63. http://dx.doi.org/10.1214/ecp.v16-1683.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Aldous, David. "Hitting times for random walks on vertex-transitive graphs." Mathematical Proceedings of the Cambridge Philosophical Society 106, no. 1 (July 1989): 179–91. http://dx.doi.org/10.1017/s0305004100068079.

Full text

Abstract:

AbstractFor random walks on finite graphs, we record some equalities, inequalities and limit theorems (as the size of graph tends to infinity) which hold for vertex-transitive graphs but not for general regular graphs. The main result is a sharp condition for asymptotic exponentiality of the hitting time to a single vertex. Another result is a lower bound for the coefficient of variation of hitting times. Proofs exploit the complete monotonicity properties of the associated continuous-time walk.

APA, Harvard, Vancouver, ISO, and other styles

40

Nguyen, Tuan-Minh, and Stanislav Volkov. "On a class of random walks in simplexes." Journal of Applied Probability 57, no. 2 (June 2020): 409–28. http://dx.doi.org/10.1017/jpr.2020.19.

Full text

Abstract:

AbstractWe study the limit behaviour of a class of random walk models taking values in the standard d-dimensional ( $d\ge 1$ ) simplex. From an interior point z, the process chooses one of the $d+1$ vertices of the simplex, with probabilities depending on z, and then the particle randomly jumps to a new location z′ on the segment connecting z to the chosen vertex. In some special cases, using properties of the Beta distribution, we prove that the limiting distributions of the Markov chain are Dirichlet. We also consider a related history-dependent random walk model in [0, 1] based on an urn-type scheme. We show that this random walk converges in distribution to an arcsine random variable.

APA, Harvard, Vancouver, ISO, and other styles

41

Durrett, Rick, Harry Kesten, and Vlada Limic. "Once edge-reinforced random walk on a tree." Probability Theory and Related Fields 122, no. 4 (April 1, 2002): 567–92. http://dx.doi.org/10.1007/s004400100179.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Sellke, Thomas. "Recurrence of Reinforced Random Walk on a Ladder." Electronic Journal of Probability 11 (2006): 301–10. http://dx.doi.org/10.1214/ejp.v11-313.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Raimond, Olivier, and Bruno Schapira. "On some generalized reinforced random walk on integers." Electronic Journal of Probability 14 (2009): 1770–89. http://dx.doi.org/10.1214/ejp.v14-685.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Holmes, Mark. "The scaling limit of senile reinforced random walk." Electronic Communications in Probability 14 (2009): 104–15. http://dx.doi.org/10.1214/ecp.v14-1449.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Li, Hongzheng, Yingxia Shao, Junping Du, Bin Cui, and Lei Chen. "An I/O-efficient disk-based graph system for scalable second-order random walk of large graphs." Proceedings of the VLDB Endowment 15, no. 8 (April 2022): 1619–31. http://dx.doi.org/10.14778/3529337.3529346.

Full text

Abstract:

Random walk is widely used in many graph analysis tasks, especially the first-order random walk. However, as a simplification of real-world problems, the first-order random walk is poor at modeling higher-order structures in the data. Recently, second-order random walk-based applications (e.g., Node2vec, Second-order PageRank) have become attractive. Due to the complexity of the second-order random walk models and memory limitations, it is not scalable to run second-order random walk-based applications on a single machine. Existing disk-based graph systems are only friendly to the first-order random walk models and suffer from expensive disk I/Os when executing the second-order random walks. This paper introduces an I/O-efficient disk-based graph system for the scalable second-order random walk of large graphs, called GraSorw. First, to eliminate massive light vertex I/Os, we develop a bi-block execution engine that converts random I/Os into sequential I/Os by applying a new triangular bi-block scheduling strategy, the bucket-based walk management, and the skewed walk storage. Second, to improve the I/O utilization, we design a learning-based block loading model to leverage the advantages of the full-load and on-demand load methods. Finally, we conducted extensive experiments on six large real datasets as well as several synthetic datasets.. The empirical results demonstrate that the end-to-end time cost of popular tasks in GraSorw is reduced by more than one order of magnitude compared to the existing disk-based graph systems.

APA, Harvard, Vancouver, ISO, and other styles

46

Wong, Thomas G. "Unstructured search by random and quantum walk." Quantum Information and Computation 22, no. 1&2 (January 2022): 53–85. http://dx.doi.org/10.26421/qic22.1-2-4.

Full text

Abstract:

The task of finding an entry in an unsorted list of $N$ elements famously takes $O(N)$ queries to an oracle for a classical computer and $O(\sqrt{N})$ queries for a quantum computer using Grover's algorithm. Reformulated as a spatial search problem, this corresponds to searching the complete graph, or all-to-all network, for a marked vertex by querying an oracle. In this tutorial, we derive how discrete- and continuous-time (classical) random walks and quantum walks solve this problem in a thorough and pedagogical manner, providing an accessible introduction to how random and quantum walks can be used to search spatial regions. Some of the results are already known, but many are new. For large $N$, the random walks converge to the same evolution, both taking $N \ln(1/\epsilon)$ time to reach a success probability of $1-\epsilon$. In contrast, the discrete-time quantum walk asymptotically takes $\pi\sqrt{N}/2\sqrt{2}$ timesteps to reach a success probability of $1/2$, while the continuous-time quantum walk takes $\pi\sqrt{N}/2$ time to reach a success probability of $1$.

APA, Harvard, Vancouver, ISO, and other styles

47

Merkl, Franz, and Silke W. W. Rolles. "Edge-reinforced random walk on one-dimensional periodic graphs." Probability Theory and Related Fields 145, no. 3-4 (August 13, 2008): 323–49. http://dx.doi.org/10.1007/s00440-008-0170-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Lovász, Lászlo, and Peter Winkler. "A note on the last new vertex visited by a random walk." Journal of Graph Theory 17, no. 5 (November 1993): 593–96. http://dx.doi.org/10.1002/jgt.3190170505.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

KAIMANOVICH, VADIM A. ""MÜNCHHAUSEN TRICK" AND AMENABILITY OF SELF-SIMILAR GROUPS." International Journal of Algebra and Computation 15, no. 05n06 (October 2005): 907–37. http://dx.doi.org/10.1142/s0218196705002694.

Full text

Abstract:

The structure of a self-similar group G naturally gives rise to a transformation which assigns to any probability measure μ on G and any vertex w in the action tree of the group a new probability measure μw. If the measure μ is self-similar in the sense that μw is a convex combination of μ and the δ-measure at the group identity, then the asymptotic entropy of the random walk (G, μ) vanishes; therefore, the random walk is Liouville and the group G is amenable. We construct self-similar measures on several classes of self-similar groups, including the Grigorchuk group of intermediate growth.

APA, Harvard, Vancouver, ISO, and other styles

50

Melchionna, Andrew. "Stochastic sandpile on a cycle." Journal of Physics A: Mathematical and Theoretical 55, no. 19 (April 12, 2022): 195001. http://dx.doi.org/10.1088/1751-8121/ac61b9.

Full text

Abstract:

Abstract In the stochastic sandpile (SS) model on a graph, particles interact pairwise as follows: if two particles occupy the same vertex, they must each take an independent random walk step with some probability 0 < p < 1 of not moving. These interactions continue until each site has no more than one particle on it. We provide a formal coupling between the SS and the activated random walk models, and we use the coupling to show that for the SS with n particles on the cycle graph Z n , the system stabilizes in O(n 3) time for all initial particle configurations, provided that p(n) tends to 1 sufficiently rapidly as n → ∞.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Vertex Reinforced Random Walk'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles