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. A counterpart for the grid-based model is provided; it creates all edges deterministically and shows an asymptotically matching upper bound on the route length. The main goal is to improve greedy routing through a decentralized machine learning process.
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