High Degree Vertices and Eigenvalues in the Preferential Attachment Graph
Abraham D. Flaxman, ALAN M. FRIEZE, Trevor I. Fenner · Lecture notes in computer science · 2003
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 [Barabási and Albert 99]. 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 ƒ with ƒ(_t_)→ ∞ as , and for , with high probability (whp). We use this to show that at time t the largest k eigenvalues of the adjacency matrix of this graph have λ k = (1 ± _o_(1))Δ k 1/2 whp.