Mapping small worlds

Social networks are usually navigable small worlds: individuals are able to find short chains of acquaintances connecting pairs of unrelated nodes. This property can be explained by the fact that nodes are characterized by a series of properties, such as geographical position, work or educational background; the navigation proceeds towards the node that is "most similar" to the destination. Since nodes are likely to be linked with similar individuals, this strategy permits to quickly reach the destination. We approach the problem of creating the information that makes a network navigable. Starting from a given network, and without any other information, we show how nodes can reconstruct, with a scalable and decentralized algorithm, a "network map ": a d-dimensional layout that places nodes in a way that reflects the network structure, so that navigability is achieved. Euclidean distance on the layout is used as a measure for node similarity, and efficient routing can be simply achieved by iteratively jumping towards the neighbor that is closest to the destination. The network map provides a means for implementing routing on social networks that can be used in "darknets", that is, anonymous networks where nodes establish connections only if they are mutually trusted. Moreover, the distance between nodes on the network map can be used as a measure of node affinity, and may help in various types of network analysis, for instance to help evaluate reputation in webs of trust, or in order to perform "personalized" ranking. © 2007 IEEE.