Expected length of longest construction path in Barabási–Albert Model The Barabási-Albert Model is used for constructing scale-free networks using the preferential attachment technique. The essence, as I understand it, is that nodes are incrementally added to a graph by adding an edge to an existing node selected with probability proportional to the number of edges connecting the node. The algorithm starts on some initial clique, $G$.

Now let's assume that newly added nodes are labelled $0, 1, 2, \ldots$. 
Define a construction path to be a path $l_0l_1l_2\ldots l_n o$ in the generated graph such that $o$ is a node from the initial clique $G$, $l_n&lt;\cdots&lt;l_2&lt;l_1&lt;l_0$ and $l_0$ is maximal. 

Clearly, at one extreme, such paths will be of length $1$, when all newly added nodes connect to one of the initial nodes.
At the other extreme, the length of the path will be equal to the number of nodes added to the graph. Both of these cases are extremely unlikely.

I'm interested in the average case.  Are there any known results about the expected value of the lengths of construction paths? 

NB. Construction path is a name I invented for this question: please let me know if such paths go by another name.
(Answer-in-progress, according to comments.)

I will look at a special case, and then discuss how it relates to the general case. The special case is $m=1$ and $V(G)=\{0\}$ with no edge. The added vertices, in order, are $1,2,\ldots,n$, starting from $1$.

Let $d_{i,n}$ be the degree of vertex $i$ divided by $2n$. So $\sum_{i=0}^n d_{i,n}=1$. Let $l_i$ be the length of the longest path from $i$ to $0$ that visits vertices in decreasing order. (Vertices added after $i$ do not affect decreasing paths starting from $i$, so there is no need for $l_{i,n}$.) Both $d_{i,n-1}$ and $l_i$ are random variables. The generating model for these variables is how you'd expect: Once we fixed their values for $n-1$, we pick a number $k_n$ from $\{0,\ldots,n-1\}$ according to the probabilities $d_{i,n-1}$, and compute $d_{i,n}$ and $l_n$ as if we added edge $nk_n$.

We have that $l_n=1+l_{k_n}$, where $k_n$ is a random variable drawn from $\{0,\ldots,n-1\}$ according to the distribution given by $d_{k,n-1}$. In other words, $l_n=1+\sum_{i\lt n}[k_n=i]l_i$ and $\mathbb{E}[l_n]=1+\sum_{i\lt n}d_{i,n}\mathbb{E}[l_i]$. (The independence here is a bit tricky. In the comment on the post I said it does not hold, but I think it does. The trick is to think of this as a stratified generative model, such that the choice of $k_n$ is independent from $l_i$, but drawn from a certain distribution.)

Let's assume, without proof for now, that $d_{i,n}$ depends on $i$ as $\Theta(i^c)$ for some constant $c$.

Now, let's assume $\mathbb{E}[l_n]=O(f(n))$, and see what properties should $f(n)$ have. According to the recurrence on $\mathbb{E}[l_n]$, we should have that
$$
\sum_{i=0}^{n-1} i^c f(i) \Big/ \sum_{i=0}^{n-1} i^c = O(f(n))
$$
In the continuous approximation, this is
$$
\int_1^n x^c f(x) \,dx = O(n^{c+1}\cdot f(n))
$$
One function that has this property is $f(n)=\log n$.

But, does $d_{i,n}$ grow like $i^c$ (for fixed $n$)?

When $m=1$, we can write a recurrence on vertex degrees. The arc $ni$ occurs with probability $d_{i,n-1}$, so $$d_{i,n}=d_{i,n-1}\frac{2(n-1)d_{i,n-1}+1}{2n}+(1-d_{i,n-1})\frac{2(n-1)d_{i,n-1}}{2n}=d_{i,n-1}\Bigl(1-\frac{1}{2n}\Bigr)$$ The border conditions are $d_{n,n}=1/2n$ and $d_{0,1}=d_{1,1}=1$. Now apply linearity of expectation and approximate $\sum_k\log\Bigl(1-\frac{1}{2k}\Bigr)$ with an integral. Alternatively, note that $d_{i,n}/d_{i-1,n}=d_{i,i}/d_{i-1,i}=(i-1)/(i-1/2)$, so $d_{i,n}$ is roughly $\Gamma(n)/\Gamma(n+1/2)$.

Both approaches lead to $\mathbb{E}[d_{i,n}]=\Theta(i^{-(1/2)})$.

For $m=2$, you draw two variables $k_n$ and $k'_n$ from $\{0,\ldots,n-1\}$ according to $d_{i,n}$, and we keep just the maximum. This is like picking just one variable, $\max\{k_n,k'_n\}$, but from a different distribution. The question is if this distribution is still $\Theta(i^c)$ for some (other) $c$. Let $d^{(2)}_{i,n}$ be this distribution. We have, dropping the $n$ subscript, $d^{(2)}_i=2\sum_{j=0}^i d_i d_j + d_i^2$. So, $d^{(2)}_i=\Theta(1/i)$. In fact, $d^{(2m)}_i=2\sum_{j=0}^i d^{(m)}_i d^{(m)}_j + {d^{(m)}_i}^2$. Again based only on some quick-and-dirty calculations, I believe that for $m\gt 2$ we have $d^{(m)}_i=\Theta((\log i)^{cm}/i)$, which would seem to say that the $O(\log n)$ bound on $\mathbb{E}[l_n]$ doesn't work anymore.

The only thing that matters about the seed graph is how many edges it has. I didn't look at how this affects the answer, but, again, it cannot increase the expected length.