Networks surround us, from social networks to protein–protein interaction networks within the cells of our bodies. The theory of random graphs provides a necessary framework for understanding their structure and development. This text provides an accessible introduction to this rapidly expanding subject. It covers all the basic features of random graphs – component structure, matchings and Hamilton cycles, connectivity and chromatic number – before discussing models of real-world networks, including intersection graphs, preferential attachment graphs and small-world models. Based on the authors' own teaching experience, it can be used as a textbook for a one-semester course on random graphs and networks at advanced undergraduate or graduate level. The text includes numerous exercises, with a particular focus on developing students' skills in asymptotic analysis. More challenging problems are accompanied by hints or suggestions for further reading.
Author(s): Alan Frieze, Michał Karoński
Edition: 1
Publisher: Cambridge University Press
Year: 2023
Language: English
Pages: 232
City: Cambridge, UK
Tags: Algebra; Combinatorics; Graph Theory; Random Graphs; Erdős–Rényi–Gilbert Model; Modeling Complex Networks
Preface page ix
Acknowledgments x
Conventions/Notations xi
Part I Preliminaries 1
1 Introduction 3
1.1 Course Topics 3
1.2 Course Outline 4
2 Basic Tools 8
2.1 Asymptotics 8
2.2 Binomials 10
2.3 Tail Bounds 16
Part II Erdős–Rényi–Gilbert Model 27
3 Uniform and Binomial Random Graphs 29
3.1 Models and Relationships 29
3.2 Thresholds 35
4 Evolution 45
4.1 Subcritical Phase 45
4.2 Supercritical Phase 54
4.3 Phase Transition 58
5 Vertex Degrees 64
5.1 Degrees of Sparse Random Graphs 64
5.2 Degrees of Dense Random Graphs 70
6 Connectivity 78
6.1 Connectivity 78
6.2 ?-Connectivity 82
7 Small Subgraphs 85
7.1 Thresholds 85
7.2 Asymptotic Distributions 89
8 Large Subgraphs 93
8.1 Perfect Matchings 93
8.2 Long Paths and Cycles 100
8.3 Hamilton Cycles 102
8.4 Spanning Subgraphs 106
9 Extreme Characteristics 111
9.1 Diameter 111
9.2 Largest Independent Sets 114
9.3 Chromatic Number 120
Part III Modeling Complex Networks 125
10 Inhomogeneous Graphs 127
10.1 Generalized Binomial Graph 127
10.2 Expected Degree Sequence 134
10.3 Fixed Degree Sequence 140
11 Small World 154
11.1 Watts–Strogatz Model 154
11.2 Kleinberg’s Model 160
12 Network Processes 163
12.1 Preferential Attachment 163
12.2 Spatial Preferential Attachment 171
13 Intersection Graphs 178
13.1 Binomial Random Intersection Graphs 179
13.2 Random Geometric Graphs 187
14 Weighted Graphs 197
14.1 Minimum Weight Spanning Tree 198
14.2 Shortest Paths 200
14.3 Minimum Weight Assignment 205
References 210
Author Index 216
Subject Index 218
