Complex Graphs and Networks
by Fan Chung and Linyuan Lu

A new book published by AMS
ISBN-10: 0-8218-3657-9     ISBN-13: 978-0-8218-3657-6
Available at Amazon or AMS

From the Preface --

In many ways, working on graph theory problems over the years has always seemed like fun and games. Recently, through examples of large sparse graphs in realistic networks, research in graph theory has been forging ahead into an exciting new dimension. 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 will need to use all the tools at our disposal, including combinatorial, probabilistic and spectral methods. ...

                    The preface (in full)

Chapter 1: Graph theory in the information age

Chapter 2: Old and new concentration inequalities, revised September 2010 (thanks to Jacques' comments).

Chapter 3: A generative model -- the preferential attachment scheme

Chapter 4: Duplication models for biological networks

Chapter 5: Random graphs with given expected degrees

Chapter 6: The rise of the giant component

Chapter 7: Average distance and the diameter

Chapter 8: Eigenvalues of the adjacency matrix of G(w)

Chapter 9: The semi-circle law for G(w)

Chapter 10: Coupling on-line and off-line analyses of random graphs

Chapter 11: The configuration model for power law graphs

Chapter 12: The small world phenomenon in hybrid graphs

This page is part of Fan Chung Graham's website.