Network Information Flow in Small World Networks
1Recent 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.