Random Graphs and Large-Scale Real-World Networks
(1 May - 30 Jun 2006)
~ Abstracts ~
Boundary connections in trees and
Dimers
David Wilson, Microsoft Research
We study groves on planar graphs, which are forests in which every tree contains one or more of a special set of vertices on the outer face. Each grove partitions the set of special vertices. When a random grove is selected, we show how to compute the various partition probabilities as functions of the electrical properties of the graph when viewed as a resistor network. We prove that for any partition sigma, Pr[grove has type sigma] / Pr[grove is a tree] is a dyadic-coefficient polynomial in the pairwise resistances between the special vertices, and Pr[grove has type sigma] / Pr[grove has maximal number of trees] is an integer-coefficient polynomial in the entries of the Dirichlet-to-Neumann matrix. We give analogous polynomial formulas for the double-dimer model. These partition probabilities are relevant to multichordal SLE_8, SLE_2, and SLE_4.
Joint work with Richard Kenyon.
Threshold growth cellular
automata: bootstrap percolation
Jozsef Balogh, University of Illinois at Urbana-Champaign
Cellular automata were introduced by von Neumann after a suggestion of Ulam. A very popular cellular automaton is Conway's `Game of Life'. Bootstrap percolation, a deterministic threshold growth model of cellular automata with random initial condition, was introduced by statistical physicists in the early 1980s.
The underlying graph of bootstrap percolation could be any graph, in the literatute infinite trees, grids, the $n$-dimensional hypercube and random regular graphs were considered.
In this talk I shall briefly survey the history of bootstrap percolation, and then present some recent results from a number of papers written jointly with B. Bollobas, Y. Peres, G. Pete and B. Pittel.
Long cycles in random graphs
Nick Wormald, University of Waterloo
When a random graph on n vertices has enough edges, i.e.
about (1/2) n log n, it almost surely has a cycle containing
all of its vertices, and the circumference (length of
longest cycle) is n.
What happens in the sparser case? When the graph has much
less than
n/2 edges, and the average degree is less than 1, there are
few cycles and the answer is well understood. I will discuss
old results on circumference as well as a new lower bound
applying to intermediate range. Here the average degree of a
vertex is at least 1 but can be regarded as bounded. (Joint
work with Jeong Han Kim.)
Cheeger constant, capacity and computation in wireless networks
Devavrat Shah, Massachusetts Institute of Technology
Recent technological progress has made it feasible to
design in-expensive sensors that can communicate over
wireless channel as well as perform computation.
Network of such sensors has become instrumental in enabling
many new applications.
In this tutorial, we will provide the fundamental
performance limits of such networks in terms of
communication capacity, network delay and the computation
time-complexity of distributed algorithms operating within
them.
We will identify the well-known Cheeger Constant or
Conductance of appropriately defined wireless graph matrix
as a key property that determines the capacity, delay and
computation time of distributed algorithms. We will describe
the precise results in arbitrary setup. We will present
random graph models for static and mobile wireless networks.
Then, we will evaluate the Cheeger Constant for these models
to obtain the capacity, delay and computation time of
algorithms for wireless networks.
On the asymptotic behaviour of random recursive trees in random environment
Konstantin Borovkov, The University of Melbourne
We consider growing random recursive trees in random environment, in which at each step a new vertex is attached (by an edge of a random length) to an existing tree vertex according to a probability distribution that assigns the tree vertices masses proportional to their random weights. The main goal is to study the asymptotic behaviour of the distance from the newly inserted vertex to the tree's root and that of the mean numbers of outgoing vertices as the number of steps tends to infinity. Most of the results are obtained under the assumption that the random weights have a product form with independent identically distributed factors.
Modeling and analysis of large
ad hoc networks
Martin Haenggi, University of Notre Dame
Wireless ad hoc and sensor networks have many exciting
applications and thus are a very active area of research.
In constrast to the well-understood case of point-to-point
communication, the analysis of large wireless networks
presents many interesting challenges. Starting with the
classical disk graph, we introduce increasingly refined
models for such systems, and we present approaches to
analyze their performance in terms of interference and
throughput.
Continuum models for
large-scale sensor networks: routing and broadcasting
Sanjay Shakkottai, University of Texas
This tutorial will present an overview of routing and broadcasting over sensor networks. We develop continuum models for sensor networks -- models where node location discretization effects are ignored, and develop both routing and broadcasting algorithms for large-scale networks using these models. A key emphasis in this tutorial will be on the role of information -- geographic location knowledge, or memory at nodes (which corresponds to state information), and how this affects network delay, capacity and broadcast efficiency.
Critical percolation on
random regular graphs
Assaf Noar, University of California
Let d>2 be a fixed integer, n an integer such that nd is
even and p in (0,1). Let G(n,d,p) be a probability space on
the set of graph with n vertices obtained by drawing
uniformly at random a d-regular graph on n vertices and then
independently retaining each edge with probability p and
deleting it with probability 1-p.
Alon, Benjamini and Stacey proved that for p= c/(d-1) the
model exhibits a phase transition as c grows: the
cardinality of the largest component is of order log(n) for
c<1 and of order n for c>1. We investigate the model in its
critical value and show the existence of a scaling window
and "mean-field" behavior.
Small-world graphs
Oskar Sandberg, Chalmers University
The small-world phenomenon, that the world's social
network is tightly connected, and that any two people can be
linked by a short chain of friends, has long been a subject
of interest. Famously, the psychologist Stanley Milgram
performed an experiment where he asked people to deliver a
letter to a stranger by forwarding it to an acquaintance,
who could forward it to one his acquaintances, and so on
until the destination was reached. The results seemed to
confirm that the small-world phenomenon is real. Recently it
has been shown by Jon Kleinberg that in order to search in a
network, that is to actually find the short paths in the
manner of the Milgram experiment, a very special type of a
graph model is needed. We study the formation of networks of
this type, attempting to see why the kind of connections
necessary may arise naturally. A different criterion on the
network which also makes the efficient searches possible is
shown, and based on it an algorithmic model is proposed for
how searching can become possible as a network evolves.
Euclidean ramsey theory
Imre Leader, University of Cambridge
Euclidean Ramsey Theory is a natural multidimensional
version of Ramsey Theory. A subset of Euclidean space is
called Ramsey if, for any k, whenever we partition Euclidean
space of sufficiently high dimension into k classes, one
class must contain a congruent copy of our subset. It is
still unknown which sets are Ramsey.
The aim of the talk is to present background, involving the
known results, and then to put forward a new conjecture
which is the first `challenge' to the accepted main
conjecture in the area.
Clustering via random
ultrametrics
Assaf Noar, Microsoft Research
In this talk I will present a general method for
clustering a large graph so that the clusters are small in
various metric senses. There is a wide range of problems of
this type which have been studied in the literature. It
turns out that many of them can be reduced to the same
problem on trees (and even ultrametrics), using a
probabilistic technique which we call Maximum Gradient
Embeddings. I will introduce this notion, explain the basic
theorems about it, and show how it can be used to solve
several clustering problems with monotone costs.
Tie-strength and structure in a
huge social network
J'anos Kert'esz, Budapest University of Technology and
Economics
We consider a network constructed from the data of mobile
phone conversations as a proxy for a weighted societal
network: Individuals are the nodes (vertices), mutual calls
are the links (edges) and the accumulated call durations
serve as the weights of the links representing the
intensities of social ties. We observe a coupling between
interaction strengths and the network's local structure in
good agreement with Granovetter's hypothesis.
As a consequence we find that social networks are robust to
the removal of the strong ties but fall apart in a
percolation transition if the weak ties are removed. We show
that this structure results in a dynamic trapping of
information and give hints to increase efficiency of
information spreading.
Discrete versions of the newman,
moore, watts small worlds model
Andrew Barbour, Universität Zürich
Newman, Moore and Watts proposed a model that is aimed at
describing paths of communication in a system consisting of
good local contacts and sporadic long range links. In this
talk, we discuss the asymptotics of the distribution of
interpoint distances in some discrete versions of their
simplest continuous-state model. The arguments required in
the fully discrete analogue are more complicated than in the
continuous case, because the associated branching process,
describing the local evolution of the long range contact
structure at a typical point, is two-dimensional.
For some combinations of parameters, this is enough to cause
the standard approximation argument to break down.
Joint work with Gesine Reinert, Oxford.
Random planar graphs with fixed
average degree
Stefanie Gerke, Institute of Theoretical Computer Science,
ETH, Zürich
Let P(n,m) be the class of simple labelled planar graphs
with n nodes and m edges, and let R(n,q) be a graph drawn
uniformly at random from P(n,qn). We show properties that
hold with high probability (w.h.p.) for R(n,q) when 1<q<3.
For example, we show that R(n,q) contains w.h.p. linearly
many nodes of each given degree and linearly many node
disjoint copies of each given fixed connected planar graph.
Additionally, we show that the probability that R(n,q) is
connected is bounded away from one by a non-zero constant.
As a tool we show that (|P(n,qn)|/n!)^{1/n} tends to a limit
as n tends to infinity.
This is joint work with Colin McDiarmid, Angelika Steger and
Andreas Weissl.
Complex networks and markov
processes – degree distributions
Liming Liu, Hong Kong Polytechnic University
Since Barabási, Albert and Jeong proposed the first
scale-free network model (the BA model), the study of
complex networks has become one of the newest
inter-disciplinary scientific pursuits. Many new network
models have been proposed attempting to identify the
underlying mechanisms for various complex networks observed
in physical, digital, and societal worlds. While simulation
can usually be used to examine the properties of the network
generated from any given mechanism, it is still desirable to
provide analytical characterizations of network properties
under a given mechanism. The common analytical approach
however can only tackle a few simple network models. In this
talk, we show that the degree dynamics of many complex
networks is intimately related to Markov processes. By
modeling the degree evolution of a node in a growing network
by a non-homogeneous Markov process, we not only can provide
the asymptotic network degree distribution numerically, but
also can capture the complete network degree evolution
process. We will provide a number of network model examples,
including the BA mechanism with a logarithmic link adding
function and a new evolving network model that generate a
wide-range of networks with degree exponents > 1.
New critical phenomena in complex
random graphs
Serguei Dorogovtsev, Universidade de Aveiro, Portugal and
A.F. Ioffe Physico-Technical Institute, St. Petersburg
We consider critical phenomena in cooperative models
defined on graphs where a diameter is a function growing
slower than any power law of the number of vertices, e.g.,
logarithmic. These graphs are infinite-dimensional objects,
and so critical phenomena on them should be described in the
framework of a mean field approach. Nonetheless, these mean
field theories turn out to be nontraditional, and they
produce a set of new effects. We outline exact and
asymptotically exact results obtained for the Ising and
Potts models and for the percolation on equilibrium and
non-equilibrium random graphs. We also touch upon new
findings for cooperative models on
deterministic graphs with complex architectures.
Convergent Sequence of Dense
Graphs, Part I
Jennifer Chayes, Microsoft Research
We consider how to suitably define convergence for a
sequence of dense graphs, with the number of vertices
tending to infinity. To this end, we consider two ways of
probing a large graph with small graphs: “from the left”, by
counting the the number of times a small graph is contained
in
the large graph as a subgraph, and “from the right”, by
counting the number of H-colorings of the large graph, i.e.,
the number of homomorphisms
from the large graph into some small graph H. This leads to
two notions of convergence: from the left, corresponding to
the convergence of local properties like the frequency of
triangles, and from the right, corresponding to more global
properties like the number of colorings or the size of the
max-cut. We show that these two notions are equivalent for
sequences of dense graphs, and also show that a convergent
sequence can also be characterized as a Cauchy sequence with
respect to a suitable metric.
In the first talk, we discuss the equivalence of
left-convergence and convergence in metric, and the
relations to sampling and testing of large graphs. In the
second talk, we discuss the equivalence of left-convergence
and right-convergence, as well as relations to statistical
physics and the convergence of factor graphs obtained from
large graphs by “factoring out” Szemeredi partitions.
This is joint work with Laci Lovasz, Vera Sos and Kati
Vesztergombi.
Convergent Sequence of Dense
Graphs, Part II
Christian Borgs, Microsoft Research
We consider how to suitably define convergence for a
sequence of dense graphs, with the number of vertices
tending to infinity. To this end, we consider two ways of
probing a large graph with small graphs: “from the left”, by
counting the the number of times a small graph is contained
in
the large graph as a subgraph, and “from the right”, by
counting the number of H-colorings of the large graph, i.e.,
the number of homomorphisms
from the large graph into some small graph H. This leads to
two notions of convergence: from the left, corresponding to
the convergence of local properties like the frequency of
triangles, and from the right, corresponding to more global
properties like the number of colorings or the size of the
max-cut. We show that these two notions are equivalent for
sequences of dense graphs, and also show that a convergent
sequence can also be characterized as a Cauchy sequence with
respect to a suitable metric.
In the first talk, we discuss the equivalence of
left-convergence and convergence in metric, and the
relations to sampling and testing of large graphs. In the
second talk, we discuss the equivalence of left-convergence
and right-convergence, as well as relations to statistical
physics and the convergence of factor graphs obtained from
large graphs by “factoring out” Szemeredi partitions.
This is joint work with Laci Lovasz, Vera Sos and Kati
Vesztergombi.
Inversion and stability in
extremal and Ramsey graph theory
Vladimir Nikiforov, University of Memphis
I will present several recent results in extremal and
Ramsey graph theory involving the general concepts of
inversion and stability. These concepts were present already
in the works of Erdős and Simonovits from 1966 and became a
hot topic again in modern extremal graph theory.
These results are joint work with B. Bollobás, C.C.
Rousseau, and R.H. Schelp.
On the number of complete
bipartite subgraphs of a graph
Jonathan Cutler, University of Nebraska-Lincoln
Entropy methods have recently been employed by Kahn to
bound the number of independent sets in a regular bipartite
graph. Galvin and Tetali noted that these methods extend to
bounding the number of homomorphisms from a regular
bipartite graph. Our research grows out of a conjecture of
Galvin and Kahn, and examines the very special case of
homomorphisms into a fully-looped path of length two. We, in
fact, look at the problem in the complementary graph, where
a homomorphism into this graph corresponds to a complete
bipartite subgraph. Thus, our question becomes an extremal
one: which graph on a given number of vertices and edges has
the most complete bipartite subgraphs? We answer this and
show that some interesting extremal behavior exists.
This is joint work with Jamie Radcliffe.
The phase transition in random
digraphs
Tomasz Luczak, Emory University
In the talk we survey some results on the phase
transition in random digraphs which have been published for
the last twenty five years. Then, we show that the critical
behavour of a random digraph is precisely as one might
expect.
This is a joint work with Taral Guldahl Seierstad.
