Book contents
- Frontmatter
- Dedication
- Contents
- Preface
- Possible Course Outlines
- Part I Preliminaries
- Part II Connected Components in Random Graphs
- Part III Small-World Properties of Random Graphs
- 6 Small-World Phenomena in Inhomogeneous Random Graphs
- 7 Small-World Phenomena in Configuration Models
- 8 Small-World Phenomena in Preferential Attachment Models
- Part IV Related Models and Problems
- Appendix: Metric Space Structure of Rooted Graphs
- Glossary
- References
- Index
7 - Small-World Phenomena in Configuration Models
from Part III - Small-World Properties of 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
- Part III Small-World Properties of Random Graphs
- 6 Small-World Phenomena in Inhomogeneous Random Graphs
- 7 Small-World Phenomena in Configuration Models
- 8 Small-World Phenomena in Preferential Attachment Models
- Part IV Related Models and Problems
- Appendix: Metric Space Structure of Rooted Graphs
- Glossary
- References
- Index
Summary
In this chapter we investigate the distance structure of the configuration model by investigating its typical distances and its diameter. We adapt the path-counting techniques in Chapter 6 to the configuration model, and obtain typical distances from the “giant is almost local” proof. To understand the ultra-small distances for infinite-variance degree configuration models, we investigate the generation growth of infinite-mean branching processes. The relation to branching processes informally leads to the power-iteration technique that allows one to deduce typical distance results in random graphs in a relatively straightforward way.
Keywords
- Type
- Chapter
- Information
- Random Graphs and Complex Networks , pp. 289 - 325Publisher: Cambridge University PressPrint publication year: 2024