اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدExtensive Condensation in a model of Preferential Attachment with Fitnesses
98
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We introduce a new model of preferential attachment with fitness, and establish a time reversed duality between the model and a system of branching-coalescing particles. Using this duality, we give a clear and concise explanation for the condensation phenomenon, in which unusually fit vertices may obtain abnormally high degree: it arises from a growth-extinction dichotomy within the branching part of the dual. We show further that the condensation is extensive. As the graph grows, unusually fit vertices become, each only for a limited time, neighbouring to a non-vanishing proportion of the current graph.
قيم البحث
اقرأ أيضاً
We extend the work of Antunovi{c}, Mossel and R{a}cz on competing types in preferential attachment models to include cases where the types have different fitnesses, which may be either multiplicative or additive. We will show that, depending on the v
alues of the parameters of the models, there are different possible limiting behaviours depending on the zeros of a certain function. In particular we will show the existence of choices of the parameters where one type is favoured both by having higher fitness and by the type attachment mechanism, but the other type has a positive probability of dominating the network in the limit.
We introduce a model of a preferential attachment based random graph which extends the family of models in which condensation phenomena can occur. Each vertex has an associated uniform random variable which we call its location. Our model evolves in
discrete time by selecting $r$ vertices from the graph with replacement, with probabilities proportional to their degrees plus a constant $alpha$. A new vertex joins the network and attaches to one of these vertices according to a given probability associated to the ranking of their locations. We give conditions for the occurrence of condensation, showing the existence of phase transitions in $alpha$ below which condensation occurs. The condensation in our model differs from that in preferential attachment models with fitness in that the condensation can occur at a random location, that it can be due to a persistent hub, and that there can be more than one point of condensation.
In this paper, a random graph process ${G(t)}_{tgeq 1}$ is studied and its degree sequence is analyzed. Let $(W_t)_{tgeq 1}$ be an i.i.d. sequence. The graph process is defined so that, at each integer time $t$, a new vertex, with $W_t$ edges attache
d to it, is added to the graph. The new edges added at time t are then preferentially connected to older vertices, i.e., conditionally on $G(t-1)$, the probability that a given edge is connected to vertex i is proportional to $d_i(t-1)+delta$, where $d_i(t-1)$ is the degree of vertex $i$ at time $t-1$, independently of the other edges. The main result is that the asymptotical degree sequence for this process is a power law with exponent $tau=min{tau_{W}, tau_{P}}$, where $tau_{W}$ is the power-law exponent of the initial degrees $(W_t)_{tgeq 1}$ and $tau_{P}$ the exponent predicted by pure preferential attachment. This result extends previous work by Cooper and Frieze, which is surveyed.
We consider the degree distributions of preferential attachment random graph models with choice similar to those considered in recent work by Malyshkin and Paquette and Krapivsky and Redner. In these models a new vertex chooses $r$ vertices according
to a preferential rule and connects to the vertex in the selection with the $s$th highest degree. For meek choice, where $s>1$, we show that both double exponential decay of the degree distribution and condensation-like behaviour are possible, and provide a criterion to distinguish between them. For greedy choice, where $s=1$, we confirm that the degree distribution asympotically follows a power law with logarithmic correction when $r=2$ and shows condensation-like behaviour when $r>2$.
We consider a general preferential attachment model, where the probability that a newly arriving vertex connects to an older vertex is proportional to a sublinear function of the indegree of the older vertex at that time. It is well known that the di
stribution of a uniformly chosen vertex converges to a limiting distribution. Depending on the parameters, this model can show power law, but also stretched exponential behaviour. Using Steins method we provide rates of convergence for the total variation distance. Our proof uses the fact that the limiting distribution is the stationary distribution of a Markov chain together with the generator method of Barbour.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
