Network Information Flow in Small World Networks

Recent results from statistical physics show that large classes of complex networks, both man-made and of natural origin, are characterized by high clustering properties yet strikingly short path lengths between pairs of nodes. Breaking with the traditional approach to these so called small worlds which relies mainly on graph parameters directly related to connectivity, we investigate the capacity of these networks from the perspective of network information flow. Our contribution includes upper and lower bounds for the capacity of standard and navigable small-world models, i.e. those which admit efficient distributed routing algorithms and are deemed particularly effective, for example in resource discovery tasks and peer-to-peer applications.

Joint work with Rui A. Costa.

Speaker Details

João Barros received his undergraduate education in Electrical and Computer Engineering from the Universidade do Porto (UP), Portugal and Universitaet Karlsruhe, Germany, in 1999, and the Ph.D. degree in Electrical Engineering and Information Technology from the Technische Universitaet Muenchen (TUM), Germany, in 2004. After his doctoral research on network information theory and joint source and channel coding, João Barros joined the faculty of the Department of Computer Science at the Universidade do Porto, where he currently leads the Information Networks Group at LIACC (Laboratory of Artificial Intelligence and Computer Science), and conducts research in the general areas of information theory and communication networks. In 2003, Dr. Barros received a Best Teaching Award from the Bavarian State Ministry of Sciences, Research and the Arts (2003). In 2002 and 2003, he spent six months as a Fulbright scholar at Cornell University, where he worked on fundamental limits of wireless sensor networks. João Barros serves on the Technical Program Committee of ISIT 2007.

João Barros
Universidade do Porto, Portugal