"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 primary tool for detecting numerous hidden structures in various information networks, including Intenet 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 network large sparse networks, we use combinatorial, probablistic, 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. " --- Quoted from Complex Graphs and Networks.

• Lecture 1: Overview and outlines
  A large family of real-world graphs from diverse arenas have been shown to have completely unexpected coherence. These graphs are very large, sparse, having small diameters, and having power law degree distributions. In the power law degree distribution, the number of vertices with degree k is proportional to k^-β. Here β is the exponent of power law. In this lecture, we will give motivations, theories, and results on modeling power law graphs. These talks are based on the book "Complex Graphs and Networks" and also on Fan Chung Graham's talks at CBMS Workshop in 2004. The first talk is an overview. Each of the subsequent talks is corresponding to one or two chapters of the book.
• Lecture 2: Generative models - preferential attachment schemes
  In this lecture, we will analyze a simple model using preferential attachment scheme. Starting from an graph G₀ consisting of a single loop. For t>0, at time t, the graph G_t is formed by modifying G_t-1 as follows: with probability p, add a new vertex v, and add an edge uv from v by randomly and independently choosing u in proportion to the degree of u in the current graph. With probability 1-p, add a new edge rs by independently choosing vertices r and s with probability proportional to their degrees. We will rigorously prove this model generates the power law degree distribution with exponent β=2+ p/(2-p).
  
  Reference: William Aiello, Fan Chung, and Linyuan Lu. Random evolution in massive graphs, Proceedings of the Forty-Second Annual Symposium on Foundations of Computer Science, (2001), 510--519. Full version is published at Handbook on Massive Data Sets, (Eds. James Abello et al.), (2001), 97--122.
• Lecture 3: Duplication models for biological networks
  The preferential attachment model generates graphs with power law degree distribution with exponents β greater than 2. However, the partial duplication model can yield power law graphs with β < 2. Many biological networks have power law graphs with exponents β less than 2, while numerous non-biological networks, such as the WWW-graphs and telephone graphs, among others, are power law graphs with the exponent β between 2 and 3. Since gene duplications is the driving force behind biological networks, the partial duplication model is particularly suitable for studying complex networks arising in bioinformatics and biocomplexity.
  
  Reference: Fan Chung, Linyuan Lu, Gregory Dewey, and David J. Galas. Duplication models for biological networks, Journal of Computational Biology, 10, No. 5 (2003), 677-688.

• Lecture 4: The rise of the giant component
  From lecture 4-6, we will study random graphs with given expected degree sequence. For a given sequence (w₁, w₂,..., w_n), we define a general random graph model G(w₁, w₂,..., w_n), as follows: Each potential edge between vertex v_i and v_j is chosen with probability w_i w_j / Σ_i=1ⁿ w_i and is independent of other edges. In this talk, we give an asymptotic formula for the volume of the giant component when it exists.
  
  Reference 1: Fan Chung and Linyuan Lu, Connected components in a random graph with given degree sequences, Annals of Combinatorics 6, (2002), 125--145.
  Reference 2: Fan Chung and Linyuan Lu The volume of the giant component for a random graph with given expected degrees, SIAM J. Discrete Math., 20 (2006), No. 2, 395-411.
• Lecture 5: The small world phenomenon: average distance and diameter
  In 1967 the psychologist Stanley Milgram conducted a series of experiments and concluded the average distance of the social network is about 6. Since then, the so-called ``small world phenomenon'' has long been a subject of anecdotal observation and folklore. In this lecture, we will prove the average distance is (1+o(1)) log n / log d and the diameter is Θ(log n / log d). Here d = (Σ<sub>i=1</sub><sup>n</sup> w<sub>i</sub><sup>2</sup>) / (Σ<sub>i=1</sub><sup>n</sup> w<sub>i</sub>) is the second order average degree. These results also hold for random power law graphs with β > 3. However, for β=3, the average distance is O(log n / log log n) while the diameter is still Θ(log n). For 2 < β < 3, the average distance is O(log log n) while the diameter is still Θ(log n). Random power law graphs have an interesting ``octopus'' shape. It has a dense core of diameter O(log log n) and a few long legs of length Θ(log n).
  
  Reference: Fan Chung and Linyuan Lu The average distance in random graphs with given expected degrees, Proceedings of National Academy of Science, 99 (2002), 15879-15882.Full version, Internet Mathematics 1 (1), 2003, 91-114.

• Lecture 6: Spectrum of random graphs with given degrees
  Wigner's semi-circle law states that for a symmetric matrix with entries taken from a distribution satisfying certain rather general properties, the distribution of eigenvalues is a semi-circle function. Wigner's theorem and its extensions have been used for the stochastic treatment of complex quantum systems that lie beyond the reach of exact methods. In this lecture, we show the Laplacian spectra of random graphs with given expected degree sequence follows the semi-circle law. However, for random power law graphs, large eigenvalues of adjacency matrix are mainly determined by the degrees.
  
  Reference: Fan Chung, Linyuan Lu, and Van Vu, The spectra of random graphs with given expected degrees, Proceedings of National Academy of Science, 100, No. 11, (2003), 6313-6318.
  Fan Chung, Linyuan Lu, and Van Vu, Eigenvalues of random power law graphs, Annals of Combinatorics 7, (2003), 21--33.