brief communications Navigation in a sma‖word It is easier to find short chains between points in some networks than others he small-world phenomenon- the tions follow an inverse-square distribution, nection that brings it as close as possible to inciple that most of us are linked by there is a decentralized algorithm that the target in lattice distance. Moreover, ort chains of acquaintances- was achieves a very rapid delivery time; T is a=2 is the only exponent at which any first investigated as a question in sociolo- bounded by a function proportional to decentralized algorithm can achieve a deliv gy.and is a feature of a range of networks (log N). The algorithm achieving this ery time bounded by any polynomial arising in nature and technology-. Experi- bound is agreed heuristic: each message log N: for every other exponent, an asymp- mental study of the phenomenon revealed holder forwards the message across a con- totically much larger delivery time is that it has two fundamental components regardless of the algorithm first, such short chains are ubiquitous, and employed(Fig. 1b) second, individuals operating with purel These results indicate that efficient navi- local information are very adept at finding ooooo gability is a fundamental property of only these chains. The first issue has been some small-world structures. The results analysed, and here I investigate the sec- o also generalize to d-dimensional lattices for ond by modelling how individuals can find short chains in a large social network. vo oo9 o/any value of d>1, with the critical value of the clustering exponent becoming a=d i have found that the cues needed for Simulations of the greedy algorithm yield discovering short chains emerge in a very -o results that are qualitatively consistent with simple network model. This model is based on early experiments, in which source indi o the asymptotic analytical bounds(Fig1c) the areas of communication net viduals in Nebraska attempted to transmit a works and neuroanatomy, the issue of letter to a target in Massachusetts, with the routing without a global network organiza letter being forwarded at each step to some- 0.8 tion has been considered; also in social psy one the holder knew on a first-name basis.=S (a-2y(a-1) hology and information foraging some of The networks underlying the model follow the cues that individuals use to construct the small-world paradigm: they are rich paths through a social network or hyper- 知m1 linked environment have been discovered Although I have focused on a very clean Long-range connections are added to a model, I believe that a more general conclu two-dimensional lattice controlled by a sion can be drawn for small-world networks clustering exponent, a, that determines the namely that the correlation between local probability of a connection between two Clustering exponent (a) tructure and long-range connections pro nodes as a function of their lattice distance vides critical cues for finding paths through (Fig. 1a). Decentralized algorithms are the network studied for transmitting a message: at each 7 When this correlation is near a critical step, the holder of the message must pass it 5 hreshold, the structure of the long-range across one of its short- or long-range con connections forms a type of gradient that nections; crucially, this current holder does260 allows individuals to guide a message effi not know the long-range connections of ciently towards a target. As the correlation nodes that have not touched the drops below this critical value and the social The primary figure of merit for such an5 etwork becomes more homogeneous, algorithm is its expected delivery time T,k5.0 these cues begin to disappear; in the limit, which represents the expected number of when long-range connections are generated steps needed to forward a message between Clustering exponent (a uniformly at random, the result is a world a random source and target in a network in which short chains exist but individuals generated according to the model. It is cru- Figure 1 The navigability of small-world networks. a, The network faced with a disorienting array of social cial to constrain the algorithm to use only model is derived from an nx n lattice. Each node, u, has a short. contacts, are unable to find them. local information- with global knowledge range connection to its nearest neighbours(a, b, cand d)and a Jon M. Kleinberg of all connections in the network, the short- long-range connection to a randomly chosen node, where node v Department of computer Science, Cornell est chain can be found very simply is selected with probability proportional to r", where ris the kat. University, Ithaca, New York 14853,USA A characteristic feature of small-world tice(Manhattan) distance between u and v, and a>0 is a fixed networks is that their diameter is exponen- clustering eponent. More generally, for p,q>1,each node whas Kochen, M (ed The Small World (Ablex. Norwood, N], 1989)- tially smaller than their size, being bounded a short-range connection to all nodes within plaice steps, and q 4. Albert, r e al Natur :401, 130-131(1999 y a polynomial in log N, where N is the long-range connections generated independently from a distribu- 5. Adamic, L. in Proc. Conference on Digital Libraries number of nodes. In other words, there is tion with clustering exponent a b, Lower bound from my charac nodes.This does not imply, however, that a of any decentralised algorthim satisfies Te art, where 6. Carmen. 7. eisersompeuter Science ot 16965 Beim, 9) decentralized algorithm will be able to dis- B=(2-d3 for 02, 7. peleg. D. Upfal, E L Assoc. Comput. Machinery 36,510-530 cover such short paths. My central finding and where c depends on a, p and q but not n c, Simulation of (1989). is that there is in fact a unique value of the the greedy algorithm on a 20,000 x 20,000 toroidal lattice, with Braitenberg, v& schiz, A. natomy of the Cortex (Springer, exponent a at which this is possible. random long-range connections as in a. Each data point is th 9. Killworth, P. Bernard. H Socinl Networks 1, 159-192( 1978). Then a= 2, so that long-range verage of 1, 000 runs. 10.Pirolli, P. Card, S. Psychol. Rev. 106, 643-675(1999). NatuRevOl40624august2000www.nature.com Me2000 Macmillan Magazines Ltd 845
T he small-world phenomenon — the principle that most of us are linked by short chains of acquaintances — was first investigated as a question in sociology1,2 and is a feature of a range of networks arising in nature and technology3–5. Experimental study of the phenomenon1 revealed that it has two fundamental components: first, such short chains are ubiquitous, and second, individuals operating with purely local information are very adept at finding these chains. The first issue has been analysed2–4, and here I investigate the second by modelling how individuals can find short chains in a large social network. I have found that the cues needed for discovering short chains emerge in a very simple network model. This model is based on early experiments1 , in which source individuals in Nebraska attempted to transmit a letter to a target in Massachusetts, with the letter being forwarded at each step to someone the holder knew on a first-name basis. The networks underlying the model follow the ‘small-world’ paradigm3 : they are rich in structured short-range connections and have a few random long-range connections. Long-range connections are added to a two-dimensional lattice controlled by a clustering exponent, a, that determines the probability of a connection between two nodes as a function of their lattice distance (Fig. 1a). Decentralized algorithms are studied for transmitting a message: at each step, the holder of the message must pass it across one of its short- or long-range connections; crucially, this current holder does not know the long-range connections of nodes that have not touched the message. The primary figure of merit for such an algorithm is its expected delivery time T, which represents the expected number of steps needed to forward a message between a random source and target in a network generated according to the model. It is crucial to constrain the algorithm to use only local information — with global knowledge of all connections in the network, the shortest chain can be found very simply6 . A characteristic feature of small-world networks is that their diameter is exponentially smaller than their size, being bounded by a polynomial in logN, where N is the number of nodes. In other words, there is always a very short path between any two nodes. This does not imply, however, that a decentralized algorithm will be able to discover such short paths. My central finding is that there is in fact a unique value of the exponent a at which this is possible. When a42, so that long-range connections follow an inverse-square distribution, there is a decentralized algorithm that achieves a very rapid delivery time; T is bounded by a function proportional to (logN) 2 . The algorithm achieving this bound is a ‘greedy’ heuristic: each message holder forwards the message across a connection that brings it as close as possible to the target in lattice distance. Moreover, a42 is the only exponent at which any decentralized algorithm can achieve a delivery time bounded by any polynomial in logN: for every other exponent, an asymptotically much larger delivery time is required, regardless of the algorithm employed (Fig. 1b). These results indicate that efficient navigability is a fundamental property of only some small-world structures. The results also generalize to d-dimensional lattices for any value of dà1, with the critical value of the clustering exponent becoming a4d. Simulations of the greedy algorithm yield results that are qualitatively consistent with the asymptotic analytical bounds (Fig. 1c). In the areas of communication networks7 and neuroanatomy8 , the issue of routing without a global network organization has been considered; also in social psychology and information foraging some of the cues that individuals use to construct paths through a social network or hyperlinked environment have been discovered9,10. Although I have focused on a very clean model, I believe that a more general conclusion can be drawn for small-world networks — namely that the correlation between local structure and long-range connections provides critical cues for finding paths through the network. When this correlation is near a critical threshold, the structure of the long-range connections forms a type of gradient that allows individuals to guide a message efficiently towards a target. As the correlation drops below this critical value and the social network becomes more homogeneous, these cues begin to disappear; in the limit, when long-range connections are generated uniformly at random, the result is a world in which short chains exist but individuals, faced with a disorienting array of social contacts, are unable to find them. Jon M. Kleinberg Department of Computer Science, Cornell University, Ithaca, New York 14853, USA 1. Milgram, S. Psychol. Today 1, 61–67 (1967). 2. Kochen, M. (ed.) The Small World (Ablex, Norwood, NJ, 1989). 3. Watts, D. & Strogatz, S. Nature 393, 440–442 (1998). 4. Albert, R. et al. Nature 401, 130–131 (1999). 5. Adamic, L. in Proc. 3rd European Conference on Digital Libraries (eds Abiteboul, S. & Vercoustre, A.-M.) 443–452 (Springer Lecture Notes in Computer Science, Vol. 1696, Berlin, 1999). 6. Cormen, T., Leiserson, C. & Rivest, R. Introduction to Algorithms (McGraw-Hill, Boston, 1990). 7. Peleg, D. & Upfal, E. J. Assoc. Comput. Machinery 36, 510–530 (1989). 8. Braitenberg, V. & Schüz, A. Anatomy of the Cortex (Springer, Berlin, 1991). 9. Killworth, P. & Bernard, H. Social Networks 1, 159–192 (1978). 10.Pirolli, P. & Card, S. Psychol. Rev. 106, 643–675 (1999). brief communications NATURE | VOL 406 | 24 AUGUST 2000 | www.nature.com 845 Navigation in a small world It is easier to find short chains between points in some networks than others. 0 01 2 3 4 0.2 Clustering exponent (α) Clustering exponent (α) 0.8 0.6 0.4. (2–α)/3 (α–2)/(α–1) 7.0 5.0 6.0 0 2 1 a c u d b v a b c Exponent β in lower bound on T In T for greedy algorithm Figure 1 The navigability of small-world networks. a, The network model is derived from an n2n lattice. Each node, u, has a shortrange connection to its nearest neighbours (a, b, c and d ) and a long-range connection to a randomly chosen node, where node v is selected with probability proportional to r 1a, where r is the lattice (‘Manhattan’) distance between u and v, and aà0 is a fixed clustering exponent. More generally, for p,qà1, each node u has a short-range connection to all nodes within p lattice steps, and q long-range connections generated independently from a distribution with clustering exponent a. b, Lower bound from my characterization theorem: when a ≠ 2, the expected delivery time T of any decentralized algorithm satisfies Tàcnb , where b4(21a)/3 for 0 a*2 and b4(a12)/(a11) for a¤2, and where c depends on a, p and q, but not n. c, Simulation of the greedy algorithm on a 20,000220,000 toroidal lattice, with random long-range connections as in a. Each data point is the average of 1,000 runs. © 2000 Macmillan Magazines Ltd