Book contents
- Frontmatter
- Dedication
- Contents
- Preface
- Possible Course Outlines
- Part I Preliminaries
- 1 Introduction and Preliminaries
- 2 Local Convergence of Random Graphs
- Part II Connected Components in Random Graphs
- Part III Small-World Properties of Random Graphs
- Part IV Related Models and Problems
- Appendix: Metric Space Structure of Rooted Graphs
- Glossary
- References
- Index
2 - Local Convergence of Random Graphs
from Part I - Preliminaries
Published online by Cambridge University Press: 08 February 2024
- Frontmatter
- Dedication
- Contents
- Preface
- Possible Course Outlines
- Part I Preliminaries
- 1 Introduction and Preliminaries
- 2 Local Convergence of Random Graphs
- Part II Connected Components in Random Graphs
- 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 discuss local convergence, which describes the intuitive notion that a finite graph, seen from the perspective of a typical vertex, looks like a certain limiting graph. Local convergence plays a profound role in random graph theory. We give general definitions of local convergence in several probabilistic senses. We then show that local convergence in its various forms is equivalent to the appropriate convergence of subgraph counts. We continue by discussing several implications of local convergence, concerning local neighborhoods, clustering, assortativity, and PageRank. We further investigate the relation between local convergence and the size of the giant, making the statement that the giant is “almost local” precise.
Keywords
- Type
- Chapter
- Information
- Random Graphs and Complex Networks , pp. 48 - 94Publisher: Cambridge University PressPrint publication year: 2024