  Dating back to two famous experiments by the social-psychologist, Stanley
Milgram, in the 1960s, the small-world phenomenon is the idea that all people
are connected through a short chain of acquaintances that can be used to route
messages. Many subsequent papers have attempted to model this phenomenon, with
most concentrating on the "short chain" of acquaintances rather than their
ability to efficiently route messages. In this paper, we study the small-world
navigability of the U.S. road network, with the goal of providing a model that
explains how messages in the original small-world experiments could be routed
along short paths using U.S. roads. To this end, we introduce the Neighborhood
Preferential Attachment model, which combines elements from Kleinberg's model
and the Barab\'asi-Albert model, such that long-range links are chosen
according to both the degrees and (road-network) distances of vertices in the
network. We empirically evaluate all three models by running a decentralized
routing algorithm, where each vertex only has knowledge of its own neighbors,
and find that our model outperforms both of these models in terms of the
average hop length. Moreover, our experiments indicate that similar to the
Barab\'asi-Albert model, networks generated by our model are scale-free, which
could be a more realistic representation of acquaintanceship links in the
original small-world experiment.
