Lada A. Adamic, Rajan M. Lukose, Bernardo A. Huberman
HP Laboratories
Palo Alto, CA 94304
Abstract
We discuss a number of message-passing algorithms that can be efficiently
used to search through power-law networks. Most of these algorithms are meant
to be improvements for peer-to-peer file sharing systems, and some may also
shed some light on how unstructured social networks with certain topologies
might function relatively efficiently with local information. Like the
networks that they are designed for, these algorithms are completely
decentralized, and they exploit the power-law link distribution in the node
degree. We demonstrate that some of these search algorithms can work well on
real Gnutella networks, scale sub-linearly with the number of nodes, and may
help reduce the network search traffic that tends to cripple such networks.
Full paper: reviewchap.pdf
To appear in: 'Handbook of Graphs and Networks:
From the Genome to the Internet', S. Bornholdt and H.G. Schuster (eds.), Wiley-VCH, Berlin, 2002.
|
printable version
