機率研討會

主講者: Prof. K. B. Athreya ( Iowa State Univ.)
講題: Preferential Attachment Random Graphs with General Weight Function
時間: 2008-06-16 (Mon.)  14:10- 16:00
地點:
Abstract: Start with graph $G_0 \equiv \left\{V_1, V_2 \right\} $ 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 \left\{ V_1, V_2, V_3 \right\}$. Let $G_n \equiv \left\{V_1, V_2, . . . , V_{n+2} \right\}$ be the graph after $n$ steps, $n \geq 0$. For each $i$, $1 \leq i \leq n+2$, let $d_i(n)$ be the number of vertices in $G_n$ that $V_i$ is connected to. Now create a new vertex $V_{n+3}$ and attach it to $V_i$ in $G_n$ with probability proportional to $w(d_i(n))$, $1 \leq i \leq n2$ where $w(\cdot)$ is a function form $N \equiv \left\{1, 2, 3, . . .\right\}$ to $(0,\infty)$. In this paper, some results on behavior of the degree sequence $\left\{d_i(n)\right\}_{n \geq 1,i \geq 1}$ and the empirical distribution $\left\{\pi_n(j) \equiv \frac{1}{n} \sum_{i=1}^n I(d_i(n)=j)\right\}_{n \geq 1}$ are derived. Our results indicate that the much discussed power law growth of $d_i(n)$ 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 linear. For example, if $w(x) = cx^2$ then for $i \geq 1$, ${\lim}_{n} di(n)$ exists and is finite w.p. 1 and $\pi_j \equiv \delta_{j1}$. While if $w(x) = cx^p$,$1/2 < p < 1$ then for $i \geq 1$, $d_i(n)$ grows like $(\log n)^q$ where $q = (1 - p)^{-1}$. The main tool used in this paper is an embedding in continuous time pure birth Markov chains.
  || Close window ||