Network Information Flow in Small World Networks

Details Network Information Flow in Small World Networks Network Information Flow in Small World Networks

2006-12-20

arxiv.org/abs/cs/0612099v1

Computer Science

Information Theory

23 pages, 8 fitures, submitted to the IEEE Transactions on Information Theory, November 2006

Scientific paper

Recent 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. This class of networks are said to have a small-world topology. 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. Breaking with the traditional approach to small-world topologies that privileges graph parameters pertaining to connectivity, and intrigued by the fundamental limits of communication in networks that exploit this type of topology, 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, and the somewhat surprising result that, with high probability, random rewiring does not alter the capacity of a small-world network.

Affiliated with

Also associated with

No associations

Rating

Network Information Flow in Small World Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Network Information Flow in Small World Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network Information Flow in Small World Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-241777