Thumbnail
Access Restriction
Open

Author Costa, Rui A. ♦ Barros, João
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Small World Network ♦ Man-made Network ♦ Standard Approach ♦ Communication Network ♦ High Clustering Coefficient ♦ Small Average Path Length ♦ Max-flow Min-cut Capacity ♦ Fundamental Limit ♦ Navigable Small-world Network ♦ Fundamental Property ♦ Network Information Flow ♦ Large Number ♦ Resource Discovery Task ♦ Peer-to-peer Application ♦ Abstract Small-world Graph ♦ Navigable Small-world Topology
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.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Publisher Date 2006-01-01