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.

Speaker Details

Milena Mihail received her BA in electrical engineering at the Polytechnic School of Athens, Greece, in 1984, and her PhD in Computer Science at Harvard University in 1989. During her PhD, she did pioneering work on the Markov Chain Monte Carlo Method, whose inception goes back to the mid 1980’s. Inspired by her stay at Bell Communications Research from 1989 to 1999, initially as member of technical staff and later as manager and senior scientist, she started working at the interface of algorithms and networking. Over the last five years, this area has blossomed into a premier area of research within theoretical computer science and Mihail is one of its key players. She is currently Associate Professor at the College of Computing at Georgia Tech.

Date:
Speakers:
Milena Mihail
Affiliation:
Georgia Institute of Technology
    • Portrait of Jeff Running

      Jeff Running