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

Flaxman, Abraham; Frieze, Alan; Fenner, Trevor

Internet Math. 2, No. 1, 1-19 (2005).

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.
(See also Lect. Notes Comput. Sci. 2764, 264-274 (2003).)

MSC:

05C80	Random graphs (graph-theoretic aspects)
05C50	Graphs and linear algebra (matrices, eigenvalues, etc.)
68R10	Graph theory (including graph drawing) in computer science

Keywords:

random graph; eigenvalues; adjacency matrix