Six lectures on Complex Graphs and Networks
Linyuan Lu
BASICS2008 SUMMER SCHOOL
Guiyang, China, July 28 -- August 2, 2008.
Title: Complex Graphs and Networks
"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 G0
consisting of a single loop. For t>0, at time t, the graph Gt
is formed by modifying Gt-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 (w1, w2,...,
wn), we define a general random graph model
G(w1, w2,..., wn), as follows: Each
potential edge between vertex vi and vj is
chosen with probability wi wj /
Σi=1n wi 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 = (Σi=1n wi2) / (Σi=1n wi) 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.