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.
This work was partially supported by the Italian FIRB project “WEB-MINDS”, http://web-minds.consorzio-cini.it/
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
Barrière, L., Fraigniaud, P., Kranakis, E., Krizanc, D.: Efficient Routing in Networks with Long Range Contacts. In: Welch, J.L. (ed.) DISC 2001. LNCS, vol. 2180, pp. 270–284. Springer, Heidelberg (2001)
Chiola, G., Cordasco, G., Gargano, L., Negro, A., Scarano, V.: Overlay networks with class. In: Proc. I-SPAN 2005, IEEE Press, Los Alamitos (2005)
Conway, J.H., Sloane, N.J.A.: Low Dimensional Lattices VII: Coordination Sequences. Proc. Royal Soc. A453, 2369–2389 (1997)
Dodds, P.S., Muhamad, R., Watts, D.J.: An Experimental study of Search in Global Social Networks Ca2 + . Science 301, 827–829 (2003)
Kleinberg, J.M.: The Small–World Phenomenon: An Algorithm Perspective. In: Proc. of 32th ACM Symp. on Theory of computing (STOC 2000), pp. 163–170 (May 2000)
Kleinberg, J.M.: The Small–World Phenomena and the Dynamics of informations. In: Advances in Neural Information Processing Systems (NIPS) (December 2001)
Kleinberg, J.M.: Complex Networks and Decentralized Search Algorithms. In: International Congress of Mathematicians (ICM) (2006)
Fraigniaud, P., Gavoille, C., Paul, C.: Eclecticism Shrinks Even Small Worlds. In: PODC 2004 (2004)
Loguinov, D., Kumar, A., Rai, V., Ganesh, S.: Graph-Theoretic, Analysis of Structured Peer-to-Peer Systems: Routing Distances and Fault Resilience. In: Proc. of the ACM SIGCOMM 2003 Conference (2003)
Milgram, S.: The Small World Problem. Psychology Today, 60–67 (May 1967)
Manku, G.S., Bawa, M., Raghavan, P.: Symphony: Distributed hashing in a Small World. In: Proc. of USENIX Symp. on Internet Technologies and Systems (USITS) (March 2003)
Manku, G.S., Naor, M., Wieder, U.: Know thy Neighbor’s Neighbor: The Power of Lookahead in Randomized P2P Networks. In: Proceedings of 36th ACM Symp. on Theory of Computing (STOC 2004), pp. 54–63 (June 2004)
Martel, C., Van Nguyen: Analyzing Kleinberg’s (and other) Small–world models. In: The 23rd ACM Symposium on Principles of Distributed Computing, pp. 179–188 (2004)
Newth, D., Ash, J.: Evolving cascading failure resilience in complex networks. In: Proc. of 8th Asia Pacific Symp. on Intelligent and Evolutionary Systems (December 2004)
Stoica, I., Morris, R., Liben-Nowell, D., Karger, D.R., Kaashoek, M.F., Dabek, F., Balakrishnan, H.: Chord: A Scalable Peer-to-Peer Lookup Protocol for Internet Applications. IEEE/ACM Trans. Networking 11(1), 17–32 (2003)
Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘smallworld’ networks. Nature 393, 440–442 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cordasco, G., Gargano, L. (2006). How Much Independent Should Individual Contacts Be to Form a Small–World?. In: Asano, T. (eds) Algorithms and Computation. ISAAC 2006. Lecture Notes in Computer Science, vol 4288. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11940128_34
Download citation
DOI: https://doi.org/10.1007/11940128_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49694-6
Online ISBN: 978-3-540-49696-0
eBook Packages: Computer ScienceComputer Science (R0)