I am interested to know the structure of random graphs generated by the 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.

  • 1
    $\begingroup$ This is not question. This is well-studied model (except the degree constraint). You should google the results by yourself. $\endgroup$ – Bangye Jan 10 '14 at 7:28
  • 1
    $\begingroup$ 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. $\endgroup$ – Arindam Pal Jan 10 '14 at 8:56
  • $\begingroup$ @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! $\endgroup$ – Yonatan N Jan 10 '14 at 9:04
  • $\begingroup$ Such studies usually investigate the features of random graphs in the asymptotic sense. Adding a constant bound on the degree does not make sense. $\endgroup$ – Bangye Jan 10 '14 at 10:19
  • 1
    $\begingroup$ @Bangye: Note that it makes a lot of sense to study, e.g., asymptotics of random regular graphs of a constant degree. $\endgroup$ – Jukka Suomela Jan 10 '14 at 10:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.