Navigation in a small world

By Jon M. Kleinberg. Nature, 2000

974 citations recorded by the source corpus.

Subfields: Sociology and Political Science, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/cfed87559dcba4f06742e091fa97041588562aa9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Sociology and Political Science

In Statistical and Nonlinear Physics

Citations in the corpus

Statistical mechanics of complex networks (2001, background): “…topology plays an important role in determining synchronization in a complex network, but search and random walks in complex networks is also a much investigated topic (Huberman et al., 1998; Kleinberg, 2000; Adamic et al., 2001; Bilke and Peterson, 2001; Burda et al., 2001; Walsh, 2001).”
Random Graphs and Complex Networks (2016, background): “In [169, 170], the problem is addressed how hard it is to find short paths in small-world networks on the d-dimensional lattice, finding that navigation sensitively depends upon how likely it is for large edges to be present.”
Music recommendation and discovery in the long tail (2008, background): “This is an important property, because recommender systems can be structurally optimised to allow surfing to any part of a music collection with a few of mouse clicks, and so that they are easy to navigate using only local information (Kleinberg, 2000; Newman, 2003b).”
Topic and Role Discovery in Social Networks (2005, methodology): “They find that in the case of an email network at HP Labs, a greedy search strategy works eciently as predicted by Kleinberg (2000) and Watts, Dodds, and Newman (2002).”
Network Properties Revealed through Matrix Functions (2010, background): “small world experiments of Stanley Milgram [58], messages were passed along social acquaintance links by individuals who did not have knowledge of the overall topology, even though surprisingly short walks emerged on average [51].”
Four degrees of separation (2011, result): “Indeed, we see in this study, as well as other studies of Facebook [1] that, while the world is connected enough for short paths to exist between most nodes, there is a high degree of locality induced by various externalities, geography chief amongst them, all reminiscent of the model proposed in [1”
A small world of weak ties provides optimal global integration of self-similar modules in functional brain networks (2011, background): “statistical physics makes precise predictions about optimization schemes for global function as a function of the shortcut exponent α and df (25, 44, 45).”
Resisting structural re-identification in anonymized social networks (2008, neutral): “connectdistantregionsofthemeshwithonlyafewhops[47] and meshes [ 24 ].”
The “New” Science of Networks (2004, background): “In fact, Kleinberg proved that only when γ = d , the dimension of the underlying lattice, would the network be searchable in the sense that the number of steps target is “short” 4 (Kleinberg 2000a).”