Network information flow in navigable small-world networks

Abstract

Small-world graphs, exhibiting high clustering coefficients and small average path length, have been shown to capture fundamental properties of a large number of natural and man-made networks. In the context of communication networks, navigable small-world topologies, i.e. those which admit efficient distributed routing algorithms, are deemed particularly effective, for example in resource discovery tasks and peer-to-peer applications. Intrigued by the fundamental limits of communication in networks that exploit this type of topology, we study two classes of navigable small-world networks from the point of view of network information flow and provide inner and outer bounds for their max-flow min-cut capacity. Our contribution is in contrast with the standard approach to small world networks which privileges parameters pertaining to connectivity.