The small-world phenomenon: an algorithmic perspective
By Jon M. Kleinberg. 2000
2,245 citations recorded by the source corpus.
A method of improving certain characteristics of cadmium mercury telluride single crystal material by heat treating the single crystal material in the presence of both tellurium and mercury.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Algorithms & Complexity
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Charu C. Aggarwal
- Jure Leskovec
- Yoshua Bengio
- Philip S. Yu
- Percy Liang
- Ji-rong Wen
- Wayne Xin Zhao
- Quoc V. Le
In Computational Theory and Mathematics
- Remco van der Hofstad
- Jure Leskovec
- Mark Newman
- Marc Barthelemy
- Christos Faloutsos
- Yury Malkov
- Grant Robert Schoenebeck
- Dmitry A. Yashunin
In Algorithms & Complexity
- Mark Newman
- Jure Leskovec
- Marc Barthelemy
- Grant Robert Schoenebeck
- Christos Faloutsos
- Jon M. Kleinberg
- Laurent Massoulié
- Gurmeet Singh Manku
Citations in the corpus
- Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (2016, background): “Kleinberg [31], [41] as social networkmodels for the famousMilgram experiment [42].”
- VoroNet: A scalable object network based on Voronoi tessellations (positive): “The proof is directly adapted from the proof proposed by Kleinberg[7] in the case of 2D grids.”
- Small-World Phenomena and the Dynamics of Information (2001, background): “Thus, for example, the occupations of “banker” and “stock broker” may belong to the same small sub-tree; since the target in one of Milgram’s experiments was a stock broker, it might therefore be a good strategy to send the letter to a banker.”
- Mercury: supporting scalable multi-attribute range queries (2004, methodology): “This guarantee is based upon Kleinberg’s analysis of smallworld networks [14].”
- A survey and comparison of peer-to-peer overlay network schemes (2005, methodology): “This idea is based on the intuition from the small-world models [39] and theoretical results by Kleinberg [39].”
- Nodes bearing grudges: towards routing security, fairness, and robustness in mobile ad hoc networks (2002, background): “Other interesting issues include rumor spreading and transitive trust in a ‘small world ’ [10] and how it could be used to locate friends.”
- Web Data Extraction, Applications and Techniques: A Survey (2012, background): “For example, collecting digital traces produced by users of Social Web platforms like Facebook, YouTube or Flickr is the key step to understand, model and predict human behavior [68,94,3].”
- Scalable Distributed Algorithm for Approximate Nearest Neighbor Search Problem in High Dimensional General Metric Spaces (2012, methodology): “For the greedy search algorithm to be logarithmically scalable, the small world network should have the navigation property [7].”
- Dense Text Retrieval Based on Pretrained Language Models: A Survey (2022, background): “Such approaches are efficient due to the small world phenomenon [260]: the average path length of between two vertices is short.”
- Approximate Nearest Neighbor Search Small World Approach (2011, methodology): “ There exist algorithms for building small world networks that have the ability to perform nearest neighbor and addition of a new object to the structure with complexity of [8].”
- Efficient k-nearest neighbor graph construction for generic similarity measures (2011, background): “is similar to decentralized search of small-world networks [14] (global optimization).”
- Critical phenomena in complex networks (2007, methodology): “The sparse network with exponent α equal to d is unique in the following respect described by Kleinberg (1999, 2000, 2006).”
- Trust and nuanced profile similarity in online social networks (2009, background): “They all have small world properties [Watts 2003; Kleinberg 2000] and their degree distribution follows the power law distribution [Barabasi and Albert 1999].”
- Symphony: Distributed Hashing in a Small World (2003, methodology): “Kleinberg [10] analyzed a static network in which each participant knows n precisely, has one long distance link corresponding to pn, manages a sub-range of size 1=n and always routes clockwise.”