Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRandom walk attachment graphs
184
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We consider the random walk attachment graph introduced by Saram{a}ki and Kaski and proposed as a mechanism to explain how behaviour similar to preferential attachment may appear requiring only local knowledge. We show that if the length of the random walk is fixed then the resulting graphs can have properties significantly different from those of preferential attachment graphs, and in particular that in the case where the random walks are of length 1 and each new vertex attaches to a single existing vertex the proportion of vertices which have degree 1 tends to 1, in contrast to preferential attachment models. AMS 2010 Subject Classification: Primary 05C82. Key words and phrases:random graphs; preferential attachment; random walk.
rate research
Read More
We study an evolving spatial network in which sequentially arriving vertices are joined to existing vertices at random according to a rule that combines preference according to degree with preference according to spatial proximity. We investigate phase transitions in graph structure as the relative weighting of these two components of the attachment rule is varied. Previous work of one of the authors showed that when the geometric component is weak, the limiting degree sequence of the resulting graph coincides with that of the standard Barabasi--Albert preferential attachment model. We show that at the other extreme, in the case of a sufficiently strong geometric component, the limiting degree sequence coincides with that of a purely geometric model, the on-line nearest-neighbour graph, which is of interest in its own right and for which we prove some extensions of known results. We also show the presence of an intermediate regime, in which the behaviour differs significantly from both the on-line nearest-neighbour graph and the Barabasi--Albert model; in this regime, we obtain a stretched exponential upper bound on the degree sequence. Our results lend some mathematical support to simulation studies of Manna and Sen, while proving that the power law to stretched exponential phase transition occurs at a different point from the one conjectured by those authors.
We propose a random graph model with preferential attachment rule and emph{edge-step functions} that govern the growth rate of the vertex set. We study the effect of these functions on the empirical degree distribution of these random graphs. More specifically, we prove that when the edge-step function $f$ is a emph{monotone regularly varying function} at infinity, the sequence of graphs associated to it obeys a power-law degree distribution whose exponent is related to the index of regular variation of $f$ at infinity whenever said index is greater than $-1$. When the regularly variation index is less than or equal to $-1$, we show that the proportion of vertices with degree smaller than any given constant goes to $0$ a. s..
Coalescing random walk on a unimodular random rooted graph for which the root has finite expected degree visits each site infinitely often almost surely. A corollary is that an opinion in the voter model on such graphs has infinite expected lifetime. Additionally, we deduce an adaptation of our main theorem that holds uniformly for coalescing random walk on finite random unimodular graphs with degree distribution stochastically dominated by a probability measure with finite mean.
We introduce a new type of random walk where the definition of edge reinforcement is very different from the one in the reinforced random walk models studied so far, and investigate its basic properties, such as null/positive recurrence, transience, and speed. Two basic cases will be dubbed impatient andageing random walks.
We study the evolution of a random walker on a conservative dynamic random environment composed of independent particles performing simple symmetric random walks, generalizing results of [16] to higher dimensions and more general transition kernels without the assumption of uniform ellipticity or nearest-neighbour jumps. Specifically, we obtain a strong law of large numbers, a functional central limit theorem and large deviation estimates for the position of the random walker under the annealed law in a high density regime. The main obstacle is the intrinsic lack of monotonicity in higher-dimensional, non-nearest neighbour settings. Here we develop more general renormalization and renewal schemes that allow us to overcome this issue. As a second application of our methods, we provide an alternative proof of the ballistic behaviour of the front of (the discrete-time version of) the infection model introduced in [23].
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
