Title: Convergent Sequences of Dense Graphs

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. This is joint work with Jennifer Chayes, Laci Lovasz, Vera Sos and Kati Vesztergombi. Jennifer Chayes, Microsoft Research

Title: Epidemics in Technological and Social Networks: The Downside of Six Degrees of Separation

During the past decade, complex networks have become increasingly important in communication and information technology. Vast, self-engineered networks, like the Internet, the World Wide Web, and Instant Messaging Networks, have facilitated the flow of information, and served as a medium for social and economic interaction. In social networks, the ease of information flow goes by many names: the "small world" phenomenon, the "Kevin Bacon phenomenon," and "six degrees of separation" -- the claim that any two people on earth can be connected through a chain of acquaintances with at most five intermediaries. Unfortunately, many of the properties that facilitate information transmission also facilitate the spread of viruses in both technological and social networks. The speaker uses simple mathematical models to explain these epidemics and to examine strategies for their containment.

Title: Algorithmic Performance in Complex Networks

Complex communication networks, such as the Internet, the WWW, ad-hoc and peer-to-peer networks, are pervasive in today's technology and society. Which parameters of these networks are critical in determining the performance of protocols running on these networks? Can we control these parameters and hence improve network performance?

In this talk we will argue that a critical parameter is the expansion, or conductance of the graph underlying the network topology. This is also closely related to the second eigenvalue of a suitable normalization of the adjacency matrix of this graph. We will study expansion, conductance and the spectral gap, theoretically and experimentally, in several classes of topologies whose metrics match the real network, such as power-law graphs, as well as in several instances of real network data. We will further present efficient distributed algorithms that maintain networks with good expansion, conductance and spectral gap.

Title: Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting Partition Functions

We address algorithms for approximate counting problems, such as estimating the partition function of the Ising model, or counting the number of colorings or matchings of a graph. Algorithms for these problems work via reduction to sampling from the corresponding distribution. For example, to approximately count the number of matchings of a graph G, we express the number of matchings of G as a telescoping product of the number of matchings of a sequence of weighted graphs G_0,...,G_j where G_j=G and G_0 is a trivial graph such as the empty graph. This sequence of graphs is a cooling schedule for a simulated annealing algorithm. If successive graphs are sufficiently similar, then by sampling matchings at each of the intermediate temperatures we can estimate the number of matchings of G. We present an algorithm to adaptively find a cooling schedule of length O*(\sqrt{n}) even though the ratio of the number of matchings of G_0 to G can be exponentially large. Our cooling schedule improves upon previous approaches by a factor O(\sqrt{n}) and translates into an overall savings of O(n) in the running time for many approximate counting algorithms. This is joint work with Daniel Stefankovic and Santosh Vempala.