Network information flow in navigable small-world networks

• Author(s): Rui Filipe Mendes Alves da Costa ; João Francisco Cordeiro de Oliveira Barros
• Date: 2006
• Persistent ID: http://hdl.handle.net/10216/7071
• Origin: Repositório Aberto da Universidade do Porto
• Subject(s): Ciências tecnológicas; Engenharia; Engenharia de comunicações; Engenharia de telecomunicações
• Document Type: Conference Object
• Language: English

Description

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.