[freehaven-dev] Paper on "search in power-law graphs"

[dmolnar <dmolnar@hcs.harvard.edu>]

Seen on infoanarchy.org

http://www.parc.xerox.com/istl/groups/iea/papers/plsearch/

Search in Power-Law Networks

Lada A. Adamic, Rajan M. Lukose, Amit R. Puniyani and Bernardo A.
Huberman

Abstract 
Many communication and social networks have power-law link distributions,
containing a few nodes which have a very high degree and many with low
degree. The high connectivity nodes play the important role of hubs in
communication and networking, a fact which can be exploited when designing
efficient search algorithms. We introduce a number of local search
strategies which utilize high degree nodes in power-law graphs and which
have costs which scale sub-linearly with the size of the graph. We also
demonstrate the utility of these strategies on the Gnutella peer-to-peer
network.