Preferential attachment random graphs with general weight function. (English) Zbl 1206.68225

Summary: Start with graph \(G_0 \equiv \{V_1,V_2\}\) with one edge connecting the two vertices \(V_1, V_2\). Now create a new vertex \(V_3\) and attach it (i.e., add an edge) to \(V_1\) or \(V_2\) with equal probability. Set \(G_1 \equiv \{V_1,V_2,V_3\}\). Let \(G_n \equiv \{V_1,V_2,\ldots,V_{n+2}\}\) be the graph after \(n\) steps, \(n \geq 0\). For each \(i, 1 \leq i \leq n+2\), let \(d_n(i)\) be the number of vertices in \(G_n\) to which \(V_i\) is connected. Now create a new vertex \(V_{n+3}\) and attach it to \(V_i\) in \(G_n\) with probability proportional to \(w(d_n(i)), 1 \leq i \leq n+2\), where \(w(\cdot)\) is a function from \(N \equiv \{1,2,3,\ldots\}\) to \((0,\infty)\). In this paper, some results on behavior of the degree sequence \(\{d_n(i)\}_{n\geq 1,i\geq 1}\) and the empirical distribution \(\{\pi_n(j) \equiv \frac{1}{n} \sum^n_{i=1} I(d_n(i) = j)\}_{n\geq 1}\) are derived. Our results indicate that the much discussed power-law growth of \(d_n(i)\) and power law decay of \(\pi(j) \equiv \lim_{n\to\infty} \pi_n(j)\) hold essentially only when the weight function \(w(\cdot)\) is asymptotically linear. For example, if \(w(x) = cx^2\) then for \(i\geq 1, \lim_n d_n(i)\) exists and is finite with probability (w.p.)1 and \(\pi(j) \equiv \delta_{j1}\), and if \(w(x) = cx^p, 1/2 <p < 1\) then for \(i \geq 1, d_n(i)\) grows like \((\log n)^q\) where \(q=(1-p)^{-1}\). The main tool used in this paper is an embedding in continuous time of pure birth Markov chains.


68R10 Graph theory (including graph drawing) in computer science
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Full Text: DOI Euclid