THESIS FOR THE DEGREE OF LICENTIATE OFPHILOSOPHYSearching in a Small WorldOskar SandbergDivision of Mathematical StatisticsDepartment of Mathematical SciencesChalmers University of Technology and G¨oteborg UniversityG¨oteborg, Sweden 2005Searching in a Small WorldOskar Sandbergc°Oskar Sandberg, 2005NO 2005:52ISSN 1652-9715Division of Mathematical StatisticsDepartment of Mathematical SciencesChalmers University of Technology and G¨oteborg UniversitySE-412 96 G¨oteborgSwedenTelephone +46 (0)31 772 1000Printed in G¨oteborg, Sweden 2005Searching in a Small WorldOskar SandbergDepartment of Mathematical SciencesChalmers University of TechnologyG¨oteborg UniversityAbstractThe small-world phenomenon, that the world’s social networkis tightly connected, and that any two people can be linked by ashort chain of friends, has long been a subject of interest. Famously,the psychologist Stanley Milgram performed an experiment wherehe asked people to deliver a letter to a stranger by forwarding itto an acquaintance, who could forward it to one his acquaintances,and so on until the destination was reached. The results seemed toconfirm that the small-world phenomenon is real. Recently it hasbeen shown by Jon Kleinberg that in order to search in a network,that is to actually find the short paths in the manner of the Milgramexperiment, a very special type of a graph model is needed.In this thesis, we present two ideas about searching in the smallworld stemming from Kleinberg’s results. In the first we study theformation of networks of this type, attempting to see why the kindof connections necessary may arise naturally. A different criterionon the network which also makes the efficient searches possible isderived, and based on it an algorithmic model is proposed for howsearching can become possible as a network evolves.In the second paper, we propose a method for searching in small-world networks even when the participants are oblivious to their ownand others positions in the world. This is done by assigning nodespositions in an idealized world based on the clustering of connectionsbetween them, and then searching based on these positions. Theproblem is motivated by applications to computer networks, and ourmethod is tested on real world data.iiiAcknowledgementsIt feels premature to make acknowledgments when the real taskis far from completed, but I am thankful for the continued supportof my advisers Olle H¨aggstr¨om and Devdatt Dubhashi, as well as thekindness and understanding of my initial adviser Nanny Wermuth.Thanks to Ian Clarke in discussion with whom many of these ideasfirst arose. Also thanks to Ilona, Johan, Mikael, Peter, S˜ao, myofficemate Viktor and all the other people at the Department ofMathematical Sciences who make spending almost all my wakingtime at work an eminently enjoyable way of life.vContents1 Introduction 11.1 Milgram’s Small-World Experiment . . . . . . . . . . . 11.2 The Mathematics of Small Worlds . . . . . . . . . . . 51.3 Navigation . . . . . . . . . . . . . . . . . . . . . . . . . 81.3.1 Why Navigation Matters . . . . . . . . . . . . 91.4 Kleinberg’s Results . . . . . . . . . . . . . . . . . . . . 101.5 Summary of Contributions . . . . . . . . . . . . . . . . 162 Neighbor Selection 172.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 172.1.1 Shortcut Graphs . . . . . . . . . . . . . . . . . 172.1.2 Contribution . . . . . . . . . . . . . . . . . . . 182.1.3 Previous Work . . . . . . . . . . . . . . . . . . 192.2 Results and Discussion . . . . . . . . . . . . . . . . . . 202.2.1 Distribution and Hitting Probability . . . . . . 202.2.2 Balanced Shortcuts . . . . . . . . . . . . . . . . 232.2.3 Other Graphs . . . . . . . . . . . . . . . . . . . 262.3 Re-wiring Algorithm . . . . . . . . . . . . . . . . . . . 302.3.1 Computer Simulation . . . . . . . . . . . . . . 312.3.2 Markov Chain View . . . . . . . . . . . . . . . 322.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 363 Distributed Routing 393.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 393.1.1 Motivation . . . . . . . . . . . . . . . . . . . . 403.1.2 Contribution . . . . . . . . . . . . . . . . . . . 40vii3.1.3 Previous Work . . . . . . . . . . . . . . . . . . 423.2 Kleinberg’s Model . . . . . . . . . . . . . . . . . . . . 423.3 The Problem . . . . . . . . . . . . . . . . . . . . . . . 443.4 Statement . . . . . . . . . . . . . . . . . . . . . . . . . 443.4.1 Metropolis-Hastings Algorithm . . . . . . . . . 463.4.2 MCMC on the Positions . . . . . . . . . . . . . 463.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . 483.6 Experimental Methodology . . . . . . . . . . . . . . . 483.6.1 One-Dimensional Case . . . . . . . . . . . . . . 483.6.2 Two Dimensional Case . . . . . . . . . . . . . . 503.6.3 Real World Data . . . . . . . . . . . . . . . . . 513.7 Experimental Results and Analysis . . . . . . . . . . . 523.7.1 One Dimensional Case . . . . . . . . . . . . . . 523.7.2 Two Dimensional Case . . . . . . . . . . . . . . 573.7.3 Real World Data . . . . . . . . . . . . . . . . . 603.8 Distributed Implementation and Practical Applications 633.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 64viiiChapter 1Introduction1.1 Milgram’s Small-World ExperimentIt has almost become clich´e to start out a work on random networkswith a reference to experimental psychologist Stanley Milgram’s fa-mous …