Network information flow in navigable small-world networks

• Autor(es): Rui Filipe Mendes Alves da Costa ; João Francisco Cordeiro de Oliveira Barros
• Data: 2006
• Identificador Persistente: http://hdl.handle.net/10216/7071
• Origem: Repositório Aberto da Universidade do Porto
• Assunto(s): Ciências tecnológicas; Engenharia; Engenharia de comunicações; Engenharia de telecomunicações
• Tipo de Documento: Documento de conferência
• Idioma: Inglês

Descrição

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.