<p>I am interested to know the structure of random graphs generated by the <a href="http://en.wikipedia.org/wiki/Preferential_attachment" rel="nofollow">preferential attachment</a> model with degree bounds. Specifically, when a vertex is chosen with a probability proportional to its degree, the edge is added if and only if the degree of the vertex does not exceed some upper bound.</p>

<p>What will be the vertex degree distribution of such a graph? What will be the size of the largest (giant) component, diameter and the average path length? Any reference will be highly appreciated.</p>

CC BY-SA 3.0
2014-01-10T07:28:19.743Z
This is not question. This is  well-studied model (except the degree constraint). You should google the results by yourself.
Bangye
CC BY-SA 3.0
2014-01-10T08:56:53.507Z
I want to know the effect of putting a bound on the degree in the preferential attachment model. I didn't find any papers on Google. If you know any, please let me know.
Arindam Pal
CC BY-SA 3.0
2014-01-10T09:04:44.030Z
@Bangye, it's not at all clear (and probably false) that results without the degree constraint will carry over. Note that a degree constraint of 2 limits the graph to independent path/cycle components!
Yonatan N
CC BY-SA 3.0
2014-01-10T10:19:46.363Z
Such studies usually investigate the features of random graphs in the asymptotic sense. Adding a constant bound on the degree does not make sense.
Bangye
CC BY-SA 3.0
2014-01-10T10:53:04.647Z
@Bangye: Note that it makes a lot of sense to study, e.g., asymptotics of random regular graphs of a constant degree.
Jukka Suomela
<graph-theory><randomized-algorithms>
Generating random graphs using the preferential attachment model with degree bounds
Arindam Pal
# Generating random graphs using the preferential attachment model with degree bounds

(Asked by: username_0 on 2014-01-10)

I am interested to know the structure of random graphs generated by the [preferential attachment](http://en.wikipedia.org/wiki/Preferential_attachment) model with degree bounds. Specifically, when a vertex is chosen with a probability proportional to its degree, the edge is added if and only if the degree of the vertex does not exceed some upper bound.

What will be the vertex degree distribution of such a graph? What will be the size of the largest (giant) component, diameter and the average path length? Any reference will be highly appreciated.

**Tags:** graph-theory, randomized-algorithms

> **Comments:**
> **username_1**: This is not question. This is  well-studied model (except the degree constraint). You should google the results by yourself.  
> **username_0**: I want to know the effect of putting a bound on the degree in the preferential attachment model. I didn't find any papers on Google. If you know any, please let me know.  
> **username_2**: @username_1, it's not at all clear (and probably false) that results without the degree constraint will carry over. Note that a degree constraint of 2 limits the graph to independent path/cycle components!  
> **username_1**: Such studies usually investigate the features of random graphs in the asymptotic sense. Adding a constant bound on the degree does not make sense.  
> **username_3**: @username_1: Note that it makes a lot of sense to study, e.g., asymptotics of random regular graphs of a constant degree.  

---

## 0 answers

