Book contents
- Frontmatter
- Dedication
- Contents
- Preface
- Possible Course Outlines
- Part I Preliminaries
- Part II Connected Components in Random Graphs
- 3 Connected Components in General Inhomogeneous Random Graphs
- 4 Connected Components in Configuration Models
- 5 Connected Components in Preferential Attachment Models
- Part III Small-World Properties of Random Graphs
- Part IV Related Models and Problems
- Appendix: Metric Space Structure of Rooted Graphs
- Glossary
- References
- Index
5 - Connected Components in Preferential Attachment Models
from Part II - Connected Components in Random Graphs
Published online by Cambridge University Press: 08 February 2024
- Frontmatter
- Dedication
- Contents
- Preface
- Possible Course Outlines
- Part I Preliminaries
- Part II Connected Components in Random Graphs
- 3 Connected Components in General Inhomogeneous Random Graphs
- 4 Connected Components in Configuration Models
- 5 Connected Components in Preferential Attachment Models
- Part III Small-World Properties of Random Graphs
- Part IV Related Models and Problems
- Appendix: Metric Space Structure of Rooted Graphs
- Glossary
- References
- Index
Summary
In this chapter we investigate the connectivity structure of preferential attachment models. We start by discussing an important tool: exchangeable random variables and their distribution described in de Finetti’s Theorem. We apply these results to Pólya urn schemes, which, in turn, we use to describe the distribution of the degrees in preferential attachment models. It turns out that Pólya urn schemes can also be used to describe the local limit of preferential attachment models. A crucial ingredient is the fact that the edges in the Pólya urn representation are conditionally independent, given the appropriate randomness. The resulting local limit is the Pólya point tree, a specific multi-type branching process with continuous types.
Keywords
- Type
- Chapter
- Information
- Random Graphs and Complex Networks , pp. 189 - 242Publisher: Cambridge University PressPrint publication year: 2024