Artículos de revistas: "Vertex Reinforced Random Walk"

1

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

2

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

3

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

4

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

5

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

6

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

7

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

8

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

9

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

10

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

11

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

12

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

13

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

14

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

15

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

16

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

17

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

18

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

19

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

20

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

21

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

22

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

23

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

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

24

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

25

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

26

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

27

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

28

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

29

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

30

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

31

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

32

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

33

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

34

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

35

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

36

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

37

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

38

Merkl, Franz y 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.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

39

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

40

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

41

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

43

Raimond, Olivier y 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.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

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.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

45

Li, Hongzheng, Yingxia Shao, Junping Du, Bin Cui y 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, n.º 8 (abril de 2022): 1619–31. http://dx.doi.org/10.14778/3529337.3529346.

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

46

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

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

47

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

48

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

49

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

50

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

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

Artículos de revistas sobre el tema "Vertex Reinforced Random Walk"

Crea una cita precisa en los estilos APA, MLA, Chicago, Harvard y otros