<p>(Answer-in-progress, according to comments.)</p>

<p>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$.</p>

<p>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$.</p>

<p>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.)</p>

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

<p>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$.</p>

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

<p>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)$.</p>

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

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-11-27T19:10:48.097Z
Thanks. It'll see what I can make of this. I think for large graphs the seed graph should not matter. Ultimately, it is not so interesting for me, so it could be any small clique (such as the one you assume).
Dave Clarke
CC BY-SA 3.0
2014-11-28T22:43:52.660Z
I will not have time next week to turn this into a proper answer. Unless someone disagrees, I will remove it tomorrow, because it's more confusing than clarifying the way it is now.
Radu GRIGore
CC BY-SA 3.0
2014-11-29T16:02:10.993Z
Please don't delete the answer. It's the best thing I have to work with for now. It is very useful.
Dave Clarke
CC BY-SA 3.0
2014-11-27T18:17:55.093Z
2014-11-28T10:20:39.860Z
2014-11-28T10:20:39.860Z
Radu GRIGore
<p>The <a href="http://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model" rel="nofollow">Barabási-Albert Model</a> 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$.</p>

<p>Now let's assume that newly added nodes are labelled $0, 1, 2, \ldots$. 
Define a <em>construction path</em> 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. </p>

<p>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.</p>

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

<p>NB. Construction path is a name I invented for this question: please let me know if such paths go by another name.</p>

CC BY-SA 3.0
2014-11-27T12:20:10.320Z
I did some back-of-the-envelope calculations and got that $O(\log n)$ would be an upper bound: First, an upper bound for $m=1$ is also an upper bound for $m\gt1$. Second, degree of node $i$ is proportional to $1/\sqrt{i}$. Third, conjecture that the dependence between path length and degrees isn't too strong (shabby step!). Fourth, prove the bound $O(\log n)$ by induction. I could elaborate, but, there's some serious shabbiness in step 3 that I might not be able to fix, _and_ you might not be happy with $O(\log n)$.
Radu GRIGore
CC BY-SA 3.0
2014-11-27T14:33:40.937Z
@RaduGRIGore: I guestimated $O(\log n)$ ... that would make me happy. Correctness of the derivation would make me happy too. Feel free to add your calculations as an "answer-in-progress".
Dave Clarke
CC BY-SA 3.0
2014-11-27T17:24:21.337Z
You might check out chapters 3 and 7 of Chung and Lu (http://www.math.ucsd.edu/~fan/complex/). I don't have a copy on me right now, but I imagine their rigorous analysis of the diameter and average distance might be of some use. (Your question is slightly different, since you are asking for average distance from the seed graph, whereas, if I recall correctly, they study the average over all pairs of vertices. But their techniques might be useful.)
Joshua Grochow
CC BY-SA 3.0
2014-11-27T17:37:41.013Z
@JoshuaGrochow: Thanks for the reference. The seed graph is not so important, so perhaps their analysis will be useful.
Dave Clarke
<graph-theory><graph-algorithms><random-graphs>
Expected length of longest construction path in Barabási–Albert Model
Dave Clarke
# Expected length of longest construction path in Barabási–Albert Model

(Asked by: username_0 on 2014-11-26)

The [Barabási-Albert Model](http://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_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<\cdots

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.

**Tags:** graph-theory, graph-algorithms, random-graphs
> **Comments:**
> **username_1**: I did some back-of-the-envelope calculations and got that $O(\log n)$ would be an upper bound: First, an upper bound for $m=1$ is also an upper bound for $m\gt1$. Second, degree of node $i$ is proportional to $1/\sqrt{i}$. Third, conjecture that the dependence between path length and degrees isn't too strong (shabby step!). Fourth, prove the bound $O(\log n)$ by induction. I could elaborate, but, there's some serious shabbiness in step 3 that I might not be able to fix, _and_ you might not be happy with $O(\log n)$.  
> **username_0**: @RaduGRIGore: I guestimated $O(\log n)$ ... that would make me happy. Correctness of the derivation would make me happy too. Feel free to add your calculations as an "answer-in-progress".  
> **username_2**: You might check out chapters 3 and 7 of Chung and Lu (http://www.math.ucsd.edu/~fan/complex/). I don't have a copy on me right now, but I imagine their rigorous analysis of the diameter and average distance might be of some use. (Your question is slightly different, since you are asking for average distance from the seed graph, whereas, if I recall correctly, they study the average over all pairs of vertices. But their techniques might be useful.)  
> **username_0**: @JoshuaGrochow: Thanks for the reference. The seed graph is not so important, so perhaps their analysis will be useful.  

---

## 1 answers

### Answer by username_1 on 2014-11-27. Score: 2

(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.

> **Comments:**
> **username_0**: Thanks. It'll see what I can make of this. I think for large graphs the seed graph should not matter. Ultimately, it is not so interesting for me, so it could be any small clique (such as the one you assume).  
> **username_1**: I will not have time next week to turn this into a proper answer. Unless someone disagrees, I will remove it tomorrow, because it's more confusing than clarifying the way it is now.  
> **username_0**: Please don't delete the answer. It's the best thing I have to work with for now. It is very useful.  

---

