## 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.)
Full Text: