A tutorial on Navigation in the Network of Individual Acquaintances
by Pierre Fraigniaud
(NoNA Spring School on Algorithms,
Istanbul, 12-15 March, 2009)
Abstract
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:
- extensions of the augmented graph model, and variants of greedy routing,
- identification of graph classes for which greedy routing performs efficiently,
- the quest for universal augmentation schemes,
- validation of the model, and
- analysis of dynamic processes from which navigability emerges.
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.