How Much Independent Should Individual Contacts be to Form a Small–World? ⋆ (Extended Abstract)

Abstract. We study Small–World graphs in the perspective of their use in the development of efficient as well as easy to implement network infrastructures. Our analysis starts from the Small–World model proposed by Kleinberg: a grid network augmented with directed long–range random links. The choices of the long–range links are independent from one node to another. In this setting greedy routing and some of its variants have been analyzed and shown to produce paths of polylogarithmic expected length. We start from asking whether all the independence assumed in the Kleinberg’s model among long–range contacts of different nodes is indeed necessary to assure the existence of short paths. In order to deal with the above question, we impose (stringent) restrictions on the choice of long–range links and we show that such restrictions do not increase the average path length of greedy routing and of its variations. Diminishing the randomness in the choice of random links has several benefits; in particular, it implies an increase in the clustering of the graph, thus increasing the resilience of the network.