[cond-mat/0205383] Identity and Search in Social Networks on arxiv.org.
Mathematical analysis of an old sociology experiment; How can individuals in a social network pass messages to each other when they are unaware of the links between them. Most relevant for P2P networking and P2P search.
It uses some network theory and probability to solve this. Depends primarily on two things. That individuals in the real world cluster on more than one thing. Each node (person) has a number of dimensions of similarity/dissimilarity, for individuals in a social world these could be things such as profession or geographical closeness, plus many more besides. All of these together give a vector of similarity/dissimilarity for each node relative to each other. Two people can cluster round either geographic similarity (live on same street) or professional (work at same place), so either of these dimensions can be used for similarity. We don’t have to perform any triangulation to determine distance. Thus each individual node can cluster with more other nodes, and share multiple networks. (This sharing of networks is one of the most interesting aspects of the paper, one not examined).
Its also relies heavily on a low probability of chain termination. In automated systems this can be set arbitrarily low. So little problem here.
