High degree vertices and eigenvalues in the preferential attachment graph.(English)Zbl 1077.05091

Summary: 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 [A. Barabási and R. Albert, Emergence of scaling in random networks, Science 286, 509–512 (1999)]. For any constant $$k$$, let $$\Delta_1\geq\Delta_2\geq\cdots\geq \Delta_k$$ be the degrees of the $$k$$ highest degree vertices. We show that at time $$t$$, for any function $$f$$ with $$f(t)\to\infty$$ as $$t\to\infty$$, $${t^{1/2}\over f(t)}\leq\Delta_1\leq t^{1/2}f(t)$$, and for $$i= 2,\dots, k$$, $${t^{1/2}\over f(t)}\leq \Delta_i\leq\Delta_{i-1}- {t^{1/2}\over f(t)}$$, 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 $$\lambda_k= (1\pm o(1))\Delta^{1/2}_k$$ whp.