TY - JOUR
T1 - Average message delivery time for small-world networks in the continuum limit
AU - Inaltekin, Hazer
AU - Chiang, Mung
AU - Poor, H. Vincent
PY - 2010/9
Y1 - 2010/9
N2 - This paper introduces a new model, the octopus model, for studying small-world networks. The model is proposed for general measure-metric spaces and parametrizes the generation of complex networks in terms of the distribution of long-range connections per node. This model allows for the generation of a wide spectrum of complex networks including the ones possessing the clustering features of the WattsStrogatz model and those possessing the scale-free features of the Barabsi model. Analytical expressions for the average message delivery time in small-world networks as a function of source-target separation are derived. These analytical formulas show that nodes tend to communicate with one another only through their short-range contacts, and the average message delivery time rises linearly when the separation between source and target is small. On the other hand, as this separation increases, long-range connections are more commonly used, and the average message delivery time rapidly saturates to a constant value and stays almost the same for large values of the separation. These results are consistent with previous experimental observations made by Travers and Milgram in 1969, as well as by others. Other somewhat surprising conclusions of the paper are that hubs have a limited effect in reducing the average message delivery time and that the variance of connectivity in small-world networks adversely affects this time.
AB - This paper introduces a new model, the octopus model, for studying small-world networks. The model is proposed for general measure-metric spaces and parametrizes the generation of complex networks in terms of the distribution of long-range connections per node. This model allows for the generation of a wide spectrum of complex networks including the ones possessing the clustering features of the WattsStrogatz model and those possessing the scale-free features of the Barabsi model. Analytical expressions for the average message delivery time in small-world networks as a function of source-target separation are derived. These analytical formulas show that nodes tend to communicate with one another only through their short-range contacts, and the average message delivery time rises linearly when the separation between source and target is small. On the other hand, as this separation increases, long-range connections are more commonly used, and the average message delivery time rapidly saturates to a constant value and stays almost the same for large values of the separation. These results are consistent with previous experimental observations made by Travers and Milgram in 1969, as well as by others. Other somewhat surprising conclusions of the paper are that hubs have a limited effect in reducing the average message delivery time and that the variance of connectivity in small-world networks adversely affects this time.
UR - http://www.scopus.com/inward/record.url?scp=77955765831&partnerID=8YFLogxK
U2 - 10.1109/TIT.2010.2054490
DO - 10.1109/TIT.2010.2054490
M3 - Article
AN - SCOPUS:77955765831
VL - 56
SP - 4447
EP - 4470
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
SN - 0018-9448
IS - 9
ER -