The notion that the world's social network is tightly connected and that any two people can be linked by a short chain of friends, known as the small-world phenomenon, has long been a subject of interest. Famously, the psychologist Stanley Milgram performed an experiment to investigate how long it would take for letters to cross the United States going from friend to friend. The results seemed to confirm that the small-world phenomenon is real. More recently it has been shown by Jon Kleinberg that for it to be possible to efficiently search for paths in a random graph with only local knowledge, as Milgram's subjects did, the graph must have certain special properties. Such graphs, known as navigable networks, must combine structured and random elements.
We start out from Kleinberg's work and explore a series of results and ideas related to navigable graphs. Firstly, in two different models, we explore possible dynamics which could explain the emergence of navigability. The first model shows how a graph can adapt to navigability if one allows the edges to be re-wired based on the results of past searches, while the second model shows that navigability arises directly if vertices cluster with respect to two independent spaces in a certain, intuitively clear, manner.
The final two works take different perspectives. The first of these views the small world as a random graph and looks at its connectivity properties in the classical sense. Our results bridge a gap between previously understood results from random graph theory, and results from the study of percolation. In the second, final, work we propose a method for searching in small-world networks even when the participants are oblivious to their own and others positions in the world. The problem is motivated by applications to computer networks, and our method is tested on real world data.