{"title": "Small-World Phenomena and the Dynamics of Information", "book": "Advances in Neural Information Processing Systems", "page_first": 431, "page_last": 438, "abstract": null, "full_text": "Small-World Phenomena and the\nDynamics of Information\nJon Kleinberg\n\nDepartment of Computer Science\nCornell University\nIthaca NY 14853\n1 Introduction\n\nThe problem of searching for information in networks like the World Wide Web can\nbe approached in a variety of ways, ranging from centralized indexing schemes to\ndecentralized mechanisms that navigate the underlying network without knowledge\nof its global structure. The decentralized approach appears in a variety of settings:\nin the behavior of users browsing the Web by following hyperlinks; in the design of\n\nfocused crawlers [4, 5, 8] and other agents that explore the Web's links to gather\ninformation; and in the search protocols underlying decentralized peer-to-peer sys-\ntems such as Gnutella [10], Freenet [7], and recent research prototypes [21, 22, 23],\nthrough which users can share resources without a central server.\nIn recent work, we have been investigating the problem of decentralized search\nin large information networks [14, 15]. Our initial motivation was an experiment\nthat dealt directly with the search problem in a decidedly pre-Internet context:\nStanley Milgram's famous study of the small-world phenomenon [16, 17]. Milgram\nwas seeking to determine whether most pairs of people in society were linked by\nshort chains of acquaintances, and for this purpose he recruited individuals to try\nforwarding a letter to a designated ``target'' through people they knew on a first-\nname basis. The starting individuals were given basic information about the target\n--- his name, address, occupation, and a few other personal details --- and had to\nchoose a single acquaintance to send the letter to, with goal of reaching the target\nas quickly as possible; subsequent recipients followed the same procedure, and the\nchain closed in on its destination. Of the chains that completed, the median number\nof steps required was six --- a result that has since entered popular culture as the\n``six degrees of separation'' principle [11].\nMilgram's experiment contains two striking discoveries --- that short chains are\npervasive, and that people are able to find them. This latter point is concerned\nprecisely with a type of decentralized navigation in a social network, consisting of\npeople as nodes and links joining pairs of people who know each other. From an\nalgorithmic perspective, it is an interesting question to understand the structure\nof networks in which this phenomenon emerges --- in which message-passing with\npurely local information can be e#cient.\n\nNetworks that Support E#cient Search. A model of a ``navigable'' network\nrequires a few basic features. It should contain short paths among all (or most)\npairs of nodes. To be non-trivial, its structure should be partially known and\n\f\npartially unknown to its constituent nodes; in this way, information about the known\nparts can be used to construct paths that make use of the unknown parts as well.\nThis is clearly what was taking place in Milgram's experiments: participants, using\nthe information available to them, were estimating which of their acquaintances\nwould lead to the shortest path through the full social network. Guided by these\nobservations, we turned to the work of Watts and Strogatz [25], which proposes a\nmodel of ``small-world networks'' that very concisely incorporates these features. A\nsimple variant of their basic model can be described as follows. One starts with\na p-dimensional lattice, in which nodes are joined only to their nearest neighbors.\nOne then adds k directed long-range links out of each node v, for a constant k; the\nendpoint of each link is chosen uniformly at random. Results from the theory of\nrandom graphs can be used to show that with high probability, there will be short\npaths connecting all pairs of nodes (see e.g. [3]); at the same time, the network will\nlocally retain a lattice-like structure. Asymptotically, our criterion for ``shortness''\nof paths is what one obtains from this and similar random constructions: there\nshould be paths whose lengths are bounded by a polynomial in log n, where n is\nthe number of nodes. We will refer to such a function as polylogarithmic.\n\nThis network model, a superposition of a lattice and a set of long-range links, is\na natural one in which to study the behavior of a decentralized search algorithm.\nThe algorithm knows the structure of the lattice; it starts from a node s, and is told\nthe coordinates of a target node t. It successively traverses links of the network so\nas to reach the target as quickly as possible; but, crucially, it does not know the\nlong-range links out of any node that it has not yet visited. In addition to moving\nforward across directed links, the algorithm may travel in reverse across any link\nthat it has already followed in the forward direction; this allows it to back up when\nit does not want to continue exploring from its current node. One can view this\nas hitting the ``back button'' on a Web browser --- or returning the letter to its\nprevious holder in Milgram's experiments, with instructions that he or she should\ntry someone else. We say that the algorithm has search time Y (n) if, on a randomly\ngenerated n-node network with s and t chosen uniformly at random, it reaches the\ntarget t in at most Y (n) steps with probability at least 1\n\n-\n\n#(n), for a function #()\n\ngoing to 0 with n.\n\nThe first result in [15] is that no decentralized algorithm can achieve a polyloga-\nrithmic search time in this network model --- even though, with high probability,\nthere are paths of polylogarithmic length joining all pairs of nodes. However, if we\ngeneralize the model slightly, then it can support e#cient search. Specifically, when\nwe construct a long-range link (v, w) out of v, we do not choose w uniformly at\nrandom; rather, we choose it with probability proportional to d -# , where d is the\nlattice distance from v to w. In this way, the long-range links become correlated to\nthe geometry of the lattice. We show in [15] that when # is equal to p, the dimen-\nsion of the underlying lattice, then a decentralized greedy algorithm achieves search\ntime proportional to log\n\n2\n\nn; and for any other value of #, there is no decentralized\nalgorithm with a polylogarithmic search time.\nRecent work by Zhang, Goel, and Govindan [26] has shown how the distribution of\nlinks associated with the optimal value of # may lead to improved performance for\ndecentralized search in the Freenet peer-to-peer system. Adamic, Lukose, Puniyani,\nand Huberman [2] have recently considered a variation of the decentralized search\nproblem in a network that has essentially no known underlying structure; however,\nwhen the number of links incident to nodes follows a power-law distribution, then\na search strategy that seeks high-degree nodes can be e#ective. They have applied\ntheir results to the Gnutella system, which exhibits such a structure. In joint\nwork with Kempe and Demers [12], we have studied how distributions that are\n\f\ninverse-polynomial in the distance between nodes can be used in the design of\n\ngossip protocols for spreading information in a network of communicating agents.\nThe goal of the present paper is to consider more generally the problem of decen-\ntralized search in networks with partial information about the underlying structure.\nWhile a lattice makes for a natural network backbone, we would like to understand\nthe extent to which the principles underlying e#cient decentralized search can be\nabstracted away from a lattice-like structure. We begin by considering networks\nthat are generated from a hierarchical structure, and show that qualitatively sim-\nilar results can be obtained; we then discuss a general model of group structures,\n\nwhich can be viewed as a simultaneous generalization of lattices and hierarchies.\nWe refer to k, the number of out-links per node, as the out-degree of the model.\nThe technical details of our results --- both in the statements of the results and the\nproofs --- are simpler when we allow the out-degree to be polylogarithmic, rather\nthan constant. Thus we describe this case first, and then move on to the case in\nwhich each node has only a constant number of out-links.\n2 Hierarchical Network Models\n\nIn a number of settings, nodes represent objects that can be classified according to\na hierarchy or taxonomy; and nodes are more likely to form links if they belong to\nthe same small sub-tree in the hierarchy, indicating they are more closely related.\nTo construct a network model from this idea, we represent the hierarchy using a\ncomplete b-ary tree T , where b is a constant. Let V denote the set of leaves of T ; we\nuse n to denote the size of V , and for two leaves v and w, we use h(v, w) to denote the\nheight of the least common ancestor of v and w in T . We are also given a monotone\nnon-increasing function f() that will determine link probabilities. For each node\n\nv\n\n#\n\nV , we create a random link to w with probability proportional to f(h(v, w)); in\nother words, the probability of choosing w is equal to f(h(v, w))/\n\n#\n\nx#=v f(h(v, x)).\n\nWe create k links out of each node v this way, choosing the endpoint w each time\nindependently and with repetition allowed. This results in a graph G on the set V .\nFor the analysis in this section, we will take the out-degree to be k = c log\n\n2\n\nn, for\na constant c. It is important to note that the tree T is used only in the generation\nprocess of G; neither the edges nor the non-leaf nodes of T appear in G. (By way\nof contrast, the lattice model in [15] included both the long-range links and the\nnearest-neighbor links of the lattice itself.) When we use the term ``node'' without\nany qualification, we are referring to nodes of G, and hence to leaves of T ; we will\nuse ``internal node'' to refer to non-leaf nodes of T .\nWe refer to the process producing G as a hierarchical model with exponent # if the\nfunction f(h) grows asymptotically like b -#h :\nlim\n\nh##\n\nf(h)\nb -#\n\n# h\n\n= 0 for all # # and lim\n\nh##\n\nb -#\n\n## h\n\nf(h)\n\n= 0 for all # ## > #.\nThere are several natural interpretations for a hierarchical network model. One is in\nterms of the World Wide Web, where T is a topic hierarchy such as www.yahoo.com.\n\nEach leaf of T corresponds to a Web page, and its path from the root speci-\nfies an increasingly fine-grained description of the page's topic. Thus, a partic-\nular leaf may be associated with Science/Computer Science/Algorithms or with\n\nArts/Music/Opera. The linkage probabilities then have a simple meaning --- they\nare based on the distance between the topics of the pages, as measured by the\nheight of their least common ancestor in the topic hierarchy. A page on Sci-\n\f\nence/Computer Science/Algorithms may thus be more likely to link to one on Sci-\nence/Computer Science/Machine Learning than to one on Arts/Music/Opera. Of\ncourse, the model is a strong simplification, since topic structures are not fully hier-\narchical, and certainly do not have uniform branching and depth. It is worth noting\nthat a number of recent models for the link structure of the Web, as well as other\nrelational structures, have looked at di#erent ways in which similarities in content\ncan a#ect the probability of linkage; see e.g. [1, 6, 9].\nAnother interpretation of the hierarchical model is in terms of Milgram's original\nexperiment. Studies performed by Killworth and Bernard [13] showed that in choos-\ning a recipient for the letter, participants were overwhelmingly guided by one of two\ncriteria: similarity to the target in geography, or similarity to the target in occu-\npation. If one views the lattice as forming a simple model for geographic factors,\nthe hierarchical model can similarly be interpreted as forming a ``topic hierarchy''\nof occupations, with individuals at the leaves. Thus, for example, the occupations\nof ``banker'' and ``stock broker'' may belong to the same small sub-tree; since the\ntarget in one of Milgram's experiments was a stock broker, it might therefore be\na good strategy to send the letter to a banker. Independently of our work here,\nWatts, Dodds, and Newman have recently studied hierarchical structures for mod-\neling Milgram's experiment in social networks [24].\nWe now consider the search problem in a graph G generated from a hierarchical\nmodel: A decentralized algorithm has knowledge of the tree T , and knows the\nlocation of a target leaf that it must reach; however, it only learns the structure of\n\nG as it visits nodes. The exponent # determines how the structures of G and T\n\nare related; how does this a#ect the navigability of G? In the analysis of the lattice\nmodel [15], the key property of the optimal exponent was that, from any point, there\nwas a reasonable probability of a long-range link that halved the distance to the\ntarget. We make use of a similar idea here: when # = 1, there is always a reasonable\nprobability of finding a long-range link into a strictly smaller sub-tree containing\nthe target. As mentioned above, we focus here on the case of polylogarithmic out-\ndegree, with the case of constant out-degree deferred until later.\n\nTheorem 2.1 (a) There is a hierarchical model with exponent # = 1 and poly-\nlogarithmic out-degree in which a decentralized algorithm can achieve search time\n\nO(logn).\n\n(b) For every #\n\n#=\n\n1, there is no hierarchical model with exponent # and polylog-\narithmic out-degree in which a decentralized algorithm can achieve polylogarithmic\nsearch time.\n\nDue to space limitations, we omit proofs from this version of the paper. Complete\nproofs may be found in the extended version, which is available on the author's\nWeb page (http://www.cs.cornell.edu/home/kleinber/).\nTo prove (a), we show that when the search is at a node v whose least common\nancestor with the target has height h, there is a high probability that v has a link\ninto the sub-tree of height h-1 containing the target. In this way, the search reaches\nthe target in logarithmically many steps. To prove (b), we exhibit a sub-tree T #\n\ncontaining the target such that, with high probability, it takes any decentralized\nalgorithm more than a polylogarithmic number of steps to find a link into T # .\n3 Group Structures\n\nThe analysis of the search problem in a hierarchical model is similar to the anal-\nysis of the lattice-based approach in [15], although the two types of models seem\n\f\nsuperficially quite di#erent. It is natural to look for a model that would serve as a\nsimultaneous generalization of each.\nConsider a collection of individuals in a social network, and suppose that we know\nof certain groups to which individuals belong --- people who live in the same town,\nor work in the same profession, or have some other a#liation in common. We could\nimagine that people are more likely to be connected if they both belong to the\nsame small group. In a lattice-based model, there may be a group for each subset\nof lattice points contained in a common ball (grouping based on proximity); in a\nhierarchical model, there may be a group for each subset of leaves contained in a\ncommon sub-tree. We now discuss the notion of a group structure, to make this\nprecise; we follow a model proposed in joint work with Kempe and Demers [12],\nwhere we were concerned with designing gossip protocols for lattices and hierarchies.\nA technically di#erent model of a#liation networks, also motivated by these types\nof issues, has been studied recently by Newman, Watts, and Strogatz [18].\nA group structure consists of an underlying set V of nodes, and a collection of\nsubsets of V (the groups). The collection of groups must include V itself; and it\nmust satisfy the following two properties, for constants # 1 and # > 1.\n(i) If R is a group of size q\n\n#\n\n2 containing a node v, then there is a group R #\n\n#\n\nR\n\ncontaining v that is strictly smaller than R, but has size at least #q.\n\n(ii) If R 1 , R 2 , R 3 , . . . are groups that all have size at most q and all contain a\ncommon node v, then their union has size at most #q.\n\nThe reader can verify that these two properties hold for the collection of balls in a\nlattice, as well as for the collection of sub-trees in a hierarchy. However, it is easy\nto construct examples of group structures that do not arise in this way from lattices\nor hierarchies.\nGiven a group structure (V,\n\n{R\n\ni\n\n}),\n\nand a monotone non-increasing function f(), we\nnow consider the following process for generating a graph on V . For two nodes v\n\nand w, we use q(v, w) to denote the minimum size of a group containing both v and\n\nw. (Note that such a group must exist, since V itself is a group.) For each node\n\nv\n\n#\n\nV , we create a random link to w with probability proportional to f(q(v, w));\n\nrepeating this k times independently yields k links out of v. We refer to this as a\n\ngroup-induced model with exponent # if f(q) grows asymptotically like q -# :\nlim\n\nh##\n\nf(q)\nq -#\n\n#\n\n= 0 for all # # and lim\n\nh##\n\nq -#\n\n##\n\nf(q)\n\n= 0 for all # ## > #.\nA decentralized search algorithm in such a network is given knowledge of the full\ngroup structure, and must follow links of G to a designated target t. We now state\nan analogue of Theorem 2.1 for group structures.\n\nTheorem 3.1 (a) For every group structure, there is a group-induced model with\nexponent # = 1 and polylogarithmic out-degree in which a decentralized algorithm\ncan achieve search time O(logn).\n\n(b) For every # 1, there is no group-induced model with exponent # and polylog-\narithmic out-degree in which a decentralized algorithm can achieve polylogarithmic\nsearch time.\n\nNotice that in a hierarchical model, the smallest group (sub-tree) containing two\nnodes v and w has size b\n\nh(v,w)\n\n, and so Theorem 3.1(a) implies Theorem 2.1(a).\nSimilarly, on a lattice, the smallest group (ball) containing two nodes v and w at\n\f\nlattice distance d has size #(d\n\np\n\n), and so Theorem 3.1(a) implies a version of the\nresult from [15], that e#cient search is possible in a lattice model when nodes form\nlinks with probability d -p . (In the version of the lattice result implied here, there\nare no nearest-neighbor links at all; but each node has a polylogarithmic number\nof out-links.)\nThe proof of Theorem 3.1(a) closely follows the proof of Theorem 2.1(a). We con-\nsider a node v --- the current point in the search --- for which the smallest group\ncontaining v and the target t has size q. Using group structure properties (i) and\n(ii), we show there is a high probability that v has a link into a group containing t of\nsize between #\n\n2\n\nq and #q. In this way, the search passes through groups containing\n\nt of sizes that diminish geometrically, and hence it terminates in logarithmic time.\nNote that Theorem 3.1(b) only considers exponents # 1. This is because there\nexist group-induced models with exponents # > 1 in which decentralized algorithms\ncan achieve polylogarithmic search time. For example, consider an undirected graph\n\nG # in which each node has 3 neighbors, and each pair of nodes can be connected\nby a path of length O(log n). It is possible to define a group structure satisfying\nproperties (i) and (ii) in which each edge of G # appears as a 2-node group; but then,\na graph G generated from a group-induced model with a very large exponent # will\ncontain all edges of G # with high probability, and a decentralized search algorithm\nwill be able to follow these edges directly to construct a short path to the target.\nHowever, a lower bound for the case # > 1 can be obtained if we place one additional\nrestriction on the group structure. Give a group structure (V,\n\n{R\n\ni\n\n}),\n\nand a cut-o#\nvalue q, we define a graph H(q) on V by joining any two nodes that belong to a\ncommon group of size at most q. Note that H(q) is not a random graph; it is defined\nsimply in terms of the group structure and q. We now argue that if many pairs of\nnodes are far apart in H(q), for a suitably large value of q, then a decentralized\nalgorithm cannot be e#cient when # > 1.\n\nTheorem 3.2 Let (V,\n\n{R\n\ni\n\n})\n\nbe a group structure. Suppose there exist constants\n\n#, # > 0 so that a constant fraction of all pairs of nodes have shortest-path distance\n\n# n\n\n#\n\n) in H(n\n\n#\n\n). Then for every # > 1, there is no group-induced model on (V,\n\n{R\n\ni\n\n})\n\nwith exponent # and a polylogarithmic number of out-links per node in which a\ndecentralized algorithm can achieve polylogarithmic search time.\n\nNotice this property holds for group structures arising from both lattices and hi-\nerarchies; in a lattice, a constant fraction of all pairs in H(n\n\n1/2p\n\n) have distance\n#\n\nn\n\n1/2p\n\n), while in a hierarchy, the graph H(n\n\n#\n\n) is disconnected for every # 1.\n4 Nodes with a Constant Number of Out-Links\n\nThus far, by giving each node more than a constant number of out-links, we have\nbeen able to design very simple search algorithms in networks generated according\nto the optimal exponent #. From each node, there is a way to make progress toward\nthe target node t, and so the structure of the graph G funnels the search towards\nits destination. When the out-degree is constant, however, things get much more\ncomplicated. First of all, with high probability, many nodes will have all their\nlinks leading ``away'' from the target in the hierarchy. Second, there is a constant\nprobability that the target t will have no in-coming links, and so the whole task\nof finding t becomes ill-defined. This indicates that the statement of the results\nthemselves in this case will have to be somewhat di#erent.\nIn this section, we work with a hierarchical model, and construct graphs with con-\n\f\nstant out-degree k; the value of k will need to be su#ciently large in terms of other\nparameters of the model. It is straightforward to formulate an analogue of our\nresults for group structures, but we do not go into the details of this here.\nTo deal with the problem that t itself may have no incoming links, we relax the\nsearch problem to that of finding a cluster of nodes containing t. In a topic-based\nmodel of Web pages, for example, we can consider t as a representative of a desired\ntype of page, with goal being to find any page of this type. Thus, we are given a\ncomplete b-ary tree T , where b is a constant; we let L denote the set of leaves of\n\nT , and m denote the size of L. We place r nodes at each leaf of T , forming a set\n\nV of n = mr nodes total. We then define a graph G on V as in Section 2: for a\nnon-increasing function f(), we create k links out of each node v\n\n#\n\nV , choosing w\n\nas an endpoint with probability proportional to f(h(v, w)). As before, we refer to\nthis process as a hierarchical model with exponent #, for the appropriate value of\n\n#. We refer to each set of r nodes at a common leaf of T as a cluster, and define\nthe resolution of the hierarchical model to be the value r.\n\nA decentralized algorithm is given knowledge of T , and a target node t; it must\nreach any node in the cluster containing t. Unlike the previous algorithms we have\ndeveloped, which only moved forward across links, the algorithm we design here will\nneed to make use of the ability to travel in reverse across any link that it has already\nfollowed in the forward direction. Note also that we cannot easily reduce the current\nsearch problem to that of Section 2 by collapsing clusters into ``super-nodes,'' since\nthere are not necessarily links joining nodes within the same cluster.\nThe search task clearly becomes easier as the resolution of the model (i.e. the size of\nclusters) becomes larger. Thus, our goal is to achieve polylogarithmic search time\nin a hierarchical model with polylogarithmic resolution.\n\nTheorem 4.1 (a) There is a hierarchical model with exponent # = 1, constant\nout-degree, and polylogarithmic resolution in which a decentralized algorithm can\nachieve polylogarithmic search time.\n(b) For every #\n\n#=\n\n1, there is no hierarchical model with exponent #, constant out-\ndegree, and polylogarithmic resolution in which a decentralized algorithm can achieve\npolylogarithmic search time.\n\nThe search algorithm used to establish part (a) operates in phases. It begins each\nphase j with a collection of #(log n) nodes all belonging to the sub-tree T j that con-\ntains the target t and whose root is at depth j. During phase j, it explores outward\nfrom each of these nodes until it has discovered a larger but still polylogarithmic-\nsized set of nodes belonging to T j . From among these, there is a high probability\nthat at least #(log n) have links into the smaller sub-tree T j+1 that contains t and\nwhose root is at depth j + 1. At this point, phase j + 1 begins, and the process\ncontinues until the cluster containing t is found.\n\nAcknowledgments\n\nMy thinking about models for Web graphs and social networks has benefited greatly\nfrom discussions and collaboration with Dimitris Achlioptas, Avrim Blum, Dun-\ncan Callaway, Michelle Girvan, John Hopcroft, David Kempe, Ravi Kumar, Tom\nLeighton, Mark Newman, Prabhakar Raghavan, Sridhar Rajagopalan, Steve Stro-\ngatz, Andrew Tomkins, Eli Upfal, and Duncan Watts. The research described here\nwas supported in part by a David and Lucile Packard Foundation Fellowship, an\nONR Young Investigator Award, NSF ITR/IM Grant IIS-0081334, and NSF Faculty\nEarly Career Development Award CCR-9701399.\n\f\nReferences\n\n[1] D. Achlioptas, A. Fiat, A. Karlin, F. McSherry, ``Web search via hub synthesis,'' Proc.\n42nd IEEE Symp. on Foundations of Computer Science, 2001.\n[2] L. Adamic, R. Lukose, A. Puniyani, B. Huberman, ``Search in Power-Law Networks,''\n\nPhys. Rev. E, 64 46135 (2001)\n[3] B. Bollobas, F. Chung, ``The diameter of a cycle plus a random matching,'' SIAM\nJ. Disc. Math. 1(1988).\n[4] S. Chakrabarti, M. van den Berg, B. Dom, ``Focused crawling: A new approach to\ntopic-specific Web resource discovery,'' Proc. 8th Intl. World Wide Web Conf., 1999.\n[5] J. Cho, H. Garcia-Molina, L. Page, ``E#cient Crawling Through URL Ordering,'' Proc.\n7th Intl. World Wide Web Conf., 1998.\n[6] D. Cohn and T. Hofmann, ``The Missing Link -- A Probabilistic Model of Document\nContent and Hypertext Connectivity,'' Adv. Neural Inf. Proc. Sys. (NIPS) 13, 2000.\n[7] I. Clarke, O. Sandberg, B. Wiley, T. Hong, ``Freenet: A Distributed Anonymous In-\nformation Storage and Retrieval System,'' International Workshop on Design Issues in\nAnonymity and Unobservability, 2000.\n[8] M. Diligenti, F.M. Coetzee, S. Lawrence, C.L. Giles, M. Gori, ``Focused Crawling Using\nContext Graphs,'' Proc. 26th Intl. Conf. on Very Large Databases (VLDB), 2000.\n[9] L. Getoor, N. Friedman, D. Koller, and B. Taskar. ``Learning Probabilistic Models of\nRelational Structure,'' Proc. 18th International Conference on Machine Learning, 2001.\n[10] Gnutella. http://gnutella.wego.com.\n[11] J. Guare, Six Degrees of Separation: A Play (Vintage Books, New York, 1990).\n[12] D. Kempe, J. Kleinberg, A. Demers. ``Spatial gossip and resource location protocols,''\n\nProc. 33rd ACM Symp. on Theory of Computing, 2001.\n[13] P. Killworth, H. Bernard, ``Reverse small world experiment,'' Social Networks 1(1978).\n[14] J. Kleinberg. ``Navigation in a Small World.'' Nature 406(2000).\n[15] J. Kleinberg. ``The small-world phenomenon: An algorithmic perspective.'' Proc. 32nd\nACM Symposium on Theory of Computing, 2000. Also appears as Cornell Computer\nScience Technical Report 99-1776 (October 1999).\n[16] M. Kochen, Ed., The Small World (Ablex, Norwood, 1989).\n[17] S. Milgram, ``The small world problem,'' Psychology Today 1(1967).\n[18] M. Newman, D. Watts, S. Strogatz, ``Random graph models of social networks,'' Proc.\nNatl. Acad. Sci., to appear.\n[19] A. Oram, editor, Peer-to-Peer: Harnessing the Power of Disruptive Technologies\n\nO'Reilly and Associates, 2001.\n[20] A. Puniyani, R. Lukose, B. Huberman, ``Intentional Walks on Scale Free Small\nWorlds,'' HP Labs Information Dynamics Group, at http://www.hpl.hp.com/shl/.\n[21] S. Ratnasamy, P. Francis, M. Handley, R. Karp, S. Shenker, ``A Scalable Content-\nAddressable Network,'' Proc. ACM SIGCOMM, 2001\n[22] A. Rowstron, P. Druschel, ``Pastry: Scalable, distributed object location and routing\nfor large-scale peer-to-peer systems,'' Proc. 18th IFIP/ACM International Conference\non Distributed Systems Platforms (Middleware 2001), 2001.\n[23] I. Stoica, R. Morris, D. Karger, F. Kaashoek, H. Balakrishnan, ``Chord: A Scalable\nPeer-to-peer Lookup Service for Internet Applications,'' Proc. ACM SIGCOMM, 2001\n[24] D. Watts, P. Dodds, M. Newman, personal communication, December 2001.\n[25] D. Watts, S. Strogatz, ``Collective dynamics of small-world networks,'' Nature\n\n393(1998).\n[26] H. Zhang, A. Goel, R. Govindan, ``Using the Small-World Model to Improve Freenet\nPerformance,'' Proc. IEEE Infocom, 2002.\n\f\n", "award": [], "sourceid": 2061, "authors": [{"given_name": "Jon", "family_name": "Kleinberg", "institution": null}]}