Book contents
- Frontmatter
- Dedication
- Contents
- Preface
- Acknowledgments
- Conventions/Notations
- Part I Preliminaries
- Part II Erdős–Rényi–Gilbert Model
- 3 Uniform and Binomial Random Graphs
- 4 Evolution
- 5 Vertex Degrees
- 6 Connectivity
- 7 Small Subgraphs
- 8 Large Subgraphs
- 9 Extreme Characteristics
- Part III Modeling Complex Networks
- References
- Author Index
- Subject Index
7 - Small Subgraphs
from Part II - Erdős–Rényi–Gilbert Model
Published online by Cambridge University Press: 02 March 2023
- Frontmatter
- Dedication
- Contents
- Preface
- Acknowledgments
- Conventions/Notations
- Part I Preliminaries
- Part II Erdős–Rényi–Gilbert Model
- 3 Uniform and Binomial Random Graphs
- 4 Evolution
- 5 Vertex Degrees
- 6 Connectivity
- 7 Small Subgraphs
- 8 Large Subgraphs
- 9 Extreme Characteristics
- Part III Modeling Complex Networks
- References
- Author Index
- Subject Index
Summary
In this chapter, we see how many random edges are required to have a particular fixed size subgraph w.h.p. In addition, we will consider the distribution of the number of copies of strictly balanced subgraphs. From these general results, one can deduce thresholds for small trees, stars, cliques, bipartite cliques, and many other small subgraphs which play an important role in the analysis of the properties not only of classic random graphs but also in the interpretation of characteristic features of real-world networks. Computing the frequency of small subgraphs is a fundamental problem in network analysis, used across diverse domains: bioinformatics, social sciences, and infrastructure networks studies.
- Type
- Chapter
- Information
- Random Graphs and Networks: A First Course , pp. 85 - 92Publisher: Cambridge University PressPrint publication year: 2023