×

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.

MSC:

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