A tutorial on Navigation in the Network of Individual Acquaintances by Pierre Fraigniaud

(NoNA Spring School on Algorithms, Istanbul, 12-15 March, 2009)


The small world phenomenon, a.k.a. the six degree of separation between individuals, was identified by the phycho-sociologist Stanley Milgram at the end of the 60s. Milgram series of experiments demonstrated that letters from arbitrary sources and bound to an arbitrary target can be transmitted along short chains of closely related individuals, based solely on some characteristics of the target (professional occupation, state of leaving, etc.). In his paper on small world navigability, Jon Kleinberg [STOC, 2000] modeled the small world phenomenon in the framework of augmented graphs, and analyzed the performances of greedy routing in augmented multi-dimensional meshes. This tutorial will survey the results of his analysis, and the results that followed up Kleinberg seminal work, including: These various subjects will be as many opportunities to learn techniques from algorithm design and analysis (deterministic and probabilitic), graph theory, and analysis of randomized (e.g., Markovian) processes.