The preferential attachment graph is a random graph formed by adding a new vertex at each time step, with a single edge which points to a vertex selected at random with probability proportional to its degree. Every m steps the most recently added m vertices are contracted into a single vertex, so at time t there are roughly t/m vertices and exactly t edges. This process yields a graph which has been proposed as a simple model of the world wide web [BA99]. For any constant k, let Δ_1 > Δ_2 ≥ ··· ≥ Δ_k be the degrees of the k highest degree vertices. We show that at time t, for any function f with f(t) → ∞ as t → ∞, (t~(1/2))/(f(t)) ≤ Δ_1 ≤ t~(1/2) f(t), and for i = 2, ... , k, (t~(1/2))/(f(t)) ≤ Δ_i ≤ Δ_(i-1) -
展开▼
