This dissertation studies routing in small-world networks such as grids plus long-range edges and real networks. Kleinberg showed that geography-based greedy routing in a grid-based network takes an expected number of steps polylogarithmic in the network size, thus justifying empirical efficiency observed beginning with Milgram.
Download count: 0
- Partial requirement for: Ph.D., Arizona State University, 2011Note typethesis
- Includes bibliographical references (p. 125-129)Note typebibliography
- Field of study: Computer science