Algorithmic Performance in Complex Networks

Milena Mihail
Georgia Tech

Friday, December 1st, 2006, 3:30 pm
Wean Hall 7220

Abstract

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. This has applications in peer-to-peer networks and ad-hoc networks.