Expected message delivery time for small-world networks in the continuum limit

Hazer Inaltekin*, Mung Chiang, H. Vincent Poor

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

2 Citations (Scopus)

Abstract

Small-world networks are networks in which the graphical diameter of the network is as small as the diameter of random graphs but whose nodes are highly clustered when compared with the ones in a random graph. Examples of small-world networks abound in sociology, biology, neuroscience and physics as well as in human-made networks. This paper analyzes the average delivery time of messages in dense smallworld networks constructed on a plane. Iterative equations for the average message delivery time in these networks are provided for the situation in which nodes employ a simple greedy geographic routing algorithm. It is shown that two network nodes communicate with each other only through their shortrange contacts, and that the average message delivery time rises linearly if the separation between them is small. On the other hand, if their separation increases, the average message delivery time rapidly saturates to a constant value and stays almost the same for all large values of their separation.

Original languageEnglish
Title of host publication2008 IEEE International Symposium on Information Theory
Subtitle of host publicationproceedings
Place of PublicationPiscataway, NJ
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages667-671
Number of pages5
ISBN (Electronic)9781424422579
ISBN (Print)9781424422562
DOIs
Publication statusPublished - 2008
Externally publishedYes
Event2008 IEEE International Symposium on Information Theory, ISIT 2008 - Toronto, ON, Canada
Duration: 6 Jul 200811 Jul 2008

Publication series

Name
ISSN (Print)2157-8095
ISSN (Electronic)2157-8117

Other

Other2008 IEEE International Symposium on Information Theory, ISIT 2008
Country/TerritoryCanada
CityToronto, ON
Period6/07/0811/07/08

Fingerprint

Dive into the research topics of 'Expected message delivery time for small-world networks in the continuum limit'. Together they form a unique fingerprint.

Cite this