CBMS Regional Conference Series in Mathematics
Volume: 107;
2006;
264 pp;
Softcover
MSC: Primary 05; 68; 90; 94;
Print ISBN: 978-0-8218-3657-6
Product Code: CBMS/107
List Price: $57.00
Individual Price: $45.60
Electronic ISBN: 978-1-4704-2467-1
Product Code: CBMS/107.E
List Price: $57.00
Individual Price: $45.60
You may also like
Supplemental Materials
Complex Graphs and Networks
Share this pageFan Chung; Linyuan Lu
A co-publication of the AMS and CBMS
Through examples of large complex graphs in
realistic networks, research in graph theory has been forging ahead
into exciting new directions. Graph theory has emerged as a primary
tool for detecting numerous hidden structures in various information
networks, including Internet graphs, social networks, biological
networks, or, more generally, any graph representing relations in
massive data sets.
How will we explain from first principles the universal and
ubiquitous coherence in the structure of these realistic but complex
networks? In order to analyze these large sparse graphs, we use
combinatorial, probabilistic, and spectral methods, as well as new and
improved tools to analyze these networks. The examples of these
networks have led us to focus on new, general, and powerful ways to
look at graph theory. The book, based on lectures given at the CBMS
Workshop on the Combinatorics of Large Sparse Graphs, presents new
perspectives in graph theory and helps to contribute to a sound
scientific foundation for our understanding of discrete networks that
permeate this information age.
Readership
Graduate students and research mathematicians interested in combinatorics (graph theory) and its applications to large networks.
Reviews & Endorsements
This is a well-structured and useful book for researchers in random graphs, combinatorics and computer science. Because of its self-contained nature, and the careful way the topics are introduced, it is a good text for graduate level courses in the subject.
-- Colin D. Cooper for Mathematical Reviews
Table of Contents
Table of Contents
Complex Graphs and Networks
- Cover Cover11 free
- Title i2 free
- Copyright ii3 free
- Contents iii4 free
- Preface vii8 free
- Chapter 1. Graph Theory in the Information Age 110 free
- Chapter 2. Old and New Concentration Inequalities 2130
- 2.1. The binomial distribution and its asymptotic behavior 2130
- 2.2. General Chernoff inequalities 2534
- 2.3. More concentration inequalities 3039
- 2.4. A concentration inequality with a large error estimate 3342
- 2.5. Martingales and Azuma's inequality 3544
- 2.6. General martingale inequalities 3847
- 2.7. Supermartingales and Submartingales 4150
- 2.8. The decision tree and relaxed concentration inequalities 4655
- Chapter 3. A Generative Model — the Preferential Attachment Scheme 5564
- 3.1. Basic steps of the preferential attachment scheme 5564
- 3.2. Analyzing the preferential attachment model 5665
- 3.3. A useful lemma for rigorous proofs 5968
- 3.4. The peril of heuristics via an example of balls-and-bins 6069
- 3.5. Scale-free networks 6271
- 3.6. The sharp concentration of preferential attachment scheme 6473
- 3.7. Models for directed graphs 7079
- Chapter 4. Duplication Models for Biological Networks 7584
- 4.1. Biological networks 7584
- 4.2. The duplication model 7685
- 4.3. Expected degrees of a random graph in the duplication model 7786
- 4.4. The convergence of the expected degrees 7988
- 4.5. The generating functions for the expected degrees 8392
- 4.6. Two concentration results for the duplication model 8493
- 4.7. Power law distribution of generalized duplication models 8998
- Chapter 5. Random Graphs with Given Expected Degrees 91100
- 5.1. The Erdös-Rényi model 91100
- 5.2. The diameter of G[sub(n,p)] 95104
- 5.3. A general random graph model 97106
- 5.4. Size, volume and higher order volumes 97106
- 5.5. Basic properties of G(w) 100109
- 5.6. Neighborhood expansion in random graphs 103112
- 5.7. A random power law graph model 107116
- 5.8. Actual versus expected degree sequence 109118
- Chapter 6. The Rise of the Giant Component 113122
- 6.1. No giant component if w < 1? 114123
- 6.2. Is there a giant component if w > 1? 115124
- 6.3. No giant component if w < 1? 116125
- 6.4. Existence and uniqueness of the giant component 117126
- 6.5. A lemma on neighborhood growth 126135
- 6.6. The volume of the giant component 129138
- 6.7. Proving the volume estimate of the giant component 131140
- 6.8. Lower bounds for the volume of the giant component 136145
- 6.9. The complement of the giant component and its size 138147
- 6.10. Comparing theoretical results with the collaboration graph 141150
- Chapter 7. Average Distance and the Diameter 143152
- 7.1. The small world phenomenon 143152
- 7.2. Preliminaries on the average distance and diameter 144153
- 7.3. A lower bound lemma 146155
- 7.4. An upper bound for the average distance and diameter 147156
- 7.5. Average distance and diameter of random power law graphs 149158
- 7.6. Examples and remarks 158167
- Chapter 8. Eigenvalues of the Adjacency Matrix of G(w) 161170
- 8.1. The spectral radius of a graph 161170
- 8.2. The Perron-Frobenius Theorem and several useful facts 162171
- 8.3. Two lower bounds for the spectral radius 163172
- 8.4. An eigenvalue upper bound for G(w) 164173
- 8.5. Eigenvalue theorems for G(w) 165174
- 8.6. Examples and counterexamples 169178
- 8.7. The spectrum of the adjacency matrix of power law graphs 170179
- Chapter 9. The Semi-Circle Law for G(w) 173182
- 9.1. Random matrices and Wigner's semi-circle law 173182
- 9.2. Three spectra of a graph 174183
- 9.3. The Laplacian of a graph 175184
- 9.4. The Laplacian of a random graph in G(w) 176185
- 9.5. A bound for random graphs with large minimum degree 177186
- 9.6. The semi-circle law for Laplacian eigenvalues of graphs 179188
- 9.7. An upper bound on the spectral norm of the Laplacian 180189
- 9.8. Implications of Laplacian eigenvalues for G(w) 185194
- 9.9. An example of eigenvalues of a random power law graph 187196
- Chapter 10. Coupling On-line and Off-line Analyses of Random Graphs 189198
- 10.1. On-line versus off-line 189198
- 10.2. Comparing random graphs 190199
- 10.3. Edge-independent and almost edge-independent random graphs 194203
- 10.4. A growth-deletion model for random power law graphs 198207
- 10.5. Coupling on-line and off-line random graph models 200209
- 10.6. Concentration results for the growth-deletion model 205214
- 10.7. The proofs of the main theorems 215224
- Chapter 11. The Configuration Model for Power Law Graphs 223232
- 11.1. Models for random graphs with given degree sequences 223232
- 11.2. The evolution of random power law graphs 224233
- 11.3. A criterion for the giant component in the configuration model 225234
- 11.4. The sizes of connected components in certain ranges for β 225234
- 11.5. The distribution of connected components for β > 4 229238
- 11.6. On the size of the second largest component 232241
- 11.7. Various properties of a random graph of the configuration model 236245
- 11.8. Comparisons with realistic massive graphs 237246
- Chapter 12. The Small World Phenomenon in Hybrid Graphs 241250
- 12.1. Modeling the small world phenomenon 241250
- 12.2. Local graphs with many short paths between local edges 242251
- 12.3. The hybrid power law model 244253
- 12.4. The diameter of the hybrid model 248257
- 12.5. Local graphs and local flows 250259
- 12.6. Extracting the local graph 251260
- 12.7. Communities and examples 253262
- Bibliography 255264
- Index 261270
- Back Cover Back Cover1274