TY - JOUR

T1 - Navigation in small-world networks: a scale-free continuum model

AU - Franceschetti, M.

AU - Meester, R.W.J.

N1 - MR2274645

PY - 2006

Y1 - 2006

N2 - The small-world phenomenon, the principle that we are all linked by a short chain of intermediate acquaintances, has been investigated in mathematics and social sciences. It has been shown to be pervasive both in nature and in engineering systems like the World Wide Web. Work of Jon Kleinberg has shown that people, using only local information, are very effective at finding short paths in a network of social contacts. In this paper we argue that the underlying key to finding short paths is scale invariance. In order to appreciate scale invariance we suggest a continuum setting, since true scale invariance happens at all scales, something which cannot be observed in a discrete model. We introduce a random-connection model that is related to continuum percolation, and we prove the existence of a unique scale-free model, among a large class of models, that allows the construction, with high probability, of short paths between pairs of points separated by any distance. © Applied Probability Trust 2006.

AB - The small-world phenomenon, the principle that we are all linked by a short chain of intermediate acquaintances, has been investigated in mathematics and social sciences. It has been shown to be pervasive both in nature and in engineering systems like the World Wide Web. Work of Jon Kleinberg has shown that people, using only local information, are very effective at finding short paths in a network of social contacts. In this paper we argue that the underlying key to finding short paths is scale invariance. In order to appreciate scale invariance we suggest a continuum setting, since true scale invariance happens at all scales, something which cannot be observed in a discrete model. We introduce a random-connection model that is related to continuum percolation, and we prove the existence of a unique scale-free model, among a large class of models, that allows the construction, with high probability, of short paths between pairs of points separated by any distance. © Applied Probability Trust 2006.

U2 - 10.1239/jap/1165505216

DO - 10.1239/jap/1165505216

M3 - Article

VL - 43

SP - 1173

EP - 1180

JO - Journal of Applied Probability

JF - Journal of Applied Probability

SN - 0021-9002

IS - 4

ER -