Algorithmic Performance in Complex Networks

Опубликовано 7 сентября 2016, 16:38

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.