We all know about the Stanley Milgram experiment that gave rise to the phrase "Six degrees of separation", and much has been made of the role of hubs or connectors in helping the messages carried between Omaha and Boston get there in such a small number of hops.

Left unexplained, however, was how each member of a successful path guessed at where to forward the letter next, given that any participant who knew the ultimate recipient in Boston simply forwarded it directly. It's the search mechanism used to decide who to forward it to, i.e. who was socially closer to the target, that needs explaining. The small world network (Duncan Watts' label) uncovered by the Milgram experiment had the curious property of being successfully searchable with no global co-ordination and few long paths -- messages tended to arrive quickly or not at all.

Duncan Watts, Peter Dodds, and Mark Newman have published a paper called Identity and Search in Social Networks, which describes how such successful social searches can be described. Most interesting for people designing software that might require distributed search are their list of 6 assumptions about how humans actually think about their own social networks:

#4. Individuals hierarchically cluster the social world in more than one way (for example, by geography and by occupation). We assume that these categories are independent, in the sense that proximity in one does not imply proximity in another. For example, two people may live in the same town but not share the same profession.

As with everything written by Watts, it's worth a read.

(Footnote: As important as the Milgram experiement was in sparking interest in the area of social networks, research by Judith Kleinfeld suggests that Milgram's own experimental evidence indicates that such high-degree network traversals are actually quite rare.)