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: 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.

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.