**Milena Mihail, **Georgia Tech
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.