How To Search a Social Network
Lada A. Adamic and Eytan Adar

We address the question of how participants in a small world experiment are able to find short paths in a social network using only local information about their immediate contacts. We simulate such experiments on a network of actual email contacts within an organization. We show that strategies using information about a contact's position in physical space or in an organizational hierarchy relative to the target can effectively be used to locate most targets using the small world method but not necessarily where the network is incomplete. We compare our findings to recent theoretical hypothesis about underlying social structure that would enable these simple search strategies to succeed.

Social Networks, 27(3):187-203, July 2005, pre-print: PDF (445k).